Die Mindestanzahl von Rechenoperationen zur Berechnung der Determinante

14

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 .

Lembik
quelle
4
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 n 3 ist ). Wie wäre es mit n = 4 ? 9n3n=4
Lembik
3
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
Lembik
Wenn jemand Bescheid weiß, kann er es uns vielleicht sagen.
Jeffrey Shallit

Antworten:

9

Es ist bekannt , dass die Anzahl der Rechenoperationen erforderlich , die Determinante einer berechnen - Matrix ist n ω + O ( 1 ) , 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×nnω+o(1)ω

Die Äquivalenz ist sehr effektiv. Insbesondere können Sie die Determinante einer Matrix rekursiv berechnen, indem Sie daran arbeitenn×n -Blöcke mit dem Schur-Komplement:(n/2)×(n/2)

D invertibledet(ABCD)=det(D)det(ABD1C).

Sie können also eine Determinante berechnen , indem Sie zwei ( n / 2 ) × ( n / 2 ) -Determinanten berechnen, eine ( n / 2 ) × ( n / 2 ) -Matrix invertieren und zwei Paare von ( n / 2 ) multiplizieren. × ( n / 2 ) Matrizen und einige einfachere Operationen. Wenn die Determinantenaufrufe rekursiv erweitert werden, wird die Komplexität letztendlich von der Matrixmultiplikation und -inversion dominiert.n×n(n/2)×(n/2)(n/2)×(n/2)(n/2)×(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 n = 4 det ( D ) mit zwei Multiplikationen berechnen , D - 1 mit vier Divisionen, B D - 1 C mit 2 × 8 = 16 Multiplikationen det ( A - B D - 1 C )nn=4det(D)D1BD1C2×8=16det(ABD1C)mit zwei Multiplikationen und die endgültige Antwort mit einer Multiplikation. Die Gesamtzahl beträgt Multiplikationen plus Divisionen, was weniger als die 40 aus der Cofaktorerweiterung ist. Die Verwendung des Strassen-Algorithmus spart hier zwei Multiplikationen, jedoch mehr asymptotisch.2+4+16+2+1=2540

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 n 2 + ω / 2 + o ( 1 ) -Multiplikationen und keine Divisionen erzielt.O(n4)n2+ω/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×nnω+o(1)
2
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