Apakah ada algoritma eksponensial matriks paralel yang lebih efisien daripada perkalian sekuensial?

Satu diperlukan untuk menemukan kekuatan (bilangan bulat positif) dari matriks bilangan real. Ada banyak algoritma multiplikasi matriks yang efisien (mis. Beberapa algoritma paralel adalah Cannon's, DNS ) tetapi apakah ada algoritma yang ditujukan tepat untuk menemukan kekuatan matriks dan yang lebih efisien daripada eksekusi berurutan dari multiplikasi matriks? Saya sangat tertarik dengan algoritma paralel.

Jika Anda memiliki banyak prosesor yang dapat bekerja secara paralel, maka Anda dapat menghitung daya apa pun hingga daya (2 ^ k) dalam langkah k. Misalnya: Untuk menghitung , Anda menghitung:$M^{15}$

Tahap 1: Hitung $M^2$

Tahap 2: Hitung dan M 4 = M 2 ∗ M $M^3 = M^2 * M$$M^4 = M^2 * M^2$

Tahap 3: Hitung dan M 8 = M 4 ∗ M $M^7 = M^4 * M^3$$M^8 = M^4 * M^4$

Tahap 4: Hitung $M^{15} = M^8 * M^7$

Ini adalah salah satu perkalian lebih dari menghitung dalam tiga perkalian dan meningkatkan M 5 dengan kekuatan ketiga dalam dua perkalian, tetapi harus lebih cepat jika Anda memiliki dua prosesor. Untuk kekuatan besar yang sewenang-wenang, Anda akan membutuhkan lebih banyak prosesor.$M^5$$M^5$

Jika Anda menggunakan algoritma brute force untuk perkalian, mengalikan baris demi kolom, Anda dapat menghemat waktu dengan menghitung satu baris produk, kemudian segera menggunakan baris itu untuk produk berikutnya. Ini akan membantu dalam perhitungan mana kita dapat mulai menghitung M 3 segera setelah baris pertama M 2 telah dihitung; itu tidak akan membantu dengan M 4 karena kita membutuhkan baris dan kolom M 2 . Untuk kekuatan besar, Anda mungkin bisa mengatur kekuatan mana yang harus dihitung.$M^3$$M^3$$M^2$$M^4$$M^2$

Dan setelah posting ini menjadi jelas bahwa Anda dapat menggunakan beberapa prosesor sangat mudah: Anda mulai dengan menghitung baris pertama dari . Ketika Anda memiliki baris itu, Anda memiliki semua informasi yang Anda butuhkan untuk menghitung baris pertama M 3 = M 2 ∗ M , jadi Anda menghitung baris kedua M 2 dan baris pertama M 3 secara paralel. Kemudian Anda dapat menghitung baris ketiga M 2 , baris kedua M 3 , dan baris pertama M 4 secara paralel dan seterusnya.$M^2 = M * M$$M^3 = M^2 * M$$M^2$$M^3$$M^2$$M^3$$M^4$

Ini akan melakukan lebih banyak operasi daripada yang diperlukan (misalnya, 14 perkalian matriks untuk bukannya minimal 5 atau 6 dari metode empat tahap). Jika daya tidak besar dibandingkan dengan jumlah prosesor ini masih akan lebih cepat. Tetapi menghitung M 1000 dengan empat prosesor menggunakan metode ini akan tidak efisien; melakukan ini secara optimal akan menjadi masalah yang menarik.$M^{15}$$M^{1000}$

Menggabungkan pendekatan: Menggunakan empat prosesor misalnya, Anda dapat menghitung AB, ABC, ABCD, dan ABCDE hampir secara paralel dengan menghitung setiap produk satu baris setiap kali. Ini memungkinkan penghitungan keempat hingga M 5 menggunakan empat prosesor dalam waktu yang hampir bersamaan dengan satu produk dengan satu prosesor.$M^2$$M^5$

Dengan keempat hasil ini dan M asli, Anda dapat menghitung empat matriks hingga M 25 dalam waktu yang sama lagi, asalkan matriks paling tidak memiliki lima kekuatan yang terpisah satu sama lain. Jadi setiap daya hingga M 25 dapat dihitung dalam waktu sekitar dua kali lipat dari produk matriks prosesor tunggal.$M^6$$M^{25}$$M^{25}$

Dengan matriks ini dihitung, semua matriks hingga dan beberapa lagi hingga M 125 dapat dihitung dalam tiga kali waktu produk matriks tunggal jika empat prosesor tersedia. Dengan prosesor k, ini harus naik setidaknya ke daya k ( k + 1 ) 2 .$M^{108}$$M^{125}$$k (k+1)^2$

Ada dua level yang dapat Anda analisis percepatan paralel dengan eksponensiasi matriks: Level "makro-algoritmik" yang menentukan matriks mana yang akan dikalikan, dan level "mikro-algoritmik" di mana Anda dapat mempercepat perkalian sendiri dengan paralelisme.

Untuk yang terakhir, Wikipedia menunjukkan bahwa untuk mengalikan suatu oleh n matriks, kita dapat mencapai kompleksitas O ( log 2 ( n ) ) secara teoritis dengan jumlah tak terbatas dari prosesor, atau O ( n ) dengan algoritma paralel yang lebih realistis.$n$$n$$O(\log^2(n))$$O(n)$

(Catatan: halaman wikipedia adalah untuk perhitungan matriks umum. Saya tidak yakin apakah itu dapat diparalelkan lebih jauh dengan menggunakan informasi bahwa kami mengkuadratkan matriks.)

$A^m$$A$

$A^k$$O(\log(k))$

Pertanyaannya adalah: dapatkah kita mengalahkan ini dengan paralelisme? Saya mengklaim jawabannya tidak.

Alasan sederhananya adalah bahwa eksponensial dengan mengkuadratkan pada dasarnya adalah algoritma pemrograman dinamis; itu memungkinkan Anda melewati semua pekerjaan dengan menggunakan kembali subresult, tetapi ini pada gilirannya menciptakan ketergantungan data yang melarang paralelisme. Jika kita menghilangkan ketergantungan data, tetapi kita juga sangat meningkatkan jumlah pekerjaan yang harus kita lakukan.

$k$

$\frac{k}{2}$

$k$$O(\log(k))$

Namun, jika kita melakukan eksponensial dengan cara ini, akan terlihat seperti ini:

$A^2$

$A^k$$n$$n$$A$$O(\log^2(n)\log(k))$$O(n\log(k))$

$m$$\log m$$2$$m$