Saya memiliki dua grafik dengan masing-masing hampir n ~ 100000 node. Dalam kedua grafik, setiap node terhubung tepat ke 3 node lainnya sehingga matriks adjacency simetris dan sangat jarang.
Bagian yang sulit adalah saya membutuhkan semua nilai eigen dari matriks adjacency tetapi bukan vektor eigen. Agar akurat, ini akan menjadi sekali seumur hidup saya (sejauh yang saya bisa lihat, setidaknya!) Jadi saya ingin mendapatkan semua nilai eigen dan tidak keberatan menunggu beberapa hari untuk mendapatkannya.
Saya mencoba scipy
pembungkus di sekitar ARPACK
, tetapi terlalu lama. Saya menemukan beberapa perpustakaan tetapi mereka bekerja paling baik untuk mendapatkan subset dari nilai eigen terbesar / terkecil. Apakah ada perpustakaan yang berfungsi untuk matriks jarang simetris dengan implementasi paralel mungkin untuk mendapatkan semua nilai eigen?
Jawaban:
Anda dapat menggunakan transformasi spektral shift-invert [1] dan menghitung pita spektrum demi pita.
Teknik ini juga dijelaskan dalam artikel saya [2]. Selain implementasi di [1], implementasi tersedia di C ++ di perangkat lunak Graphite saya [3] ( pembaruan 17 Januari : sekarang semuanya porting ke geogram / grafit versi 3 ), yang saya gunakan untuk menghitung fungsi eigen dari operator Laplace untuk jerat dengan hingga 1 juta simpul (masalah yang mirip dengan Anda).
Bagaimana itu bekerja:
[1] http://www.mcs.anl.gov/uploads/cels/papers/P1263.pdf
[2] http://alice.loria.fr/index.php/publications.html?redirect=0&Paper=ManifoldHarmonics@2008
[3] http://alice.loria.fr/software/graphite/doc/html/
sumber
Opsi lain akan menggunakan rotasi Jacobi. Karena matriks Anda sudah hampir diagonal, seharusnya tidak perlu banyak waktu untuk bertemu. Secara umum konvergen dalam laju linier, tetapi setelah iterasi yang cukup, laju konvergensi menjadi kuadratik.
sumber