h1

h2

h3

h4

h5
h6
http://join2-wiki.gsi.de/foswiki/pub/Main/Artwork/join2_logo100x88.png

Full and partial Jacobian computation via graph coloring : algorithms and applications = Vollständige und partielle Berechnung von Jacobi-Matrizen mittels Graphfärbung : Algorithmen und Anwendungen



VerantwortlichkeitsangabeMichael Lülfesmann

ImpressumGöttingen : Cuvillier 2012

UmfangII, 117 S. : Ill., graph. Darst.

ISBN978-3-95404-101-5


Zugl.: Aachen, Techn. Hochsch., Diss., 2012

Zsfassung in dt. und engl. Sprache


Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter


Tag der mündlichen Prüfung/Habilitation
2012-04-05

Online
URN: urn:nbn:de:hbz:82-opus-41124
URL: https://publications.rwth-aachen.de/record/82817/files/4112.pdf

Einrichtungen

  1. Fachgruppe Informatik (120000)
  2. Lehrstuhl für Informatik 12 (Hochleistungsrechnen) (123010)

Inhaltliche Beschreibung (Schlagwörter)
Graphfärbung (Genormte SW) ; Bipartiter Graph (Genormte SW) ; Kartesisches Gitter (Genormte SW) ; Kombinatorische Optimierung (Genormte SW) ; Funktionalmatrix (Genormte SW) ; Schwach besetzte Matrix (Genormte SW) ; Lineares Gleichungssystem (Genormte SW) ; Präkonditionierung (Genormte SW) ; Unvollständige Dreieckszerlegung (Genormte SW) ; Informatik (frei) ; Jacobische Matrix (frei) ; Jacobi-Matrix (frei) ; Jacobi-Matrizen (frei) ; graph coloring (frei) ; bipartite graph (frei) ; combinatorial optimization (frei) ; sparse Jacobian matrix (frei) ; preconditioners for iterative methods (frei)

Thematische Einordnung (Klassifikation)
DDC: 004
msc: 90C27 * 65F50 * 65F08 * 05C50 * 05C15

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.

Simulations and optimizations are carried out to investigate real-world problems in science and engineering. For instance, solving systems of linear equations with sparse Jacobian matrices is mandatory when using a Newton-type algorithm. The sparsity of Jacobian matrices is exploited and only a subset of the nonzero elements is determined to successfully reduce the usage of the restricting resources - memory and computational effort. This reduction is crucial to investigate real-world problems. The determination of all nonzero elements is denoted as full Jacobian computation, opposed to the partial Jacobian computation where only a subset of the nonzero elements is computed. Reducing the computational effort to determine nonzero elements with automatic differentiation is modeled by graph coloring problems. Beside the bipartite graph model for general Jacobian matrices, regular Cartesian grids are a graph class arising from stencil-based computations. In this thesis, graph coloring algorithms for full and partial Jacobian computation are introduced, for both representations. Furthermore, for regular grids, the presented algorithms even result in minimal colorings. Thereafter, several classes of Jacobian matrices are considered to assess which coloring method should be employed for which class. Iterative solvers for systems of linear equations are matrix-free and require solely access to (transposed) Jacobian matrix-vector products. These products are efficiently provided by automatic differentiation without storing the nonzero elements of the Jacobian matrix. However, when using standard preconditioning techniques to speed up the solution of the linear systems, the access to these nonzero elements is necessary. In this thesis, the preconditioning technique is restricted to a subset of the Jacobian elements which are determined using partial Jacobian computation. The bipartite graph model is employed to determine a coloring but also to carry out the symbolic factorization for the preconditioning. An initial set of nonzero elements is given; further nonzero elements are chosen without exceeding the computational effort and the available memory. A classification for these nonzero elements is introduced. Strategies and algorithms to select these elements are given. Finally, the coloring algorithms as well as the combination of preconditioning and partial Jacobian computation are applied to several applications from science and engineering. It is shown that the demands of memory and computational effort are successfully reduced.

Fulltext:
Download fulltext PDF

Dokumenttyp
Dissertation / PhD Thesis

Format
online, print

Sprache
English

Interne Identnummern
RWTH-CONV-143176
Datensatz-ID: 82817

Beteiligte Länder
Germany

 GO


OpenAccess

QR Code for this record

The record appears in these collections:
Document types > Theses > Ph.D. Theses
Faculty of Mathematics, Computer Science and Natural Sciences (Fac.1) > Department of Computer Science
Publication server / Open Access
Public records
Publications database
120000
123010

 Record created 2013-01-28, last modified 2022-04-22


Fulltext:
Download fulltext PDF
Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)