Kompleksitas Menemukan Eigendekomposisi Matriks

Pertanyaan saya sederhana:

Apa waktu berjalan terburuk dari algoritma yang paling dikenal untuk menghitung komposisi eigend dari sebuah matriks ?$n \times n$

Apakah eigendecomposition mengurangi perkalian matriks atau apakah algoritma paling dikenal (melalui SVD ) dalam kasus terburuk?$O(n^3)$

Harap dicatat bahwa saya meminta analisis kasus terburuk (hanya dalam hal ), bukan untuk batas dengan konstanta yang tergantung masalah seperti nomor kondisi.$n$

EDIT : Dengan beberapa jawaban di bawah ini, izinkan saya menyesuaikan pertanyaan: Saya akan senang dengan pendekatan . Perkiraan dapat berupa multiplikasi, aditif, entri-bijaksana, atau definisi masuk akal apa pun yang Anda inginkan. Saya tertarik jika ada algoritma yang dikenal yang memiliki ketergantungan lebih baik pada daripada sesuatu seperti ?$\epsilon$$n$$O(\mathrm{poly}(1/\epsilon)n^3)$

EDIT 2 : Lihat pertanyaan terkait ini pada matriks simetris .

Ryan menjawab pertanyaan serupa tentang mathoverflow. Inilah tautannya: mathoverflow-answer

Pada dasarnya, Anda dapat mengurangi perhitungan nilai eigen menjadi perkalian matriks dengan menghitung faktor penentu simbolis. Ini memberikan waktu berjalan O ( ) untuk mendapatkan bit dari nilai eigen; runtime yang paling dikenal saat ini adalah O ( ) untuk perkiraan dalam .$n^{\omega+1}m$$m$$n^3+n^2\log^2 n\log b$$2^{-b}$

Referensi Ryan adalah `` Victor Y. Pan, Zhao Q. Chen: Kompleksitas masalah Eigen Matriks. STOC 1999: 507-516 ''.

(Saya percaya ada juga diskusi tentang hubungan antara kompleksitas nilai eigen dan multiplikasi matriks dalam buku Aho, Hopcroft, dan Ullman yang lebih tua '' Desain dan Analisis Algoritma Komputer '', namun, saya tidak memiliki buku di di depan saya, dan saya tidak bisa memberikan nomor halaman yang tepat.)

Menemukan nilai eigen secara inheren merupakan proses berulang: Menemukan nilai eigen setara dengan menemukan akar polinomial. Selain itu, teorema Abel-Ruffini menyatakan bahwa, secara umum, Anda tidak dapat mengekspresikan akar polinomial yang berubah-ubah dalam bentuk tertutup sederhana (yaitu dengan radikal seperti rumus kuadratik). Dengan demikian Anda tidak bisa berharap untuk menghitung nilai eigen "tepat".

Ini berarti bahwa algoritma dekomposisi spektral harus merupakan perkiraan. Waktu berjalan dari semua algoritma umum harus bergantung pada akurasi yang diinginkan; tidak bisa hanya bergantung pada dimensi.

Saya bukan ahli dalam hal ini. Saya kira ketergantungan kubik pada n cukup bagus. Algoritma yang saya lihat semuanya menggunakan perkalian matriks-vektor, bukan perkalian matriks-matriks. Jadi saya akan agak terkejut jika semuanya bermuara pada perkalian matriks-matriks.

Lihatlah http://en.wikipedia.org/wiki/List_of_numerical_analysis_topics#Eigenvalue_algorithms

Saya hanya akan memberikan jawaban parsial yang berkaitan dengan nilai eigen dari sebuah matriks.

Seperti disebutkan sebelumnya, ada banyak metode iteratif untuk menemukan nilai eigen dari suatu matriks (misalnya iterasi daya), tetapi secara umum, menemukan nilai eigen berkurang hingga menemukan akar dari polinomial karakteristik. Menemukan polinom karakteristik dapat dilakukan dalam , di mana adalah biaya bit dikalikan dan adalah ukuran bit dari entri maksimum, oleh perhitungan determinan simbolis menggunakan Algoritma Bareiss . Lihat buku Yap tentang "Fundamental Aljabar Algoritma" , khususnya, Bab. 10, "Sistem Linier" .$O(n^3 M_B[n(log n + L)] )$$M_B(s)$$s$$L$

Setelah polinomial karakteristik ditemukan, seseorang dapat menemukan akar dengan tingkat akurasi yang diinginkan dengan menggunakan interval isolasi. Lihat buku Yap, Bab. 6 "Roots of Polynomials" untuk detail. Saya lupa waktu menjalankan yang tepat tetapi jumlahnya banyak pada tingkat karakteristik yang banyak dan angka akurasi yang diinginkan.

Saya menduga bahwa menghitung vektor eigen hingga tingkat akurasi berapa pun juga polinomial, tetapi saya tidak melihat algoritma yang lurus ke depan. Tentu saja ada sekumpulan trik standar yang telah disebutkan sebelumnya, tetapi sejauh yang saya tahu, tidak ada yang menjamin polinomial run time untuk akurasi yang diinginkan.

Anda bisa memeriksa makalah baru oleh Commandur dan Kale yang memberikan algoritma kombinatorial untuk Max-Cut. Tampaknya (dari bacaan sepintas) bahwa algoritma mereka didasarkan pada kombinasi mencari vektor eigen yang sesuai dengan nilai eigen maksimum, dan kemudian menggunakan algoritma Luca Trevisan begitu mereka memiliki vektor eigen ini.

Tampaknya mereka menggunakan pendekatan alternatif untuk algoritma Lanczos untuk menemukan vektor eigen seperti itu, sehingga mungkin menarik. Saya tidak yakin apa kompleksitas yang diklaim dari metode mereka untuk menemukan vektor eigen, tetapi mungkin layak untuk dilihat. Juga, karena ini adalah rasio perkiraan dan bukan waktu yang mereka minati, batas waktu apa pun yang mereka berikan mungkin tidak optimal.

Ini adalah pertanyaan lama tetapi beberapa literatur penting tampaknya telah terjawab.

Ada algoritma yang kami miliki dukungan teoretisnya lebih kuat. Misalnya, ada iterasi berdasarkan fungsi tanda matriks, lihat misalnya "Aljabar Linier Cepat Stabil" oleh Demmel, Dumitriu, dan Holtz . Dalam makalah itu, ditunjukkan bahwa masalah nilai eigen dapat diselesaikan dalam waktu , di mana adalah eksponen dari perkalian matriks dan adalah angka .$(O^{\omega+\eta})$$\omega$$\eta$$>0$

Ya, ada kertas Pan + Chen + Zheng yang menyarankan merakit polinomial karakteristik dan menghitung di BigFloat karena Anda kehilangan banyak bit akurasi pada akhirnya, tetapi tidak banyak orang akan menganggap ini sebagai pendekatan praktis.

Saya juga menyebutkan bahwa algoritma yang paling banyak digunakan, iterasi Francis QR, tidak memiliki bukti konvergensi untuk matriks umum; buku karya Kressner membahas beberapa contoh tandingan.

Ya, hampir semua aljabar linear numerik dapat dikurangi menjadi perkalian matriks, meskipun, seperti biasa, stabilitas numerik adalah masalah. Juga, dengan masalah seperti komposisi eigend, Anda harus puas dengan perkiraan karena solusinya mungkin tidak rasional. Lihatlah buku Komputasi Polinomial dan Matriks oleh Bini dan Pan.

Berikut referensi lain - Aljabar Linear Cepat Stabil http://www.netlib.org/lapack/lawnspdf/lawn186.pdf