Jumlah minimum operasi aritmatika untuk menghitung penentu

Apakah ada pekerjaan pada menemukan jumlah minimum operasi aritmatika dasar yang diperlukan untuk menghitung determinan dari suatu oleh matriks untuk kecil dan tetap ? Misalnya, . $n$ $n$ $n$ $n=5$

cc.complexity-theory linear-algebra determinant Lembik
sumber

Saya telah bertanya kepada para ahli tentang hal ini, dan tampaknya saat ini tidak diketahui apakah diperlukan 9 kali perkalian untuk menghitung determinan matriks 3x3.

Jeffrey Shallit

@ JeffreyShallit Jika adalah mungkin itu sudah menarik (karena kurang dari misalnya). Bagaimana dengan ?

9

$9$

n^{3}

$n^3$

n = 4

$n=4$

Lembik

Tidak, tidak menarik sama sekali. 9 perkalian untuk n = 3 diikuti oleh ekspansi oleh anak di bawah umur. Untuk n = 4 lagi, ekspansi oleh anak di bawah umur memberi 40. Saya tidak tahu bagaimana melakukannya dalam waktu kurang dari 40 perkalian.

Jeffrey Shallit

@ JeffreyShallit Oh, begitu, bagus. Sungguh menakjubkan (setidaknya bagi saya) jika tidak ada yang lebih baik daripada naif yang dikenal untuk tetap .

n

$n$

Lembik

Jika seseorang tahu, mungkin mereka bisa memberi tahu kami.

Jeffrey Shallit

Hal ini diketahui bahwa jumlah operasi aritmatika yang diperlukan untuk menghitung determinan dari suatu $n\times n$ matriks adalah $n^{\omega+o(1)}$ , di mana $\omega$ adalah perkalian matriks konstan. Lihat misalnya tabel ini di Wikipedia, serta catatan kaki dan rujukannya. Perhatikan bahwa kompleksitas asimptotik dari inversi matriks juga sama dengan perkalian matriks dalam pengertian yang sama.

Persamaannya cukup efektif. Secara khusus, Anda secara rekursif dapat menghitung determinan dari matriks dengan bekerja pada blok menggunakan komplemen Schur: $n\times n$ $(n/2) \times (n/2)$

D invertible ⟹ det (\begin{matrix} A & B \\ C & D \end{matrix}) = det (D) det (A - B D^{- 1} C) .

$\text{$D$ invertible}\qquad\implies\qquad\det \begin{pmatrix}A&B\\C&D\end{pmatrix} = \det(D) \det(A-BD^{-1}C).$

Dengan demikian, Anda dapat menghitung sebuah penentu dengan menghitung dua faktor penentu, pembalik satu matriks, mengalikan dua pasang matriks, dan beberapa operasi yang lebih sederhana. Memperluas panggilan penentu secara rekursif, kompleksitas akhirnya didominasi oleh perkalian dan inversi matriks. $n\times n$ $(n/2)\times (n/2)$ $(n/2)\times (n/2)$ $(n/2)\times (n/2)$

Ini bekerja dengan baik bahkan untuk kecil dan bahkan tanpa menggunakan algoritma perkalian matriks sub-kubik. (Tentu saja, pada akhirnya lebih atau kurang setara dengan eliminasi Gaussian.) Misalnya, untuk , kita dapat menghitung dengan dua perkalian, dengan empat divisi, dengan perkalian, $n$ $n=4$ $\det(D)$ $D^{-1}$ $BD^{-1}C$ $2\times 8=16$ $\det(A-BD^{-1}C)$ dengan dua perkalian, dan jawaban terakhir dengan satu perkalian. Jumlah totalnya adalah perkalian ditambah divisi, yang kurang dari dari ekspansi kofaktor. Menggunakan algoritma Strassen menyimpan dua perkalian di sini, tetapi lebih asimtotik. $2+4+16+2+1=25$ $40$

Anda mungkin memperhatikan bahwa ekspansi ini sangat menggunakan divisi. Jika Anda ingin menghindari pembagian, maka seseorang dapat melakukannya dalam operasi dengan bekerja dengan urutan Clow dan pemrograman dinamis . Juga diketahui bagaimana mencapai perkalian dan tidak ada divisi. $O(n^4)$ $n^{2+\omega/2+o(1)}$

A. Rex
sumber

Apakah Anda tahu ada batas bawah hanya pada jumlah perkalian? Bahkan untuk n = 3?

Jeffrey Shallit

Kalimat Anda "jumlah operasi aritmatika yang diperlukan untuk menghitung determinan dari suatu

matriks adalah

" menunjukkan bahwa batas bawah dikenal. Tetapi saya tidak melihat ini dalam salah satu karya yang dikutip. Apakah saya melewatkan sesuatu?

n \times n

$n \times n$

n^{ω + o (1)}

$n^{\omega +o(1)}$

Jeffrey Shallit

Batas bawah ada di koran oleh W.Baur dan V.Strassen "Kompleksitas turunan parsial" ( dx.doi.org/10.1016/0304-3975(83)90110-X )

Vladimir Lysikov

Jumlah minimum operasi aritmatika untuk menghitung penentu

Jawaban: