scientific article; zbMATH DE number 48484

From MaRDI portal
Publication:3997367





Gegenstand dieser Arbeit ist ein Algorithmus, oder besser ein Programm, das im Hinblick auf den Speicheraufwand optimal ist, und das die Zeitkomplexität O(nj) in allen Teilen erreicht. Diese Arbeit baut in großen Teilen auf der Idee der hierarchischen Basen auf. Hierarchische Basen dienen nicht nur als Hilfsmittel zur Lösung der Gleichungssysteme, sondern bilden auch die Grundlage des Fehlerschätzers und der Gittersteuerung. Der benutzte Fehlerschätzer wurde zusammen mit \textit{P. Deuflhard} und \textit{H. Yserentant} [IMPACT Comput. Sci. Eng. 1, 3-35 (1989; Zbl 0706.65111)] im Detail hergeleitet, und wird im Abschnitt 2.4 nochmals dargestellt. In Kapitel 2 werden einige mathematische Grundlagen zusammengetragen und der Gesamtalgorithmus unter mathematischen Aspekten entwickelt und diskutiert. Die konkrete Realisierung steht und fällt mit der Datenstruktur, auf der sie aufbaut. Die Datenstruktur ist eng mit der Verwaltung der Gitter verknüpft. Aus Gründen der Flexibilität des Algorithmus soll sich die Lokalität des Problems auch in der Datenstruktur wiederspiegeln. Die Datenstruktur muß es ermöglichen, den iterativen Löser, den Fehlerschätzer und den Gittermanipulationsteil optimal zu realisieren. Eine Datenstruktur, die diesen Kriterien genügt, wird in Abschnitt 3.4 beschrieben. Kapitel 3 beginnt zunächst mit einer groben Beschreibung des Programmes, in der seine wesentlichen Teile und ihr Zusammenspiel erläutert werden. Aufbau und Verwaltung der Gitter werden im Detail beschrieben. Ein Kernstück dieser Arbeit bildet die Komplexitätsanalyse im Abschnitt 3.5. Eine Reihe von Beispielen am Ende des Kapitels zeigt die Funktionsfähigkeit und die Effizienz des Programmes. Der entwickelte Algorithmus eignet sich in natürlicher Weise für Parallelrechner. Diese Aspekte werden in Kapitel 4 untersucht. Man kann den Algorithmus leicht so modifizieren, daß er auch auf Parallelrechnern mit einer nicht zu hohen Zahl von Prozessoren eine nahezu optimale Komplexität erreicht. Zusätzlich zu den schon in Kapitel 3 eingeführten Hilfsmitteln benutzt man dazu eine Gebietszerlegung, die auf graphentheoretischen Argumenten beruht und vom Algorithmus selbst erzeugt wird, sowie die Lokalität der Datenstruktur.











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3997367)