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

Computergesttzte Simulationen und Optimierungen ermglichen das Untersuchen von anwendungsnahen Fragestellungen in den Natur- und Ingenieurwissenschaften. Dabei sind der Arbeitsspeicher und die Berechnungszeit oftmals die einschrnkenden Ressourcen. In diesem Buch werden Techniken zur Reduzierung des Speicherverbrauchs und des Berechnungsaufwands der auftretenden dnnbesetzten Jacobi-Matrizen erlutert. Das Verringern des Berechnungsaufwands wird als Graphfrbungsproblem modelliert. Neben einem bipartiten Graphmodell fr Jacobi-Matrizen mit beliebiger Struktur werden auch spezielle Matrixstrukturen betrachtet. Um diese Probleme zu lsen, werden heuristische und exakte Frbungsalgorithmen vorgestellt. Die Reduktion des Speicherverbrauchs ist entscheidend, wenn vorkonditionierte lineare Gleichungssysteme mit iterativen Verfahren gelst werden und die Koeffizientenmatrix eine Jacobi-Matrix ist. Hierzu werden Techniken eingefhrt, bei denen die Vorkonditionierung nur mit einer Teilmenge der Nichtnullelemente der Jacobi-Matrix durchgefhrt wird. Abschlieend wird der erfolgreiche Einsatz der vorgestellten Methoden auf unterschiedliche Fragestellungen der Natur- und Ingenieurwissenschaften demonstriert.

Klappentext

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.