Was ist die allgemeinste Struktur, in der die Überprüfung von Matrixprodukten in

18

Freivalds hat 1979 gezeigt, dass die Überprüfung von Matrixprodukten über jedes Feld in randomisierter -Zeit durchgeführt werden kann O(n2). Genauer gesagt besteht bei drei Matrizen A, B und C mit Einträgen aus einem Feld F das Problem, zu überprüfen, ob AB = C einen randomisierten O(n2) -Zeitalgorithmus aufweist.

Dies ist interessant, da der schnellste bekannte Algorithmus zum Multiplizieren von Matrizen langsamer als dieser ist. Überprüfen Sie daher, ob AB = C schneller ist als das Berechnen von C.

Ich möchte wissen, was die allgemeinste algebraische Struktur ist, über die die Matrixproduktverifikation noch einen -Zeitalgorithmus (randomisiert) hat. Da der ursprüngliche Algorithmus über alle Felder funktioniert, funktioniert er vermutlich auch über alle integralen Domänen.O(n2)

Die beste Antwort auf diese Frage fand ich in den subkubischen Äquivalenzen zwischen Pfad-, Matrix- und Dreiecksproblemen . Dort heißt es: "Die Überprüfung des Matrixprodukts über Ringe kann in randomisierter Zeit erfolgen [BK95]." ([BK95]: M. Blum und S. Kannan. Entwerfen von Programmen, die ihre Arbeit überprüfen. J. ACM, 42 (1): 269–291, 1995.)O(n2)

Erstens, sind Ringe die allgemeinste Struktur, bei der dieses Problem einen randomisierten Algorithmus hat? Zweitens konnte ich nicht sehen, wie die Ergebnisse von [BK95] einen O ( n 2 ) -Zeitalgorithmus über alle Ringe zeigen. Kann mir jemand erklären, wie das geht?O(n2)O(n2)

Robin Kothari
quelle
Eine blöde Frage: Ist es offensichtlich, dass deterministische Verifikation so schwer wie Multiplikation ist? Was ist, wenn Sie nicht nur A, B und C, sondern auch ein kompaktes Zertifikat erhalten? hilft es irgendetwas?
Jukka Suomela
@Jukka: Ich glaube, der beste deterministische Algorithmus für dieses Problem ist nicht schneller als die Matrixmultiplikation, aber ich weiß nicht, ob es einen Grund gibt, warum dies der Fall sein sollte. Über die zweite Frage, wenn AB nicht gleich C ist, dann gibt es ein kurzes Zertifikat, das funktioniert: die Eingabe von C, das falsch ist, und die entsprechende Zeile von A und Spalte von B.
Robin Kothari

Antworten:

14

Hier ist ein kurzes Argument, warum es über Ringe funktioniert. Bei gegebenen Matrizen , B , C verifizieren wir A B = C, indem wir einen Zufallsbitvektor v auswählen und dann prüfen, ob A B v = C v ist . Dies geht deutlich , wenn A B = C .ABCAB=CvABv=CvAB=C

Angenommen, und A B v = C v . Lassen Sie D = A B - C . D ist eine Nicht-Null-Matrix, für die D v = 0 ist . Wie groß ist die Wahrscheinlichkeit, dass dies eintritt? Sei D [ i ' , j ' ] ein Eintrag ungleich Null. Durch die Annahme, Σ j D [ i ' , j ] v [ j ] = 0ABCABv=CvD=ABCDDv=0D[i,j]jD[i,j]v[j]=0. Mit der Wahrscheinlichkeit , v [ j ' ] = 1 , so haben wir1/2v[j]=1

.D[i,j]+jjD[i,j]v[j]=0

Jeder Ring unter seiner Additionsoperation ist eine additive Gruppe, daher gibt es eine eindeutige Inverse von , dh - D [ i ' , j ' ] . Nun wird die Wahrscheinlichkeit des schlechten Ereignis - D [ i ' , j ' ] = Σ j j ' D [ i ' , j ] v [ j ] ist höchstens 1 / 2D[i,j]D[i,j]D[i,j]=jjD[i,j]v[j]1/2. (Eine Möglichkeit, dies zu sehen, ist das "Prinzip der verzögerten Entscheidungen": Damit die Summe gleich , muss mindestens ein anderes D [ i ' , j ] ungleich Null sein v [ j ] entspricht diesen anderen Einträgen ungleich Null. Auch wenn wir alle diese v [ j ] mit Ausnahme eines davon optimal einstellen , ist die Wahrscheinlichkeit für den letzten Eintrag immer noch gleich 0 oder 1D[i,j]D[i,j]v[j]v[j]01, Aber immer noch nur einen dieser Werte könnte die endgültige Summe gleich machen .) Also mit einer Wahrscheinlichkeit von mindestens 1 / 4 , wir erfolgreich , dass finden D v 0 , wenn D nicht Null ist. (Anmerkung v [ j ] und v [ j ' ] werden unabhängig voneinander für j j ' gewählt .)D[i,j]1/4Dv0Dv[j]v[j]jj

Wie Sie sehen, hängt das obige Argument von der Subtraktion ab. So funktioniert es (zum Beispiel) nicht bei beliebigen kommutativen Semirings. Vielleicht könnten Sie die multiplikativen Eigenschaften der algebraischen Struktur lockern und trotzdem das Ergebnis erhalten?

Ryan Williams
quelle
Nett, danke. Ich sehe Ihren Standpunkt darin, dass es eine Möglichkeit gibt, die Beschränkungen für die multiplikative Struktur zu verringern. Ist das nicht zu meiner Information derselbe Algorithmus wie in der Originalarbeit von Freivalds?
Robin Kothari
Der Algorithmus von Freivalds wählt einen Zufallsvektor mit Komponenten in {-1,1}. Das funktioniert auch Wenn Sie vorsichtiger sind , können Sie die Wahrscheinlichkeit für einen Erfolg erhalten mindestens sein . 1/2
Ryan Williams