Welches Rechenmodell wird zur Analyse der Laufzeit von Matrixmultiplikationsalgorithmen verwendet?

7

Obwohl ich bereits etwas über die asymptotischen Laufzeiten von Matrixmultiplikationsalgorithmen (Strassens Algorithmus und ähnliche Dinge) gelernt habe, habe ich nie einen expliziten und zufriedenstellenden Hinweis auf ein Berechnungsmodell gefunden, mit dem diese Komplexität gemessen wird. Tatsächlich habe ich drei mögliche Antworten gefunden, von denen mir keine als absolut zufriedenstellend erscheint:

  • Wikipedia sagt, dass das hier verwendete Modell die Multitape Turing Machine ist. Dies scheint mir nicht sehr sinnvoll zu sein, da bei der Analyse der Matrixmultiplikation die Skalarmultiplikation eine konstante zeitliche Komplexität haben soll. Dies ist bei Turingmaschinen nicht der Fall.
  • Einige Texte beschreiben die Komplexität nur vage als die Anzahl der verwendeten arithmetischen Operationen. Was genau sind arithmetische Operationen in diesem Zusammenhang? Ich nehme an, dass Addition, Multiplikation und wahrscheinlich Subtraktion. Aber was ist mit Division, Integer Division, Rest usw.? Und was ist mit bitweisen Operationen - wie passen sie in diese Einstellung?
  • Schließlich habe ich kürzlich einen Artikel entdeckt, der die BSS-Maschine als Berechnungsmodell verwendet. Dies erscheint mir jedoch auch etwas seltsam, da es für z. B. ganzzahlige Matrizen für mich wenig sinnvoll ist, Operationen wie z. B. ganzzahlige Division nicht zuzulassen.

Ich wäre jedem dankbar, der mir helfen könnte, diese Dinge zu klären.

042
quelle
Für die Komplexität kümmern wir uns nur um eine Maßnahme: Schritte eines TM. Bei der Algorithmusanalyse ist es unwahrscheinlich, dass Sie etwas genaueres als die "Anzahl der Grundoperationen" erhalten, die in etwa den elementaren ALU- / Speicherzugriffsoperationen in Prozessoren entsprechen. Ich denke, Sie fragen nach einer Algorithmusanalyse, nicht nach einer Problemkomplexität?
Raphael
@Raphael "Für die Komplexität kümmern wir uns nur um eine Maßnahme: Schritte eines TM." Entschuldigung, aber das ist völlig falsch. Zunächst einmal gibt es viele Rechenmodelle, die keine Turing-Maschinen sind: zum Beispiel Schaltungen. Dann erhalten Sie Dinge wie geometrische und beschreibende Komplexität. Auch im Bereich der Turing-Maschinen ist der Raum ein ebenso wichtiges Maß wie die Zeit. Und was für eine Turingmaschine? Deterministische, nichtdeterministische, alternierende und probabilistische Maschinen haben unterschiedliche Ressourcenanforderungen. Der zufällige Zugriff ist wichtig, wenn Sie feinere Klassifizierungen als "Polynomzeit" wünschen.
David Richerby
@ DavidRicherby: Alles wahr. Unsere Aussagen sind kompatibel; Ich hätte meinen Anwendungsbereich klarer machen sollen. "Für die zeitliche Komplexität, wie sie in klassischen Klassen wie P, NP usw. berücksichtigt wird, ist uns wichtig ...".
Raphael
@ Raphael Aber das ist keine Frage zu P, NP usw. Es ist eine Frage zu einem bestimmten Problem. Die Obergrenzen für jedes Problem werden eine Algorithmusanalyse beinhalten, daher denke ich nicht, dass es wirklich möglich ist, die beiden zu teilen. Allerdings scheint die Komplexität von Strassen usw. eher in "arithmetischen Operationen" als in einem Standardmodell der Berechnung ausgedrückt zu werden.
David Richerby
Zu Ihrem zweiten Ansatz (Zählen von arithmetischen Operationen): Sie können einfach die Anzahl jeder Operation (Multiplikation, Addition, bitweise Operationen usw.) separat zählen. Ein Beispiel dafür finden Sie beispielsweise in Sedgewick & Flajolet: Einführung in die Analyse von Algorithmen (dort analysieren sie Quicksort ziemlich genau). Bei der Matrixmultiplikation glaube ich, dass die Anzahl der beteiligten Multiplikationen den Rest dominiert, also zählen Sie das im Wesentlichen.
John_leo

Antworten:

7

Matrixmultiplikationsalgorithmen werden hinsichtlich ihrer arithmetischen Komplexität analysiert . Das Berechnungsmodell besteht aus linearen Programmen mit Anweisungen des Formularseinbc, wo {+,- -,×,÷}}, ein ist eine Variable und b,ckönnen entweder Variablen, Eingaben oder Konstanten sein. Zusätzlich werden bestimmte Variablen als Ausgaben unterschieden . Hier erfahren Sie beispielsweise, wie Sie zwei multiplizieren2×2 Matrizen unter Verwendung des üblichen Algorithmus mit Eingabematrizen einichj,bichj und Ausgabematrix cichj::

x11ein11×b11y11ein12×b21c11x11+y11x12ein11×b12y12ein12×b22c12x12+y12x21ein21×b11y21ein22×b21c21x21+y21x22ein21×b12y22ein22×b22c22x22+y22
Das Komplexitätsmaß ist die Anzahl der Zeilen im Programm.

Für die Matrixmultiplikation kann man für alle Algorithmen eine Normalform beweisen . Jeder Algorithmus kann auf Kosten einer konstanten multiplikativen Zunahme der Komplexität in einen Algorithmus der folgenden Form umgewandelt werden:

  1. Bestimmte lineare Kombinationen αich der Eingabematrix einjk berechnet werden.
  2. Bestimmte lineare Kombinationen βich der Eingabematrix bjk berechnet werden.
  3. γichαich×βich.
  4. Jeder Eintrag in der Ausgabematrix ist eine lineare Kombination von γichs.

Dies ist als bilineare Normalform bekannt . In dem oben gezeigten Matrixmultiplikationsalgorithmusxjk,yjk Funktion als γich, aber in Strassens Algorithmus sind die linearen Kombinationen interessanter; Sie sind dieM.ichist in der Beschreibung von Wikipedia .

Unter Verwendung eines Tensoring-Ansatzes (dh rekursiver Anwendung desselben Algorithmus), ähnlich der asymptotischen Analyse des Strassen-Algorithmus, kann gezeigt werden, dass ein solcher Algorithmus zum Multiplizieren gegeben ist n×n Matrix mit r Produkte (dh r Variablen γich), dann beliebig N.×N. Matrizen können in ihrer Komplexität multipliziert werden Ö(N.Lognr);; daher ist nur die Anzahl der Produkte asymptotisch von Bedeutung. In Straßens Algorithmusn=2 und r=7und so ist die Grenze Ö(N.Log27).

Das Problem, die minimale Anzahl von Produkten zu finden, die zur Berechnung der Matrixmultiplikation benötigt werden, kann so formuliert werden, dass der Rang eines Tensors dritter Ordnung (eine "Matrix" mit drei statt zwei Indizes) ermittelt wird, und dies bildet die Verbindung zur algebraischen Komplexitätstheorie. Weitere Informationen finden Sie in diesem Buch oder in diesen Vorlesungsunterlagen (Fortsetzung hier ).


Es gibt zwei Gründe, warum dieses Modell verwendet wird: Erstens ist es sehr einfach und für Analysen zugänglich. Zweitens ist es eng mit dem allgemeineren RAM-Modell verwandt.

Im RAM-Modell können geradlinige Programme implementiert werden, und die Komplexität in beiden Modellen hängt stark zusammen: Arithmetische Operationen haben in mehreren Varianten des Modells (z. B. dem RAM-Modell mit reellen Zahlen) Stückkosten und sind ansonsten polynomisch miteinander verbunden auf die Größe der Zahlen. Im Fall der modularen Matrixmultiplikation liefert die arithmetische Komplexität daher eine Obergrenze für die Komplexität im RAM-Modell. Im Fall einer ganzzahligen oder rationalen Matrixmultiplikation kann man zeigen, dass bei bilinearen Algorithmen, die aus der Tensorisierung resultieren, die Größe der Zahlen nicht zu stark zunimmt und die arithmetische Komplexität eine Obergrenze für das RAM-Modell bis hin zu logarithmischen Faktoren liefert .

Es könnte a priori der Fall sein, dass eine RAM-Maschine einige Tricks ausführen kann, die das arithmetische Modell nicht kennt. Oft möchten wir jedoch, dass Matrixmultiplikationsalgorithmen für Matrizen über beliebige Felder (oder sogar Ringe) funktionieren, und in diesem Fall sollte ein einheitlicher Algorithmus nur die vom Modell angegebenen arithmetischen Operationen verwenden. Dieses Modell ist also eine Formalisierung "feldunabhängiger" Algorithmen.

Yuval Filmus
quelle
Gibt es ein Turing-Maschinenmodell?
T ....
Es stellt sich heraus, dass Sie keinen brauchen. Normalerweise stellt man die Turing-Maschine vor, um sie einzuführen Gleichmäßigkeit - einen Code, der für alle funktioniertn. Obwohl das von mir beschriebene Modell ungleichmäßig ist, stellt sich heraus, dass Sie sich dem optimalen Exponenten nähern könnenω sogar einheitlich, indem ein guter Algorithmus auf eine Matrixgröße, die viel kleiner als ist, brutal erzwungen wird n.
Yuval Filmus