Die Mindestanzahl von Rechenoperationen zur Berechnung der Determinante

Wurde daran gearbeitet, die minimale Anzahl elementarer arithmetischer Operationen zu finden, die erforderlich sind, um die Determinante einer $n$ × $n$ Matrix für kleines und festes zu berechnen $n$ ? Zum Beispiel ist $n=5$ .

cc.complexity-theory linear-algebra determinant Lembik
quelle

Ich habe Experten dazu befragt, und anscheinend ist derzeit noch nicht einmal bekannt, ob 9 Multiplikationen erforderlich sind, um die Determinante einer 3x3-Matrix zu berechnen.

Jeffrey Shallit

@JeffreyShallit Wenn

möglich ist, ist das schon interessant (da es zum Beispiel weniger als

). Wie wäre es mit

9

$9$

n^{3}

$n^3$

n = 4

$n=4$

Lembik

Nein, überhaupt nicht interessant. 9 Multiplikationen für n = 3 folgen durch Erweiterung um Minderjährige. Für n = 4 ergibt die Erweiterung um Minderjährige wieder 40. Ich weiß nicht, wie ich es mit weniger als 40 Multiplikationen machen soll.

Jeffrey Shallit

@ JeffreyShallit Oh ich verstehe, guter Punkt. Es ist erstaunlich (zumindest für mich), wenn für ein festes

nichts Besseres als naiv bekannt ist .

n

$n$

Lembik

Wenn jemand Bescheid weiß, kann er es uns vielleicht sagen.

Jeffrey Shallit

Es ist bekannt , dass die Anzahl der Rechenoperationen erforderlich , die Determinante einer berechnen - Matrix ist , wobei die konstante Matrizenmultiplikation ist. Siehe zum Beispiel diese Tabelle auf Wikipedia sowie deren Fußnoten und Verweise. Es ist zu beachten, dass die asymptotische Komplexität der Matrixinversion auch der Matrixmultiplikation in diesem Sinne entspricht. $n\times n$ $n^{\omega+o(1)}$ $\omega$

Die Äquivalenz ist sehr effektiv. Insbesondere können Sie die Determinante einer Matrix rekursiv berechnen, indem Sie daran arbeiten $n\times n$ -Blöcke mit dem Schur-Komplement: $(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).$

Sie können also eine Determinante berechnen , indem Sie zwei -Determinanten berechnen, eine -Matrix invertieren und zwei Paare von multiplizieren. Matrizen und einige einfachere Operationen. Wenn die Determinantenaufrufe rekursiv erweitert werden, wird die Komplexität letztendlich von der Matrixmultiplikation und -inversion dominiert. $n\times n$ $(n/2)\times (n/2)$ $(n/2)\times (n/2)$ $(n/2)\times (n/2)$

Dies funktioniert gut, auch für kleine und sogar ohne Verwendung von subkubischen Matrixmultiplikationsalgorithmen. (Natürlich entspricht dies mehr oder weniger der Gaußschen Elimination.) Zum Beispiel können wir für mit zwei Multiplikationen berechnen , mit vier Divisionen, mit Multiplikationen $n$ $n=4$ $\det(D)$ $D^{-1}$ $BD^{-1}C$ $2\times 8=16$ $\det(A-BD^{-1}C)$ mit zwei Multiplikationen und die endgültige Antwort mit einer Multiplikation. Die Gesamtzahl beträgt Multiplikationen plus Divisionen, was weniger als die aus der Cofaktorerweiterung ist. Die Verwendung des Strassen-Algorithmus spart hier zwei Multiplikationen, jedoch mehr asymptotisch. $2+4+16+2+1=25$ $40$

Möglicherweise stellen Sie fest, dass bei dieser Erweiterung die Division entscheidend ist. Wenn Sie eine Teilung vermeiden möchten, können Sie dies in -Operationen tun, indem Sie mit Clow-Sequenzen und dynamischer Programmierung arbeiten . Es ist auch bekannt, wie man -Multiplikationen und keine Divisionen erzielt. $O(n^4)$ $n^{2+\omega/2+o(1)}$

A. Rex
quelle

Kennen Sie eine Untergrenze nur für die Anzahl der Multiplikationen? Auch für n = 3?

Jeffrey Shallit

n \times n

$n \times n$

n^{ω + o (1)}

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

Die untere Schranke ist in der Arbeit von W.Baur und V.Strassen "Die Komplexität partieller Ableitungen" ( dx.doi.org/10.1016/0304-3975(83)90110-X )

Vladimir Lysikov 30.11.16

Die Mindestanzahl von Rechenoperationen zur Berechnung der Determinante

Antworten: