,,Yet despite these impressive results, the convergence curves generated by CGS are frequently so erratic that it is hard to imagine that this algorithm can be completely right. We suspect an even better algorithm may be waiting to be discovered.``Das Verfahren ,,bikonjugierter Gradienten`` beruht auf dem nichtsymmetrischen Lanczos-Algorithmus [57][58]. Ähnlich dem CG-Verfahren wurde BiCG zur Lösung nichtsymmetrischer Gleichungssysteme wiederentdeckt [27]. Gemäß der ursprünglichen Idee von Lanczos konstruiert dieser Algorithmus rekursiv zwei Mengen von Vektoren, die wechselseitig bi-orthogonal sind. Die Algorithmus ist eine Bi-Orthogonalisierungsmethode und besitzt keine monotone Konvergenz. Eine besondere Schwierigkeit ist der sogenannte ,,Zusammenbruch`` des Algorithmus, wobei die Lanczos-Rekursion terminiert, ohne daß eine Lösung des Gleichungssystems erreicht wurde. Diese Eigenschaft hat den Algorithmus lange Zeit in Mißkredit gebracht. Jüngste Forschungen [28][29][30][78] deuten aber darauf hin, daß dieses Problem in fast allen Fällen vermieden werden kann.
Lloyd N. Trefethen [71]
Tabelle 5.3: Vergleich der Anzahl arithmetischer Operationen pro Iteration
für verschiedene lineare Gleichungslöser.
Sonneveld [103] machte die Beobachtung, daß
das Vektor-Polynom, das im BiCG-Algorithmus konstruiert wird, symbolisch
quadriert werden kann. Er konnte den Algorithmus so modifizieren,
daß sich ohne wesentlichen Mehraufwand eine
theoretisch doppelt so schnell konvergierende
Vektorsequenz ergibt. Sinngemäß wurde diese Prozedur
(Bi-)Conjugate Gradient Squared-Methode (CGS) getauft.
Sehr bald fand diese Methode Anwendung in der
mikroelektronischen Bauelement-Simulation [16].
Tabelle 5.5: Nicht vorkonditionierte Version des BiCGSTAB-Algorithmus.
In der Terminologie von Gutknecht [38]
wird der BiCG-Algorithmus als Bi-ORTHOMIN (oder BIOMIN) bezeichnet.
Die dazu äquivalenten Algorithmen
Bi-ORTHORES (Biorthogonale Residuen) und Bi-ORTHODIR
(Biorthogonale Richtungsvektoren) können in ähnlicher
Weise wie BiCG quadriert werden, was auf Algorithmen führt,
die dem CGS-Algorithmus äquivalent sind
(Squared-BIORES, Squared-BIODIR).
Im Laufe dieser Arbeit wurden auch Implementationen dieser
Algorithmen vorgenommen [97].
Das Resultat bevorzugt eindeutig CGS,
da er die beste numerische Stabilität besitzt und den
geringsten Aufwand hinsichtlich Speicherplatz
und Anzahl numerischer Operationen pro Iteration erfordert.
Die Konvergenz von BiCG ist in vielen Fällen stark nichtmonoton.
Das manifestiert sich in großen Spitzen des Residuums, die das
Anfangsresiduum überschreiten können. Dabei kommt es zu signifikanten
Rundungsfehlern, die dazu führen, daß BiCG nicht weiter
konvergiert oder sogar divergiert. Durch
das Quadrieren der polynomialen Darstellung des BiCG
wird grob gesprochen auch die Nichtmonotonizität quadratisch
vergrößert. CGS leidet infolgedessen noch stärker als BiCG
an Rundungsproblemen.
Von den Rundungsproblemen des CGS-Algorithmus
ausgehend, konnte van der Vorst [119] eine stabilisierte
Version von BiCG herleiten, die er BiCGSTAB nannte.
Die Residuen, die im Laufe der
Iteration auftreten, sind wesentlich glatter, gleichzeitig
konvergiert der Algorithmus ähnlich schnell wie CGS.
BiCGSTAB ist zur Zeit ,,State-of-the-Art`` der iterativen
Algorithmen für nichtsymmetrische lineare
Gleichungssysteme in der Bauelement-Simulation.
Vor allem bei zweidimensionalen Simulationen des
Durchbruchs von Galliumarsenid-MESFETs mit dem Programm MINIMOS
hat BiCGSTAB seine Überlegenheit gegenüber CGS bewiesen.
Die Entwicklung numerischer Methoden zur Lösung nichtsymmetrischer
linearer Gleichungssysteme ist allerdings sehr dynamisch.
Neuerungen auf diesem Gebiet sind in absehbarer Zeit
sehr wahrscheinlich.
