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

Computergestützte Simulationen und Optimierungen ermöglichen das Untersuchen von anwendungsnahen Fragestellungen in den Natur- und Ingenieurwissenschaften. Dabei sind der Arbeitsspeicher und die Berechnungszeit oftmals die einschränkenden Ressourcen. In diesem Buch werden Techniken zur Reduzierung des Speicherverbrauchs und des Berechnungsaufwands der auftretenden dünnbesetzten Jacobi-Matrizen erläutert. Das Verringern des Berechnungsaufwands wird als Graphfärbungsproblem modelliert. Neben einem bipartiten Graphmodell für Jacobi-Matrizen mit beliebiger Struktur werden auch spezielle Matrixstrukturen betrachtet. Um diese Probleme zu lösen, werden heuristische und exakte Färbungsalgorithmen vorgestellt. Die Reduktion des Speicherverbrauchs ist entscheidend, wenn vorkonditionierte lineare Gleichungssysteme mit iterativen Verfahren gelöst werden und die Koeffizientenmatrix eine Jacobi-Matrix ist. Hierzu werden Techniken eingeführt, bei denen die Vorkonditionierung nur mit einer Teilmenge der Nichtnullelemente der Jacobi-Matrix durchgeführt wird. Abschließend wird der erfolgreiche Einsatz der vorgestellten Methoden auf unterschiedliche Fragestellungen der Natur- und Ingenieurwissenschaften demonstriert.