- Vollständige und partielle Berechnung von Jacobi-Matrizen mittels Graphfärbung : Algorithmen und Anwendungen
Lülfesmann, Michael; Bücker, Martin (Thesis advisor)
Göttingen : Cuvillier (2012)
Doktorarbeit
Zugl.: Aachen, Techn. Hochsch., Diss., 2012
Kurzfassung
Simulationen und Optimierungen werden genutzt, um anwendungsnahe Fragestellungen in den Natur- und Ingenieurwissenschaften zu untersuchen. Das Lösen von linearen Gleichungssystemen mit dünnbesetzten Jacobi-Matrizen ist zum Beispiel für das Newton-Verfahren zwingend erforderlich. Speicherverbrauch und Berechnungsaufwand werden durch das Ausnutzen der Dünnbesetztheit dieser Matrizen und die Berechnung einer Teilmenge der Nichtnullelemente verringert. Diese Reduktion ist für die Untersuchung von anwendungsnahen Fragestellungen entscheidend. Das Bestimmen aller Nichtnullelemente einer Jacobi-Matrix wird als vollständige Berechnung bezeichnet. Bei der partiellen Berechnung hingegen wird nur eine Teilmenge der Nichtnullelemente bestimmt. Die Nichtnullelemente werden mit Hilfe des automatischen Differenzierens berechnet. Das Verringern des Berechnungsaufwands wird als Graphfärbungsproblem modelliert. Neben dem bipartiten Graphmodell für Jacobi-Matrizen mit beliebiger Struktur werden auch reguläre kartesische Gitter betrachtet. In dieser Arbeit werden Graphfärbungsalgorithmen sowohl für die vollständige als auch für die partielle Berechnung von Jacobi-Matrizen eingeführt. Für die regulären Gitter sind die Färbungen sogar minimal. Abschließend wird für verschiedene Matrixklassen das Färbungsverfahren, das zur geringsten Farbanzahl führt, gesucht. Zum Lösen 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 automatische Differenzieren werden Jacobi-Matrix-Vektor-Produkte effizient zur Verfügung gestellt, wobei das Speichern der Nichtnullelemente der entsprechenden Jacobi-Matrix nicht erforderlich ist. Der Zugriff auf die Nichtnullelemente ist jedoch notwendig, um den Lösungsprozess mit Hilfe von Standardtechniken der Vorkonditionierung zu beschleunigen. In dieser Arbeit werden die Vorkonditionierer aufgrund einer Teilmenge der Nichtnullelemente bestimmt. Das bipartite Graphmodell wird nicht nur verwendet, um eine Färbung zu berechnen, sondern auch, um das symbolische Faktorisieren für die Vorkonditionierung durchzuführen. Nachdem eine anfängliche Teilmenge von Nichtnullelementen gegeben ist, werden weitere Nichtnullelemente ausgewählt, ohne dass der Berechnungsaufwand und der verfügbare Speicher überschritten werden. Nach der Klassifizierung der Nichtnullelemente werden Auswahlstrategien und entsprechende Algorithmen eingeführt. Sowohl die Färbungsalgorithmen 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 Anforderungen an den Speicher und den Berechnungsaufwand erfolgreich verringert werden.
Einrichtungen
- Fachgruppe Informatik [120000]
- Lehrstuhl für Hochleistungsrechnen (Informatik 12) [123010]