Ich bin auf der Suche nach einer guten Übersicht über Algorithmen und Komplexität der linearen Algebra (Operationen wie Rang, Inverse, Eigenwerte, ... für Boolesche, und Ganzzahlen / Rationale Matrizen) mit Schwerpunkt auf Parallelität ( Hierarchie). und Polyzeitalgorithmen. Ich konnte keinen neuen finden. NC
Kennen Sie eine gute aktuelle Umfrage oder ein Buch über die Komplexität der linearen Algebra?
In diesem Buch werden parallele Algorithmen nicht explizit erwähnt, aber Yaps Buch "Grundlegende Probleme der algorithmischen Algebra" ist eine sehr gute Referenz und erörtert die Komplexität vieler linearer Algebra-Fragen. Es gibt ein spezielles Kapitel über lineare Systeme , in dem unter anderem die Zeit / Bit-Komplexität der Determinantenberechnung, Matrixinversion und Hermite-Normalformalgorithmen behandelt werden.
Das Buch befasst sich auch mit der Komplexität der Multiplikation, Grobner-Basen und Gitterreduktionstechniken (wie LLL). Ich kann es nicht genug empfehlen und ich wette, Sie werden darin etwas Wertvolles finden.
quelle