Cuvillier Verlag

37 Jahre Kompetenz im wissenschaftlichen Publizieren
Internationaler Fachverlag für Wissenschaft und Wirtschaft

Cuvillier Verlag GmbH

De En Es
Full and partial Jacobian computation via graph coloring: Algorithms and applications

Printausgabe
EUR 38,70 EUR 36,77

E-Book
EUR 0,00

Download
PDF (1 MB)

Full and partial Jacobian computation via graph coloring: Algorithms and applications

Michael Lülfesmann (Autor)

Vorschau

Inhaltsverzeichnis, Datei (40 KB)
Leseprobe, Datei (150 KB)

Simulationen und Optimierungen werden genutzt, um anwendungsnahe Fragestel-
lungen in den Natur- und Ingenieurwissenschaften zu untersuchen. Das L¨osen von
linearen Gleichungssystemen mit d¨unnbesetzten Jacobi-Matrizen ist zum Beispiel f¨ur
das Newton-Verfahren zwingend erforderlich. Speicherverbrauch und Berechnungs-
aufwand werden durch das Ausnutzen der D¨unnbesetztheit dieser Matrizen und die
Berechnung einer Teilmenge der Nichtnullelemente verringert. Diese Reduktion ist
f¨ur die Untersuchung von anwendungsnahen Fragestellungen entscheidend.
Das Bestimmen aller Nichtnullelemente einer Jacobi-Matrix wird als vollst¨andige
Berechnung bezeichnet. Bei der partiellen Berechnung hingegen wird nur eine Teil-
menge der Nichtnullelemente bestimmt. Die Nichtnullelemente werden mit Hilfe
des automatischen Differenzierens berechnet. Das Verringern des Berechnungsauf-
wands wird als Graphf¨arbungsproblem modelliert. Neben dem bipartiten Graphmo-
dell f¨ur Jacobi-Matrizen mit beliebiger Struktur werden auch regul¨are kartesische
Gitter betrachtet. In dieser Arbeit werden Graphf¨arbungsalgorithmen sowohl f¨ur die
vollst¨andige als auch f¨ur die partielle Berechnung von Jacobi-Matrizen eingef¨uhrt.
F¨ur die regul¨aren Gitter sind die F¨arbungen sogar minimal. Abschließend wird f¨ur
verschiedene Matrixklassen das F¨arbungsverfahren, das zur geringsten Farbanzahl
f¨uhrt, gesucht.
Zum L¨osen linearer Gleichungssysteme mit Hilfe eines iterativen Verfahrens ist die
Berechnung von (transponierten) Jacobi-Matrix-Vektor-Produkten ausreichend. Eine
explizite Aufstellung der Jacobi-Matrizen ist nicht erforderlich. Durch das automa-
tische Differenzieren werden Jacobi-Matrix-Vektor-Produkte effizient zur Verf¨ugung
gestellt, wobei das Speichern der Nichtnullelemente der entsprechenden Jacobi-Matrix
nicht erforderlich ist. Der Zugriff auf die Nichtnullelemente ist jedoch notwendig, um
den L¨osungsprozess mit Hilfe von Standardtechniken der Vorkonditionierung zu be-
schleunigen. In dieser Arbeit werden die Vorkonditionierer aufgrund einer Teilmenge
der Nichtnullelemente bestimmt. Das bipartite Graphmodell wird nicht nur verwen-
det, um eine F¨arbung zu berechnen, sondern auch, um das symbolische Faktorisieren
f¨ur die Vorkonditionierung durchzuf¨uhren. Nachdem eine anf¨angliche Teilmenge von
Nichtnullelementen gegeben ist, werden weitere Nichtnullelemente ausgew¨ahlt, oh-
ne dass der Berechnungsaufwand und der verf¨ugbare Speicher ¨uberschritten werden.
Nach der Klassifizierung der Nichtnullelemente werden Auswahlstrategien und ent-
sprechende Algorithmen eingef¨uhrt.
Sowohl die F¨arbungsalgorithmen als auch die Kombination von Vorkonditionierung
und partieller Berechnung von Jacobi-Matrizen werden in Anwendungen der Natur-
und Ingenieurwissenschaften angewendet. Dadurch wird gezeigt, dass die Anforde-
rungen an den Speicher und den Berechnungsaufwand erfolgreich verringert werden.

ISBN-13 (Printausgabe) 3954041014
ISBN-13 (Printausgabe) 9783954041015
ISBN-13 (E-Book) 9783736941014
Buchendformat B5
Sprache Englisch
Seitenanzahl 130
Umschlagkaschierung matt
Auflage 1 Aufl.
Band 0
Erscheinungsort Göttingen
Promotionsort Aachen
Erscheinungsdatum 14.05.2012
Allgemeine Einordnung Dissertation
Fachbereiche Informatik
Schlagwörter Dünnbesetzte Jacobi-Matrizen, Partielle Jacobi-Matrix-Berechnung, Graphfärbungsalgorithmen, Automatisches Differenzieren, Bipartite Graphen, Reguläre kartesische Gitter, Einseitige und zweiseitige Graphfärbung, Matrixfreie iterative Gleichungslöser, Vorkonditionierung linearer Gleichungssysteme, Speicher- und Rechenaufwandsoptimierung