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

11

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.

Untuk Tuan
sumber
1
Apa yang sudah kamu coba? Di mana Anda terjebak? Penelitian apa yang telah Anda lakukan? Selain judul, di mana pertanyaannya? Untuk versi keputusan masalah Anda (dari judul), jawabannya adalah "ya", tetapi Anda sudah mengetahuinya, kan?
Jahat
2
@ TomR Pertanyaan ini mungkin menarik bagi Anda
adrianN
1
Mungkin kira - kira seperti ini ? Atau Anda mencari sesuatu yang lain? Apa ukuran dan kekuatan dalam aplikasi Anda?
Evil
1
Anda dapat menghitung daya ke-n dengan perkalian kurang dari n-1 ketika n ≥ 4. Untuk matriks besar, biasanya akan bermanfaat untuk menemukan jumlah perkalian sekecil mungkin (misalnya, ada metode sederhana untuk menghitung n ^ 15 dengan 6 perkalian, tetapi bisa dilakukan dengan 5). Anda kemudian dapat menerapkan prinsip yang sama untuk menemukan jumlah perkalian sekuensial terkecil, yang akan lebih sulit.
gnasher729
1
Anda juga harus mempertimbangkan jumlah paralelisme yang tersedia untuk Anda. "Paralelisme" adalah tentang mengeksploitasi sumber daya yang seharusnya tidak digunakan. Jika implementasi perkalian matriks sudah dapat menggunakan semua sumber daya yang tersedia secara efisien, maka tidak ada lagi yang bisa dieksploitasi untuk menghitung kekuatan matriks.
gnasher729

Jawaban:

5

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:M15

Tahap 1: Hitung M2

Tahap 2: Hitung dan M 4 = M 2M 2M3=M2MM4=M2M2

Tahap 3: Hitung dan M 8 = M 4M 4M7=M4M3M8=M4M4

Tahap 4: Hitung M15=M8M7

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.M5M5

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.M3M3M2M4M2

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 2M , 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.M2=MMM3=M2MM2M3M2M3M4

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.M15M1000

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.M2M5

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.M6M25M25

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 .M108M125k(k+1)2

gnasher729
sumber
4

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.nnHAI(catatan2(n))HAI(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.)

SEBUAHmSEBUAH

SEBUAHkHAI(catatan(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

SEBUAH1SEBUAH2SEBUAH3SEBUAH4SEBUAH5...SEBUAHk

k2

(SEBUAH1SEBUAH2)(SEBUAH3SEBUAH4)(SEBUAH5SEBUAH6)...(SEBUAHk-1SEBUAHk)

kHAI(catatan(k))

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

(SEBUAHSEBUAH)(SEBUAHSEBUAH)(SEBUAHSEBUAH)...(SEBUAHSEBUAH)

SEBUAH2

SEBUAHknnSEBUAHHAI(catatan2(n)catatan(k))HAI(ncatatan(k))

Kurt Mueller
sumber
3

mcatatanm2m

SEBUAH=SΛS-1SEBUAHm=SΛmS-1
mHAI(1)m
nbubis
sumber