SC²S Colloquium - September, 11, 2008

From Sccswiki
Jump to navigation Jump to search
Date: September 11
Room: 02.07.023
Time: 3 pm, s.t.

15:00 Uhr - Evgeniy Zharovsky: Gebietszerlegungsorientierte Dünngitterverfahren (DA Zwischenvortrag)

Bei der FEM-Diskretisierung partieller Differentialgleichungen muss man feststellen, dass die auf dünnen Gittern assemblierten Matrizen (Massen- und Steifigkeitsmatrix) nicht sehr dünn besetzt sind. Dies stellt ein Problem für iterative Löser dar, da der Aufwand einer naiven Matrix-Vektor-Multiplikation höher als linear ist. Es gibt jedoch Algorithmen, die durch geschicktes Ausnutzen der Struktur des Problems auf lineare Laufzeit kommen.

In dieser Arbeit wird ein neuer algorithmischer Zugang zur Berechnung des Matrix-Vektor-Produkts auf dünnen Gittern untersucht. Als Basis dient die Idee, das Definitionsgebiet zu zerlegen, um ein "divide and conquer"-Schema anzuwenden. Dünne Gitter weisen eine rekursive Struktur auf, die man hierbei ausnutzen kann. Die so entstandenen Algorithmen sind inhärent parallelisierbar. Besonderer Wert wird darauf gelegt, die Ordnung des Aufwands auch bei diesem Zugang niedrig zu halten, um einen Gewinn gegenüber dem "naiven" (direkten) Vorgehen zu erzielen.