Was ist die Raumkomplexität bei der Berechnung von Eigenwerten?

Ich bin auf der Suche nach einem Übersichtsartikel oder einem Buch, das Ergebnisse über die Raumkomplexität gängiger linearer Algebraoperationen wie Matrixrang, Eigenwertberechnung usw. enthält ist einfacher, Zeitergebnisse zu verfolgen. Ich schätze jeden Hinweis in der Sache.

Vielen Dank.

linear-algebra space-complexity Gil
quelle

Ich vermute, dass die Komplexität immer höchstens linear ist (z. B. für eine Matrix). Interessieren Sie sich für "Gesamtfläche" oder für "Arbeitsfläche"?

O (n m)

$O(nm)$

n \times m

$n\times m$

Yuval Filmus

Ich hätte erwähnen sollen, dass ich am Arbeitsplatz interessiert bin.

Gil

Ich bin sicher, es ist für eine Matrix. Der Grund ist, dass ich zwei nützliche Methoden kenne, um sie zu berechnen, und beide im Raum quadratisch sind. Zuerst wird das charakteristische Polynom (quadratisch) berechnet und die Wurzeln gefunden. Zweitens werden einige Approximationsmethoden verwendet, die alle zum Speichern einer modifizierten Matrix erforderlich sind (ich kann dies jedoch nicht näher erläutern, da ich mich mit numerischer linearer Algebra befasst habe).

O (n^{2})

$\mathcal O(n^2)$

n \times n

$n\times n$

Um auf den Punkt von @Yuval Filmus einzugehen, ist die Raumkomplexität für das jeweilige Berechnungsmodell sehr empfindlich. Da die Ausgabe eine lineare Größe hat, kann man Tricks abspielen, indem man das Ausgabeband als Arbeitsbereich verwendet, es sei denn, das Modell gibt eindeutig ein schreibgeschütztes Ausgabeband an. Um solche Probleme zu vermeiden, wäre ich versucht, als Entscheidungsprobleme eine neue Formulierung zu verwenden (z. B. als Eingabe von drei Matrizen, prüfen Sie, ob die dritte das Produkt der ersten beiden ist). Können Sie das Modell angeben, an das Sie gedacht haben? (Ich kenne auch keine Bücher über Raumkomplexität und habe auch keine nützlichen Umfragen gefunden.)

András Salamon

in Bezug auf @ AndrásSalamon kann eine für mich nützliche Entscheidungsversion also lauten: Ist der k-te Eigenwert in größer als q? für Integer k und rational q. Vielen Dank.

Gil

Antworten:

Die Entscheidungsversionen vieler häufiger Probleme in der linearen Algebra über die ganzen Zahlen (oder Rationalen) befinden sich in der Klasse (siehe Artikel) $\mathsf{DET}$

Gerhard Buntrock, Carsten Damm, Christoph Meinel, Ulrich Hertrampf: Struktur und Bedeutung der Klasse Logspace-MOD. Mathematical Systems Theory 25 (3): 223 & ndash; 237 (1992)

$\mathsf{DET}$ ist in . $\mathsf{DSPACE}(\log^2)$

Die Berechnung der Eigenwerte ist etwas komplizierter:

1) In kann man die Koeffizienten des charakteristischen Polynoms berechnen. $\mathsf{DSPACE}(\log^2)$

2) Dann können Sie den Parallelalgorithmus von Reif und Neff verwenden, um Annäherungen an die Eigenwerte zu berechnen. Der Algorithmus läuft auf einem CREW-PRAM in logarithmischer Zeit mit polynomisch vielen Prozessoren, so dass er mit polylogarithmischem Raum simuliert werden kann. (Es wird nicht ausdrücklich in der Veröffentlichung angegeben, aber ihr PRAM sollte logarithmisch einheitlich sein.) Der verwendete Raum ist in der Größe der Eingabematrix und der Genauigkeit polylogarithmisch . Präzision bedeutet, dass Sie Annäherungen bis zu einem additiven Fehler von . $p$ $p$ $2^{-p}$

Dies ist eine Verkettung von Funktionen, die im polylogarithmischen Raum berechenbar sind. (Ausgabebänder sind nur beschreibbar und nur in einer Richtung.)

C. Andrew Neff, John H. Reif: Ein effizienter Algorithmus für das komplexe Wurzelproblem. J. Complexity 12 (2): 81 & ndash; 115 (1996)

Markus Bläser
quelle

Kürzlich hat Ta-Shma [STOC 2013] gezeigt, dass die spektrale Approximation von Matrizen im Quantenlograum durchgeführt werden kann. Daher erfolgt die spektrale Approximation in DSPACE ( ) mit zufälligen Münzen, und ich glaube, dass dies in mit zufälligen Münzen tatsächlich möglich ist , da es sich nur um eine iterierte Matrixmultiplikation handelt. $log^2$ $NC^2$

Lior Eldar
quelle