Cara tercepat untuk menyelesaikan sistem persamaan linear

Saya harus memecahkan sistem hingga 10.000 persamaan dengan 10.000 tidak diketahui secepat mungkin (lebih disukai dalam beberapa detik). Saya tahu bahwa eliminasi Gaussian terlalu lambat untuk itu, jadi algoritma apa yang cocok untuk tugas ini?

Semua koefisien dan konstanta adalah bilangan bulat non-negatif modulo p (di mana p adalah bilangan prima). Dijamin hanya ada 1 solusi. Saya perlu solusi modulo p.

Sebuah dekomposisi LU dari$n \times n$ matriks dapat dihitung dalam $O(M(n))$ waktu di mana $M(n)$ adalah waktu untuk melipatgandakan dua $n \times n$matriks. Oleh karena itu, Anda dapat menemukan solusi untuk sistem$n$ persamaan linear dalam $n$ tidak diketahui di $O(M(n))$waktu. Sebagai contoh, algoritma Strassen mencapai$M(n) = O(n^{2.8})$, Yang lebih cepat dari eliminasi Gaussian. Lihat https://en.wikipedia.org/wiki/Invertible_matrix#Blockwise_inversion .

Daripada mencoba mengimplementasikan ini sendiri, saya akan menyarankan menggunakan perpustakaan: misalnya, perpustakaan BLAS.

Ada apa yang ingin Anda capai, dan ada kenyataan, dan kadang-kadang mereka saling bertentangan. Pertama, Anda memeriksa apakah masalah Anda merupakan kasus khusus yang dapat diselesaikan lebih cepat, misalnya matriks jarang. Kemudian Anda mencari algoritma yang lebih cepat; Dekomposisi LU akan berakhir sedikit lebih cepat. Kemudian Anda menyelidiki apa yang dapat dilakukan Strassen untuk Anda (yang tidak terlalu banyak; itu dapat menghemat 1/2 operasi jika Anda mengalikan ukuran masalah dengan 32).

Dan kemudian Anda menggunakan kekerasan. Gunakan sistem multi-prosesor dengan banyak utas. Gunakan unit vektor yang tersedia. Atur data dan operasi Anda agar ramah terhadap cache. Selidiki apa cara tercepat untuk melakukan perhitungan modulo p untuk beberapa p tetap. Dan Anda sering dapat menyimpan operasi dengan tidak melakukan operasi modulo p (menghasilkan rentang 0 ≤ hasil <p) tetapi sedikit lebih santai (misalnya menghasilkan rentang -p <hasil <p).

Cara terbaik untuk memecahkan persamaan linear besar adalah dengan menggunakan parallelisation atau entah bagaimana untuk mendistribusikan komputasi di antara CPU atau lebih.

Lihat CUDA, OpenCL, OpenMP.

Banyak orang menyarankan Strassen's algorithmtetapi memiliki konstanta tersembunyi yang sangat besar yang membuatnya tidak efisien.

Omong-omong: persamaan linear Anda mungkin sangat jarang (banyak nol), ada beberapa optimisasi yang sangat rapi untuk menyelesaikannya secara paralel.