[Next]:  Präsentation und Visualisierung von numerischen Simulationen  
 [Up]:  Projektbeschreibungen  
 [Previous]:  Gittergenerierung  
 [Contents]   [Index] 


Lineare Gleichungssysteme

Bearbeiter: F. Grund  

 

Förderung: BMBF

Beschreibung der Forschungsarbeit:

 Bei der numerischen Simulation wissenschaftlicher und technischer Vorg�nge, die mathematisch durch Systeme partieller Differentialgleichungen bzw. durch Systeme von Algebro-Differentialgleichungen beschrieben werden, sind viele lineare Gleichungssysteme mit schwachbesetzten Koeffizientenmatrizen zu l�sen. Die Struktur der linearen Systeme bleibt zusätzlich w�hrend der Simulation erhalten. Lineare Systeme, die bei der Diskretisierung von Algebro-Differentialgleichungen entstehen, haben im allgemeinen Matrizen, die keine Struktureigenschaften besitzen, weshalb mit dem Gaußschen Eliminationsverfahren   gearbeitet wird und Sparse-Matrix-Techniken   verwendet werden. F�r die numerische Stabilit�t ist eine geeignete Pivotreihenfolge zu bestimmen. Im Gegensatz zu den Systemen mit vollbesetzten Matrizen, wo die numerische Komplexit�t der Verfahren immer O(n3) ist, kann bei Systemen mit schwachbesetzten Matrizen durch eine g�nstige Pivotreihenfolge, die auch das Fill-in minimiert, die Komplexit�t dramatisch verringert werden [2]. Hierzu ist in jedem Schritt mit einem heuristischen Verfahren die Pivotspalte zu bestimmen. Es gelang, ein Verfahren zu finden, das statt bisher mit einer quadratischen Komplexit�t nun mit einer linearen Komplexit�t arbeitet. Die Rechenzeit f�r die erste Faktorisierung konnte dadurch entscheidend reduziert werden. Auf einem DEC AlphaServer (Prozessor 21164A mit 400 MHz) wurden die in Tabelle 1 gezeigten CPU-Zeiten (in Sekunden) gefunden [1]. Mit |A| wird die Anzahl der Nichtnullelemente bezeichnet.



 

Matrix n |A| bisher neu

bayer01

57 735 277 774 34.92 2.35
bayer02 13 935 63 679 2.20 0.55
bayer03 6 747 56 196 0.67 0.30
bayer04 20 545 159 082 5.18 1.82
Tabelle 1: CPU-Zeiten f�r erste Faktorisierung

Projektliteratur:

  1.  J. BORCHARDT, K. EHRHARDT, F. GRUND, D. HORN, Parallel modular dynamic process simulation, erscheint in: Scientific Computing in Chemical Engineering II (F. Keil, W. Mackens, H. Voss, J. Werther, Hrsg.), Springer-Verlag Berlin Heidelberg New York.
  2.  F. GRUND, Direct linear solver for vector and parallel computers, erscheint in: VECPAR'98, Springer-Verlag Berlin Heidelberg.


 [Next]:  Präsentation und Visualisierung von numerischen Simulationen  
 [Up]:  Projektbeschreibungen  
 [Previous]:  Gittergenerierung  
 [Contents]   [Index] 

LaTeX typesetting by I. Bremer
7/30/1999