Moderne numerische Algorithmen für die Lösung Partieller Differenzialgleichungen müssen mit den effizientesten numerischen Methoden wie etwa Mehrgitterverfahren und adaptiver Gitterverfeinerung und damit mit hierarchischen Datenstrukturen arbeiten können. Unglücklicherweise erzeugen -- zumindest in den meisten existierenden Implementierungen -- hierarchische Datenstrukturen, die üblicherweise in Bäumen gespeichert werden, einen nicht zu vernachlässigenden Overhead beim Zugriff auf die gespeicherten Daten. Die im Rahmen dieser Arbeit entwickelte Methodik benutzt, um dieser Zwickmühle -- numerische Effizienz gegen effiziente Implementierung -- zu entkommen, das Konzept der Raumfüllenden Kurven, um Datenstrukturen aufzubauen, die streng linear bearbeitet werden. Tatsächlich werden sogar nur Keller als einzige Datenstruktur benutzt. Deshalb ist der Zugriff auf die benötigten Daten sehr schnell -- sogar schneller als der sonst übliche Zugriff auf nicht-hierarchische Daten, die in Matrizen gespeichert sind -- und es werden insbesondere cache misses deutlich reduziert. Außerdem wird auf diesen Datenstrukturen die Implementierung von Mehrgitterzyklen und Diskretisierungen höherer Ordnung wie auch die Parallelisierung des gesamten Algorithmus recht einfach und natürlich möglich sein.     «

Moderne numerische Algorithmen für die Lösung Partieller Differenzialgleichungen müssen mit den effizientesten numerischen Methoden wie etwa Mehrgitterverfahren und adaptiver Gitterverfeinerung und damit mit hierarchischen Datenstrukturen arbeiten können. Unglücklicherweise erzeugen -- zumindest in den meisten existierenden Implementierungen -- hierarchische Datenstrukturen, die üblicherweise in Bäumen gespeichert werden, einen nicht zu vernachlässigenden Overhead beim Zugriff auf die gespeicher...     »

Nowadays, competitive numerical algorithms for solving partial differential equations have to work with the most efficient numerical methods like multigrid and adaptive grid refinement and thus with hierarchical data structures. Unfortunately, in most implementations, hierarchical data -- typically stored in trees -- cause a non-negligible overhead in data access. To overcome this quandary -- numerical efficiency versus efficient implementation -- our algorithm uses space-filling curves to build up data structures which are processed linearly. In fact, the only kind of data structure used in our implementation are stacks. Thus, data access becomes very fast -- even faster then the common access of non-hierarchical data stored in matrices -- and, in particular, cache misses are reduced considerably. Furthermore, the implementation of multigrid cycles and/or higher order discretizations as well as the parallelization of the whole algorithm becomes very easy and straightforward on these data structures.     «

Nowadays, competitive numerical algorithms for solving partial differential equations have to work with the most efficient numerical methods like multigrid and adaptive grid refinement and thus with hierarchical data structures. Unfortunately, in most implementations, hierarchical data -- typically stored in trees -- cause a non-negligible overhead in data access. To overcome this quandary -- numerical efficiency versus efficient implementation -- our algorithm uses space-filling curves to build...     »