The performance of FORTRAN implementations for preconditioned conjugate gradients on vector computers. (English) Zbl 0608.65021
Der Autor beschäftigt sich mit der Vektorisierung der Konjugierte- Gradienten-Methode mit Vorkonditionierung. Als Zielrechner dienen ihm die Systeme CRAY 1 und CRAY XMP sowie der Rechner CYBER 205. Dabei wird aufgezeigt, wie sich die verschiedenen Architektureigenschaften auf den Entwurf der Algorithmen auswirken.
Zur Bestimmung der Konditionierungsmatrizen wird neben der Diagonalskalierung, auf die nur knapp eingegangen wird, hauptsächlich eine modifizierte unvollständige Cholesky-Zerlegung benutzt. Um bessere Vektorisierung zu erreichen, wird als drittes Verfahren die Cholesky- Zerlegung dahingehend geändert, daß die notwendigen Invertierungen von Teilmatrizen durch Ausgangsglieder der Neumann-Reihe approximiert werden. Es zeigt sich, daß der sich ergebende algorithmische Verlust durch die Gewinne, die sich aus der höheren Vektorisierungsrate ergeben, mehr als kompensiert wird.
Der Autor gibt für alle behandelten Verfahren und alle angesprochenen Rechner theoretische untere Schranken für die Laufzeit an sowie die tatsächlich gemessenen Zeiten für die beiden auf der Cholesky- Zerlegung beruhenden Methoden. Dabei erweisen sich die theoretischen Werte als gute Approximation der tatsächlichen Laufzeiten.
Zur Bestimmung der Konditionierungsmatrizen wird neben der Diagonalskalierung, auf die nur knapp eingegangen wird, hauptsächlich eine modifizierte unvollständige Cholesky-Zerlegung benutzt. Um bessere Vektorisierung zu erreichen, wird als drittes Verfahren die Cholesky- Zerlegung dahingehend geändert, daß die notwendigen Invertierungen von Teilmatrizen durch Ausgangsglieder der Neumann-Reihe approximiert werden. Es zeigt sich, daß der sich ergebende algorithmische Verlust durch die Gewinne, die sich aus der höheren Vektorisierungsrate ergeben, mehr als kompensiert wird.
Der Autor gibt für alle behandelten Verfahren und alle angesprochenen Rechner theoretische untere Schranken für die Laufzeit an sowie die tatsächlich gemessenen Zeiten für die beiden auf der Cholesky- Zerlegung beruhenden Methoden. Dabei erweisen sich die theoretischen Werte als gute Approximation der tatsächlichen Laufzeiten.
Reviewer: F.Hofmann