Untere Schranken der Gaußschen Komplexität

18

Definieren Sie die Gaußsche Komplexität einer Matrix als die minimale Anzahl elementarer Zeilen- und Spaltenoperationen, die erforderlich sind, um die Matrix in die Form eines oberen Dreiecks zu bringen. Dies ist eine Größe zwischen 0 und n 2 (über die Gaußsche Elimination). Der Begriff ist in jedem Bereich sinnvoll.n×n0n2

Dieses Problem scheint sicherlich sehr grundlegend zu sein und muss untersucht worden sein. Überraschenderweise sind mir keine Referenzen bekannt. Also, ich freue mich über jeden Hinweis, den es gibt. Aber natürlich ist die Hauptfrage:

Sind nicht-triviale explizite Untergrenzen bekannt?

Mit nichttrivial meine ich superlinear. Um es klar zu machen: Über endlichen Feldern zeigt ein Zählargument, dass eine Zufallsmatrix die Komplexitätsordnung n ^ 2 hat (eine ähnliche Behauptung sollte über unendliche Felder gelten). Daher suchen wir eine explizite Familie von Matrizen, z. B. Hadmard-Matrizen. Dies ist dasselbe wie bei der Booleschen Schaltungskomplexität, bei der wir wissen, dass eine Zufallsfunktion eine hohe Komplexität aufweist, aber wir suchen nach expliziten Funktionen mit dieser Eigenschaft.

Moritz
quelle
Ich bin mir nicht ganz sicher, was die Frage hier ist. Fragen Sie nach bestimmten Matrizenformen oder nach dem allgemeinen Fall (in diesem Fall scheint ein einfaches Zählargument zu funktionieren)?
Joe Fitzsimons
@ Joe, wie bereits erwähnt, bitte ich um eine explizite Matrizenfamilie, zB Hadamard-Matrizen. Wie üblich betrügen zufällige Matrizen. Dies ist in etwa so, als wären wir mit der Tatsache nicht zufrieden, dass eine Zufallsfunktion große Schaltkreise erfordert. Ich habe einen Absatz hinzugefügt, um diesen Punkt zu betonen.
Moritz
Vielleicht sollte das als Antwort neu gepostet werden :)
Suresh Venkat
Ok, werde das tun.
Joe Fitzsimons
Eigentlich glaube ich, dass meine Methode fehlerhaft war.
Joe Fitzsimons

Antworten:

17

Dies scheint ein sehr schwieriges Problem zu sein, das mit einem umfassenderen Problem zusammenhängt.

Angenommen, wir betrachten eine quadratische invertierbare Matrix A und definieren c (A) als die minimale Anzahl elementarer Zeilenoperationen, die erforderlich sind, um A auf die Identitätsmatrix zu reduzieren. Dieses Maß für die Komplexität ist größer als das, was Moritz vorschlägt, weshalb es nur einfacher sein kann, superlineare Grenzen zu beweisen.

Zeilenoperationen sind jetzt umkehrbar . Daraus folgt, dass c (A) äquivalent als die minimale Anzahl von Zeilenoperationen definiert werden kann, die zur Erzeugung von A ausgehend von der Identitätsmatrix erforderlich sind.

Beachten Sie, dass die Erzeugung von A auf diese Weise zu einer arithmetischen Schaltung führt, mit der die Abbildung berechnet wird, die x zu Ax führt. Das Fanin jedes Gatters ist 2, und die Anzahl der nicht eingegebenen Gatter entspricht der Anzahl der Zeilenoperationen.

Es gibt keine offensichtliche Verringerung der umgekehrten Richtung (von Schaltkreisen zu Reihenoperationssequenzen). Dennoch können wir c (A) in Bezug auf die Rechenschaltungskomplexität von Ax in einem Modell mit eingeschränkter Schaltung charakterisieren: Ich behaupte, dass c (A) gleich der Hälfte der minimalen Anzahl von Kanten in einer Rechenschaltung für A ist, von fanin höchstens 2 und width n, wobei wir keine Kanten berechnen, die in die Gates von fanin 1 führen. (Ich verwende hier den üblichen Begriff der Schaltkreisbreite.) Dies kann mit der einfachen Idee gezeigt werden, die zuvor skizziert wurde.

Hier ist der Zusammenhang zu gut untersuchten Problemen: Es ist seit über 30 Jahren ein bekanntes offenes Problem, eine explizite lineare Abbildung Ax (über ein beliebiges endliches Feld) zu zeigen, die eine superlineare Anzahl von Gattern in einer Fanin-2-Schaltung erfordert. Die klassische Referenz ist Valiant, "Graphentheoretische Argumente in geringer Komplexität", und eine aktuelle FTTCS-Umfrage von Lokam ist ebenfalls hilfreich.

In c (A) wird eine zusätzliche Breitenbeschränkung eingeführt, aber da unsere Beschränkung so schwach ist (Breite n), gehe ich nicht davon aus, dass das Problem viel einfacher wird. Aber hey - ich würde gerne als falsch erwiesen werden.

Andy Drucker
quelle
2
Gowers diskutierte in seinem Blog auch die Komplexität der Gaußschen Eliminierung. Ich habe es nicht sorgfältig gelesen (es hat die Form eines langen Dialogs), aber es kann hilfreich sein: gowers.wordpress.com/2009/11/03/…
Andy Drucker
Nur um dies richtig zu verstehen, kommt die Breitenbeschränkung ins Spiel, weil Sie höchstens n Operationen pro Spalte haben und spaltenweise fortfahren können?
Moritz
Ich denke in Zeilenoperationen. Die Einschränkung der Breite n entspricht der Tatsache, dass wir n Zeilen haben, in denen alle unsere Zwischenarbeiten stattfinden würden. Die n Schaltungsgatter in der Tiefe t repräsentieren die Zustände der n Zeilen nach t Anwendungen von Zeilenoperationen. (Vielleicht sagst du dasselbe wie ich)
Andy Drucker
Wenn wir stattdessen zusätzliche 'Hilfsarbeitsraum'-Zeilen in unserer Gauß'schen Elimination zulassen würden, würden wir meiner Meinung nach eine genaue Entsprechung zwischen der Komplexität der Reduktion von A auf die Identität und der linearen Komplexität der Rechenschaltung von Ax (die seitdem im Wesentlichen die Komplexität der Rechenleistung ist) erhalten Multiplikationen helfen nicht, lineare Funktionen über einen konstanten Faktor hinaus zu berechnen.
Andy Drucker
Ja das ist, was ich meinte. Ich stimme auch der zweiten Aussage zu. Ein allgemeiner linearer Schaltkreis kann sozusagen immer dann neue Zeilen erstellen, wenn er möchte :-)
Moritz
9

Es gibt Referenzen, und sie sind ziemlich alt. Ich bin auf sie gestoßen, als ich an kombinatorischen Algorithmen für die Boolesche Matrixmultiplikation gearbeitet habe.

1966 bewiesen Moon und Moser, dass die Inverse einer Matrix über GF (2) berechnet werden muss Θ(n2/lOGn)Logn

JW Moon und L. Moser. Ein Matrixreduktionsproblem. Mathematics of Computation 20 (94): 328–330, 1966.

Der Artikel sollte in JSTOR verfügbar sein.

Ich bin mir ziemlich sicher, dass die Untergrenze nur ein Zählargument ist und keine expliziten Matrizen angegeben wurden, die die Untergrenze erreichen.

Ryan Williams
quelle