Apa algoritma tercepat untuk menghitung matriks invers dan determinannya untuk matriks simetris pasti positif?

Diberikan matriks simetris pasti positif, apa algoritma tercepat untuk menghitung matriks terbalik dan determinannya? Untuk masalah yang saya tertarik, dimensi matriks adalah 30 atau kurang.

Akurasi dan kecepatan tinggi sangat diperlukan. (jutaan matriks dilakukan)
Penentu diperlukan. Dalam setiap perhitungan, hanya satu elemen dari matriks iverse yang diperlukan. Terima kasih!

algorithms matrix Pesanan
sumber

Apakah Anda harus membalik jutaan matriks seperti itu? Kalau tidak, kecepatan seharusnya tidak menjadi masalah.

Wolfgang Bangerth

Saya mengedit judul dan pertanyaan Anda untuk kejelasan. Jika saya membuat kesalahan, harap beri tahu saya.

Geoff Oxberry

@ Wolfgang Bangerth Ya, kecepatan harus dipertimbangkan.

Pesanan

Apakah Anda tahu elemen matriks invers mana yang diperlukan? Atau dapatkah itu entri acak?

Memming

@Orders Komentar dan edit Anda tampaknya bertentangan: apakah Anda memerlukan satu elemen dari invers, atau semuanya ?

Federico Poloni

Untuk masalah yang saya tertarik, dimensi matriks adalah 30 atau kurang.

Sebagai catatan WolfgangBangerth, kecuali jika Anda memiliki sejumlah besar matriks ini (jutaan, miliaran), kinerja inversi matriks biasanya tidak menjadi masalah.

Diberikan matriks simetris pasti positif, apa algoritma tercepat untuk menghitung matriks terbalik dan determinannya?

Jika kecepatan adalah masalah, Anda harus menjawab pertanyaan-pertanyaan berikut:

Apakah Anda benar-benar membutuhkan keseluruhan terbalik? (Banyak aplikasi tidak perlu membentuk invers eksplisit.)
Apakah Anda benar-benar membutuhkan determinan? (Faktor-faktor penentu tidak umum, tetapi tentu saja tidak pernah terdengar dalam ilmu komputasi.)
Apakah Anda perlu keakuratan tinggi? (Algoritma akurasi rendah cenderung lebih cepat.)
Apakah perkiraan probabilistik sudah mencukupi? (Algoritma probabilitas cenderung lebih cepat.)

$A = LL^{T}$ $\det(A) = \prod_{i=1}^{n}l_{ii}^{2}$ $\det(A^{-1}) = \prod_{i=1}^{n}l_{ii}^{-2}$

Dengan asumsi adalah oleh , dekomposisi Cholesky dapat dihitung di sekitar jepit, yaitu sekitar setengah biaya dekomposisi LU. Namun, algoritma seperti itu tidak akan dianggap "cepat". Sebuah acak dekomposisi LU $A$ $n$ $n$ $n^{3}/3$ mungkin algoritma yang lebih cepat layak dipertimbangkan jika (1) Anda benar-benar harus memfaktorkan sejumlah besar matriks, (2) faktorisasi adalah benar-benar langkah pembatas dalam aplikasi Anda, dan (3) setiap kesalahan yang terjadi dalam menggunakan algoritma acak adalah dapat diterima. Matriks Anda mungkin terlalu kecil untuk algoritma jarang menjadi berharga, sehingga satu-satunya peluang untuk algoritma yang lebih cepat akan memerlukan struktur matriks tambahan (mis., Berpita), atau mengeksploitasi struktur masalah (mis., Mungkin Anda dapat dengan cerdik menata ulang algoritma Anda sehingga Anda tidak perlu lagi menghitung invers matriks atau determinannya). Algoritma determinan yang efisien kira-kira merupakan biaya penyelesaian sistem linear, hingga dalam faktor konstan, sehingga argumen yang sama yang digunakan untuk sistem linear juga berlaku untuk menghitung determinan.

Geoff Oxberry
sumber

Hanya sebuah catatan singkat: jika , untuk menghitung satu elemen satu harus menghitung hanya th kolom . Setelah factorisation Cholesky dihitung, ini dilakukan dengan substitusi maju dan mundur sehubungan dengan vektor rhs dari semua nol dan dengan hanya satu di baris . Karena perhitungan dapat terputus segera setelah telah dihitung, kasus terbaik adalah untuk kasus terburuk untuk mana seseorang harus menghitung kembali penuh dan penggantian maju.

B = A^{- 1}

$B = A^{-1}$

b_{i j}

$b_{ij}$

j

$j$

B

$B$

j

$j$

b_{i j}

$b_{ij}$

b_{n n} = l_{n n}^{- 2}

$b_{nn} = l_{nn} ^{-2}$

b_{11}

$b_{11}$

Stefano M

@StefanoM Lebih baik lagi, Anda dapat mengubah permutasi matriks Anda sebelum permulaan perhitungan sehingga Anda selalu berada dalam kondisi terbaik.

Federico Poloni

Apa algoritma tercepat untuk menghitung matriks invers dan determinannya untuk matriks simetris pasti positif?

Jawaban: