Kompleksitas Menemukan Eigendekomposisi Matriks * Simetris *

9

Ini adalah versi khusus dari pertanyaan sebelumnya: Kompleksitas Menemukan Komposisi Eigend dari Matriks .

Untuk matriks simetris NxN, diketahui bahwa waktu O (N ^ 3) cukup untuk menghitung dekomposisi eigen. Pertanyaannya adalah: bisakah kita mencapai kompleksitas sub-kubik? Terima kasih.

ds.algorithms time-complexity matrices linear-algebra na.numerical-analysis Lihong Li
sumber
Apakah ini benar-benar memerlukan pertanyaan terpisah? Tentunya jika seseorang tahu jawaban untuk kasus khusus ini mereka akan mengatakannya dalam pertanyaan lain.
Warren Schudy
Saya menekankan kasus terburuk dalam pertanyaan saya, jadi saya pikir ini adil ...
Lev Reyzin
2
Apakah Anda yakin tentang batas waktu O (N ^ 3) itu? Lihat pertanyaan terkait saya tentang eliminasi Gaussian.
Jeff
Tampaknya dari mathoverflow.net/questions/24287/… Anda bisa mendapatkan untuk solusi perkiraan . O(n3)
Lev Reyzin

Jawaban:

2

Seperti yang saya lihat, kasus khusus ini tidak lebih mudah daripada kasus umum. Secara simbolis, Anda dapat mengurangi masalah menemukan dekomposisi nilai singular (SVD) menjadi masalah mendiagonalisasi matriks simetris. Kita dapat membaca SVD M dari vektor eigen dan nilai eigen M * M. Perhatikan bahwa reduksi hanya melibatkan perkalian matriks untuk menghitung M * M. Tampaknya tidak ada masalah numerik yang serius.


sumber