scientific article; zbMATH DE number 1313343
Die vorliegende Arbeit beschäftigt sich mit polynomial basierter a posteriori Verifikation bei großen linearen Gleichungssystemen mit spärlich besetzten Matrizen beliebiger Bandbreite. Im Anschluß an ein einführendes Kapitel werden zunächst bekannte Verfikationsverfahren für lineare Gleichungssysteme systematisch hergeleitet. Es sind dies das Intervall-Gauß-Verfahren, Matrixzerlegungsverfahren, der Rump-Algorithmus, die Verfahren von Cordes und Lohner sowie Varianten symmetrischer Einschließung. Während die Realisierung des Intervall-Gauß-Verfahrens und der Matrixzerlegungsverfahren auf H-Matrizen beschränkt bleibt, sind sowohl Rump-Algorithmus als auch die Verfahren von Cordes und Lohner für allgemeine Matrizen anwendbar. Letztere benötigen allerdings eine Näherungsinverse, welche explizit berechnet bzw. mittels einer LU-Zerlegung der Systemmatrix implizit bereitgestellt wird. Der Autor kommt zu dem Schluß, daß bislang für große lineare Gleichungssysteme mit Matrizen beliebiger Bandbreite, will man die Klasse der H-Matrizen verlassen, vor dem Hintergrund der begrenzten Ressource Hauptspeicher kein praktikables Verifikationsverfahren existiert, gerade aber die symmetrischen Varianten des Rump-Algorithmus' geeignete Ansätze für eine spärlich realisierbare Verifikation bieten. Aus einem polynomialen Blickwinkel erfolgt in Kapitel 3 dieser Arbeit die Beschreibung verallgemeinerter CG-Verfahren. Es sind dies insbesondere die Verfahren CR, PCG und PPCR2, wobei neben polynomialer Vorkonditionierung auch die Verfahren DIAG, SPAI und AINV betrachtet werden. Die Zusammenführung verallgemeinerter CG-Verfahren und der Verifikation wird in Kapitel 4 vollzogen. Dabei bedeutet die Verwendung von a posteriori Verifikationsmethoden ein Zerfallen des Lösungsprozesses in die Phasen Approximation und Verifikation. Am Beispiel des CR-Verfahrens werden zunächst die Fragestellungen \(\vartriangleright\) Lassen sich mit Hilfe polynomialer Verfahren Näherungsinverse so berechnen, daß diese zur Verifikation eingesetzt werden können? \(\vartriangleright\) Kann die Berechnung der Näherungsinversen spärlich, d.h. ohne Speicherprobleme erfolgen? \(\vartriangleright\) Ist eine Entkopplung von Approximation und Verifikation möglich oder muß eine Erweiterung der Approximationsphase erfolgen? \(\vartriangleright\) Zu welchem Datentransfer kommt es im Verlauf des Lösungsprozesses, d.h. wie gestaltet sich die Phasenschnittstelle? \(\vartriangleright\) Wie groß ist der durch die Verifikation bedingte zusätzliche Aufwand an arithmetischen Operationen? detailliert untersucht. Sowohl theoretisch als auch durch umfangreiche Tests mit praxisrelevanten Gleichungssystemen wird gezeigt, daß die Durchführbarkeit der Verifikationsphase wesentlich von der Konditionszahl der Systemmatrix und der bezüglich der rechten Seite gewichteten Eigenwertverteilung abhängt. Durch die Herleitung eines auf kubischen Splines basierenden Diagnose-Werkzeugs wird jedoch sowohl die nährungsweise Bestimmung der Konditionszahl als auch die Beurteilung der jeweils vorliegenden spektralen Situation ermöglicht. Alternative Möglichkeiten zur spärlichen Berechnung einer Näherungsinversen werden dargestellt bzw. realisiert und getestet. Im folgenden werden die im Zusammenhang mit PCG-Verfahren eingesetzten expliziten Vorkonditionierer DIAG, SPAI und AINV auf ihre Eignung als Näherungsinverse für die Verifikationsphase hin untersucht. Darüberhinaus werden PPCR2-Verfahren betrachtet, wobei die Vorkonditionierung mittels Tschebyschev- bzw. linearen Ausgleichspolynomen erfolgt. Umfangreiche Tests, welche erneut auch mit alternativen Berechnungsverfahren durchgeführt werden, belegen eine verbesserte Anwendbarkeit der Verifikation im Vergleich zum CR-Verfahren ohne Vorkonditionierung. Schließlich wird eine von der Approximationsphase völlig entkoppelte polynomial basierte Verifikationsphase formuliert, welche durch ihre Unabhängigkeit von der spektralen Situation immer realisierbar ist. Im abschließenden Kapitel werden die Ergebnisse der vorliegenden Arbeit nochmals zusammengestellt und die an einigen Stellen angedeutete Verallgemeinerung auf symmetrisch indefinite und nichtsymmetrische lineare Gleichungssysteme diskutiert. Insgesamt kann festgestellt werden, daß durch die in dieser Arbeit vorgestellten Verfahren erstmals eine Verifikation bei großen linearen Gleichungssystemen mit spärlich besetzten Matrizen beliebiger Bandbreite möglich ist.
- scientific article; zbMATH DE number 4115819
- scientific article; zbMATH DE number 176411
- On solution of large systems of linear equations with block-Toeplitz banded matrices
- scientific article; zbMATH DE number 3986524
- Fast verification of solutions for sparse monotone matrix equations
- scientific article; zbMATH DE number 1424515
- scientific article; zbMATH DE number 714516
- Fast verified solutions of linear systems
- scientific article; zbMATH DE number 3850364
- An algorithm for solving certain large scale sparse linear systems
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4254906)