Bagaimana cara menghitung kekuatan matriks bujur sangkar?

Misalkan kita diberi matriks , dan biarkan . Seberapa cepat kita dapat menghitung kekuatan dari matriks itu?$A \in \mathbb R^{N\times N}$$m \in \mathbb N_0$$A^m$

Hal terbaik berikutnya dibandingkan dengan menghitung produk- adalah memanfaatkan eksponen cepat, yang membutuhkan produk-produk matriks .$m$$\mathcal O(\log m )$

Untuk matriks yang dapat didiagonalisasi, dekomposisi nilai eigen dapat digunakan. Generalisasi alami, dekomposisi Jordan, tidak stabil di bawah pertubasi dan karena itu tidak masuk hitungan (afaik).

Bisakah matriks eksponensial dalam kasus umum dipercepat?

Eksponen cepat menyarankan variasi pertanyaan ini juga berguna:

Dapatkah kuadrat dari matriks umum dihitung lebih cepat daripada dengan algoritma penggandaan matriks yang dikenal?$A$

Seperti yang Anda perhatikan, komputasi dapat dilakukan dalam O ( log m ) kali jumlah operasi untuk perkalian matriks pada N × N matriks. Jawaban untuk pertanyaan kedua Anda adalah tidak, setidaknya untuk kompleksitas asimptotik - kuadrat matriks dan perkalian matriks memiliki kompleksitas waktu / aritmatika yang setara (hingga faktor konstan). Mengurangi kuadrat ke perkalian matriks jelas. Untuk mengurangi perkalian untuk mengkuadratkan, misalkan kita ingin menghitung produk A dan B . Bentuk 2 n × 2 n matriks C dengan struktur balok:$A^m$$O(\log m)$$N \times N$$A$$B$$2n \times 2n$$C$

$[0~~A]$

$[B~~0]$

Artinya, memiliki n × n semua-nol matriks dalam Surat kuadran kiri atas dan bawah kanan kuadran. Perhatikan bahwa C 2 berisi A ⋅ B di kuadran kiri atas.$C$$n \times n$$C^2$$A\cdot B$