jika saya hanya menginginkan satu elemen dari matriks invers, apakah ada algoritma yang cepat?

9

Saya menggunakan Mathematica untuk menyelesaikan masalah. Saya punya pertanyaan tentang matriks invers.

jika saya hanya menginginkan satu elemen dari matriks invers, apakah ada algoritma yang lebih cepat daripada menggunakan Inverseuntuk menghitung seluruh matriks invers dan mengekstrak elemen yang saya inginkan?

algorithms pengguna15964
sumber
Ini kertas abstrak mengatakan mereka dapat menghitung mereka diagonal dari matriks kebalikan di , tapi saya tidak tahu apakah ada sesuatu untuk entri yang sewenang-wenang. O(n32)
G. Bach
Masalah mendasar di sini mungkin tentang Matematika lebih dari Ilmu Komputer .
Dukeling
1
Berikut adalah sesuatu yang lebih dari sekedar diagonal untuk matriks jarang, dan di sini ada sesuatu pada algoritma paralel untuk matriks jarang terstruktur.
G. Bach
@ G.Bach, terima kasih atas informasi Anda
user15964
2
@ G.Bach Banyak jawaban saya yang seperti itu. Menggunakan google secara efektif adalah hal yang tidak sepele. Jika informasi itu berguna, maka ia menjawab pertanyaan itu.
Yuval Filmus

Jawaban:

1

Saya belum melihat persis ini di Mathematica tapi saya pikir bisa menyelesaikan persamaan yang ditetapkan hanya untuk satu yang tidak diketahui dapat didukung.

Cara langsung tentu saja akan mengimplementasikan algoritma matriks terbalik dan meminta mereka berhenti ketika elemen tertentu ditentukan. Mungkin akan menarik untuk melihat optimasi apa yang dapat Anda miliki untuk setiap algoritma jika tujuannya adalah untuk mendapatkan satu elemen saja.

Tetapi menurut paragraf pertama, satu ide bisa untuk mengekspresikan invers matriks Anda sebagai tidak dikenal dalam sistem persamaan dan kemudian mencoba memecahkan hanya untuk yang tidak diketahui yang Anda butuhkan (karena memecahkan persamaan yang ditetapkan untuk satu yang tidak diketahui harus didukung). Jika Anda mendapatkan memori dan kinerja CPU yang lebih baik maka mungkin aman untuk mengatakan bahwa Mathematica tidak benar-benar menyelesaikan seluruh persamaan tetapi hanya melakukan optimasi untuk menentukan hanya Anda yang tidak dikenal. Anda mungkin mendapatkan kinerja yang lebih buruk tentu saja karena Anda tidak menggunakan algoritma terbalik secara langsung. Jika Anda memutuskan untuk mencoba beri tahu kami jika itu berhasil!

pengguna3134164
sumber