No label defined (Q4254906)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 1313343
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 1313343

      Statements

      0 references
      4 July 1999
      0 references
      verified solution
      0 references
      large sparse matrices
      0 references
      interval arithmetic
      0 references
      Gauß elimination
      0 references
      Rump algorithm
      0 references
      symmetric enclosure
      0 references
      LU-factorization
      0 references
      conjugate gradient methods
      0 references
      preconditioning
      0 references
      numerical examples
      0 references
      condition number
      0 references
      polynomial methods
      0 references
      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.
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references