Several highly optimized implementations of Finite Difference schemes are discussed. The combination of vectorization and an interleaved data layout, spatial and temporal loop tiling algorithms, loop unrolling, and parameter tuning lead to efficient computational kernels in one to three spatial dimensions, truncation errors of order two to twelve, and isotropic and compact anisotropic stencils. The kernels are implemented on and tuned for several processor architectures like recent Intel Sandy Bridge, Ivy Bridge and AMD Bulldozer CPU cores, all with AVX vector instructions as well as Nvidia Kepler and Fermi and AMD Southern and Northern Islands GPU architectures, as well as some older architectures for comparison. The kernels are either based on a cache aware spatial loop or on time-slicing to compute several time steps at once. Furthermore, vector components can either be independent, grouped in short vectors of SSE, AVX or GPU warp size or in larger virtual vectors with explicit synchronization. The optimal choice of the algorithm and its parameters depend both on the Finite Difference stencil and on the processor architecture.

Current CPU and GPU architectures heavily use data and instruction parallelism at different levels. Floating point operations are organised in vector instructions of increasing vector length. For reasons of performance it is mandatory to use the vector instructions efficiently. Several ways of tuning a model problem finite difference stencil computation are discussed. The combination of vectorisation and an interleaved data layout, cache aware algorithms, loop unrolling, parallelisation and parameter tuning lead to optimised implementations at a level of 90% peak performance of the floating point pipelines on recent Intel Sandy Bridge and AMD Bulldozer CPU cores, both with AVX vector instructions as well as on Nvidia Fermi/ Kepler GPU architectures. Furthermore, we present numbers for parallel multi-core/ multi-processor and multi-GPU configurations. They represent regularly more than an order of speed up compared to a standard implementation. The analysis may also explain deficiencies of automatic vectorisation for linear data layout and serve as a foundation of efficient implementations of more complex expressions.

Numerical schemes for Einstein's vacuum equation of general relativity are developed. The equation in harmonic gauge is discretized in space-time by Galerkin methods. A split into space and time leads to time-stepping schemes for second order wave equations. Finite Element and Discontinuous Galerkin are covered along with local mesh refinement in space-time.

In der vorliegenden Arbeit werden Herausforderungen diskutiert, die sich durch die Verwendung unterschiedlicher Speichermedien, hier in erster Linie Hauptspeicher und Festplatte, beim Lösen von adaptiven finiten Elementen ergeben. Es werden Datenstrukturen auf ihre Eignung für diese konkrete mathematische Problemstellung analysiert und Mittel bereitgestellt, welche ohne viel Aktualisierungsaufwand die Arbeit mit den benötigten Daten ermöglichen. Der eigentliche Rechenablauf wird dahingehend angepasst, dass der Datenaustausch zwischen Hauptspeicher und Festplatte, der einen (Performance-)Engpass darstellt, so stark wie möglich eingeschränkt wird.

Numerical schemes for the vacuum Einstein equations are developed. The Einstein equation in harmonic gauge is second order symmetric hyperbolic. It is discretized in four-dimensional spacetime by Finite Differences, Finite Elements, and Interior Penalty Discontinuous Galerkin methods, the latter related to Regge calculus. The schemes are split into space and time and new time-stepping schemes for wave equations are derived. The methods are evaluated for linear and non-linear test problems of the Apples-with-Apples collection.

High performance computers offer lots of parallelism at different levels of vectorization, thread parallelism, message-passing between distributed memory architectures and even function off-loading by hardware accelerators. Large scale numerical simulations often have lots of parallelism, which may be difficult to express in a high level programming language. A common abstract parallel programming style is proposed, which can be translated automatically into parallel code for one or a combination of common programming styles for different parallel architectures.

This diploma thesis is about solving the Navier-Stokes equations numerically and emphases parallelizing on GPUs. The work has shown that the computation of the Navier-Stokes equations can be accelerated significantly by using GPUs. The speedup factor is at least 20 which has been shown by the simulations. It is the result of parallelizing the SOR-method which is used to solve the discretization of the poisson pressure equation.

In dieser Arbeit wurde zunächst ein Krylov-Unterraum-Verfahren zur Lösung linearer algebraischer Gleichungssysteme für spezielle dünnbesetzte Matrizen (hier als 27-Diagonal-Matrizen bezeichnet) implementiert. Solche Matrizen erhält man insbesondere bei der Diskretisierung von RWA. Durch die Auslagerung großer Teile des Programms auf die vielen parallel arbeitenden Prozessoren einer Grafikkarte konnte bereits eine beachtliche Rechenleistung erzielt werden. Danach wurde durch das Implementieren und Testen von einigen Varianten der Gebietszerlegungs- und Mehrgitterverfahren eine Beschleunigung des Lösers erreicht. Es ist zu erwarten, dass bei einer weiterentwickelten Grafikkarte eine noch stärkere Beschleunigung erreicht werden kann, weil dann vermutlich größere Teilgebiete in den Vorkonditionierern verwendt werden können. Abschließend wurde die theoretische Grundlage gebildet, um das entwickelte Programm zur Lösung einer nichtlinearen RWA aus der Astrophysik anzuwenden.

Ziel der vorliegenden Arbeit ist die Überprüfung der Vor- und Nachteile von Spektralmethoden. In der Praxis werden häufig Finite-Elemente-Methoden genutzt, die stückweise lineare Funktionen verwenden. Der Vorteil daran liegt auf der Hand. Die Steifigkeitsmatrix ist dünnbesetzt und kann somit schnell gelöst werden. In der vorliegenden Arbeit wird eine partielle Differentialgleichung auf einem gegebenen Gebiet mit Dirichlet- oder Cauchy-Randbedingungen numerisch mittels Spektralmethoden gelöst. Die Umsetzung erfolgt in der Programmiersprache C/C++. Im Mittelpunkt stehen die Möglichkeiten den Zeit- und Rechenaufwand zu optimieren. Dafür werden verschiedene Ansätze miteinander zu verglichen. Dies können neben Gebietszerlegungsmethoden auch verschiedene Vorkonditionierer für die jeweiligen Teilprobleme sein.

There are several parallel programming models available for numerical computations at different levels of expressibility and ease of use. For the development of new domain specific programming models, a splitting into a distributed data container and parallel data iterators is proposed. Data distribution is implemented in application specific libraries. Data iterators are directly analysed and compiled automatically into parallel code. Target architectures of the source-to-source translation include shared (pthreads, Cell SPE), distributed memory (MPI) and hybrid programming styles. A model applications for grid based hierarchical numerical methods and an auto-parallelizing compiler are introduced.

Diese Arbeit befaßt sich mit der Berechnung von Wechselwirkungen zwischen geladenen Partikeln nach dem Coulombschen Gesetz. Werden die Kräfte für jedes Partikel einzeln berechnet, führt dies zu einem Algorithmus der Ordnung O(N²). Dies ist in der Praxis für große Partikelzahlen nicht praktikabel, wenn nicht sogar ummöglich, zu berechnen. Deshalb befassen sich vieleWissenschaftler mit Algorithmen, die diese Berechnungen vereinfachen und stark beschleunigen. Im Wesentlichen baut diese Arbeit auf den Artikeln von L. Greengard, V. Rohklin, R. Beatson und J. Carrier. Sie entwickelten die Schnelle Multipol-Methode, einen Algorithmus, der die Ordnung O(N log N) besitzt. Dadurch ist es möglich, auch für eine sehr große Partikelanzahl die Wechelwirkungen zu berechnen. Ziel der Diplomarbeit war die Umsetzung des Multipol-Algorithmus in JAVA, wobei hier besonders großer Wert auf die Parallelisierung mit Hilfe von Threads gelegt wurde.

Particle models play an important role in many applications in physics, chemistry and biology. These can be studied on the computer with the help of molecular dynamics simulations. This book presents in detail the necessary numerical methods, the theoretical background and foundations and the techniques involved, including linked-cell method, SPME-method, tree codes, amd multipol technique. It illustrates such aspects as modeling, discretization, algorithms and their parallel implementation with MPI on computer systems with distributed memory. The text goes on to offer detailed explanations of the different steps of numerical simulation, providing illustrative code examples. With the description of the algorithms and the presentation of the results of various simulations from fields such as material science, nanotechnology, biochemistry and astrophysics, the reader of this book will learn step by step how to write programs capable of running successful experiments for molecular dynamics.

Data dependence analysis for automatic parallelization of sequential tree codes is discussed. Hierarchical numerical algorithms often use tree data structures for unbalanced, adaptively and dynamically created trees. Moreover, such codes often do not follow a strict divide and conquer concept, but introduce some geometric neighborhood data dependence in addition to parent-children dependencies. Hence, recognition mechanisms and hierarchical partition strategies of trees are not sufficient for automatic parallelization. Generic tree traversal operators are proposed as a domain specific language. Additional geometric data dependence can be specified by code annotation. A code transformation system with data dependence analysis is implemented, which generates several versions of parallel codes for different programming models.

Die vorliegende Arbeit befasst sich mit der numerischen Evaluierung von zweidimensionalen Finanzderivaten. Dafür werden zunächst partielle Differentialgleichungen vorgestellt, die die Entwicklung dieser Derivate beschreiben. Zur Diskretisierung der Differentialgleichungen wird eine finite Volumen Methode verwendet. Im Laufe der Arbeit werden an dem Verfahren einige Modifikationen vorgenommen. Zunächst wird auf Konvektionsdominanz eingegangen. Um stabile Verfahren mit hoher Konvergenz zu erhalten, werden zwei flux-Limiter vorgestellt: Der van Leer und van Albada Limiter. Da es sich bei beiden Limitern um TVD-Schemata handelt und diese höchstens lineare Konvergenz erreichen, werden modifizierte Limiter-Schemata entwickelt, eine Kombination aus zentralen Differenzen und flux- Limitern. Eine weitere Veränderung des Verfahrens besteht in der Gittermodifikation. Gradierte Gitter erlauben eine gezielte lokale Verfeinerung bei gleich bleibender Anzahl an Diskretisierungspunkten. Dünne Gitter verfolgen einen Ansatz mit hierarchischen Basen und erlauben eine Berechnung mit wesentlich weniger Speicheraufwand, aber einer nur in geringem Maße schlechteren Fehlerentwicklung. Ein Nachteil dünner Gitter besteht in recht komplizierten Strukturen, die durch die hierarchischen Basen entstehen. Eine Alternative ist die Kombinationstechnik, die das Gesamtproblem in mehrere Teilprobleme zerlegt, welche wiederum mit bekannten Verfahren gelöst werden können. Die Entwicklung des Fehlers ist äquivalent zu dem auf dünnen Gittern.

The data parallel programming language construct of a “foreach” loop is proposed in the context of hierarchically nested arrays and unbalanced k-ary trees used in high performance applications. In order perform an initial evaluation, an implementation of an automatic parallelization system for C++ programs is introduced, which consists of a preprocessor and a matching library for distributed memory, shared memory and mixed model parallelism. For a full compile time dependence analysis and a tight distributed memory parallelization, some additional application knowledge about alignment of arrays or indirect data access can be put into the application's code data declarations. Results for a multigrid and a fast multipole benchmark code illustrate the concept.

Für europäische und amerikanische Optionen sowie für zwei- und dreidimensionale Basket- Optionen wird aus den Black-Scholes-Gleichungen der faire Preis numerisch berechnet. Da in den meisten Fällen keine geschlossenen Lösungsformeln exisiteren, müssen die multivariaten parabolischen Optionspreisaufgaben numerisch gelöst werden. Die Eindeutigkeit der Gleichungen wird über die Anfangs- und Randwertprobleme garantiert. Das Berechnen von Näherungslösungen für diese Differentialgleichungen geschieht dann durch Diskretisierung der Gleichungen und durch das Lösen der daraus resultierenden Gleichungssysteme. Die Diskretisierung der parabolischen Gleichungen erfolgt mit Finiten Differenzen auf stark anisotropen, regulären und rechtwinkligen Vollgittern. Bei amerikanischen Optionen wird das Hindernisproblem über das Projektions-Successive-Overrelaxation-Iterationsverfahren numerisch gelöst. Die Basket-Optionen beruhen auf Advektions-Diffusions-Reaktions-Gleichungen. Um den numerischen Aufwand vertretbar zu halten, wird die Kombinationstechnik basierend auf der Dünngitter-Theorie eingesetzt. Der numerische Aufwand bei steigender Problemdimension kann dabei substantiell reduziert werden, ohne den Informationsgehalt der Lösung wesentlich zu verschlechtern. Damit kann entscheidend dem “Fluch der Dimensionen“ entgegengewirkt und die Komplexität der Algorithmen verbessert werden. Die unterschiedlichen Lösungen auf den stark anisotropen, regulären, rechtwinkligen und gröberen Dünngittern werden miteinander geeignet linear kombiniert und liefern, bis auf eine logarithmische Dämpfung, denselben numerischen Fehler wie die numerische Lösung auf einem feineren isotropen Referenzvollgitter. Anhand von empirischen Ergebnissen soll die vorgestellte Theorie bestätigt werden.

Das Lehrbuch führt in die wichtigsten Simulationstechniken zur numerischen Behandlung der Newtonschen Bewegungsgleichungen ein. Der Schwerpunkt liegt hierbei auf der schnellen Auswertung kurz- und langreichweitiger Kräfte mittels Linked Cell-, P3M-, Baum- und Multipol-Verfahren sowie deren paralleler Implementierung und Lastbalancierung auf Rechensystemen mit verteiltem Speicher. Die einzelnen Kapitel bieten detaillierte Hinweise, um die Verfahren Schritt für Schritt in ein Programmpaket umzusetzen. Zahlreiche farbige Abbildungen enthalten Simulationsergebnisse für eine Reihe von Anwendungen.

The primary purpose of this report is to collect some information on the CPU-time consumption in a series of typical numerical simulations for solving partial differential equations (PDEs). We would like to establish, through analyzing the CPU-measurements, the performance model for a number of numerical methods when applied in different model problems. All the simulators, i.e. the software programs carrying out the simulations, have been developed using Diffpack which is a generic C++ library based on object-oriented programming techniques. Therefore, the established performance models may offer a rough prediction of real CPU-time consumption by actual Diffpack simulators for practical problems. Additionally, the report can also be regarded as an investigation of the computational efficiency of the current Diffpack implementations. Last but not least, we wish to point out to Diffpack programmers some implementation issues that may affect the performance of the simulators.

Main aspects of the efficient treatment of partial differential equations are discretisation, multilevel/multigrid solution and parallelisation. These distinct topics are covered from the historical background to modern developments. It is demonstrated how the ingredients can be put together to give an adaptive and parallel multilevel approach for the solution of elliptic boundary value problems. Error estimators and adaptive grid refinement techniques for ordinary and for sparse grid discretisations are presented. Different types of additive and multiplicative multilevel solvers are discussed with respect to parallel implementation and application to adaptive refined grids. Efficiency issues are treated both for the sequential multilevel methods and for the parallel version by hash table storage techniques. Finally, space-filling curve enumeration for parallel load balancing and processor cache efficiency are discussed.

The solution of partial differential equations on a parallel computer usually follows the data parallel paradigm. The grid is partitioned and mapped onto the processors. In this paper a parallelisable and cheap method based on space-filling curves is proposed. The partitioning is embedded into the parallel solution algorithm using multilevel iterative solvers and adaptive grid refinement. Numerical experiments on two massively parallel computers prove the efficiency of this approach.

The solution of partial differential equations on a parallel computer is usually done by a data parallel approach. The grid is partitioned and mapped onto the processors. However, partitioning of unstructured meshes and adaptively refined meshes in general is an NP-hard problem and heuristics are needed. In this paper a parallelisable and cheap method based on space-filling curves is analysed. Quasi-optimal estimates are derived for partitions of adaptively refined grids.

In this text we propose a space-filling curve enumeration scheme for the load balancing problem. It is based on the principles of self-similarity and scaling invariance. It provides even multilevel locality, i.e. as much locality on each scale as possible. We introduce the space-filling curve schemes and prove some of the properties of the partitions. The scheme is cheap, deterministic, incremental, can be parallelised and provides acceptable partitions. However, even more striking, it seems to be one of the few partitioning methods where quasi-optimal estimates can be shown. We are able to derive sharp estimates both on the partition and on the multilevel algorithms on the partition, which is more than is known about competing graph partitioning load balancing methods so far. Furthermore, we give a survey of the three main aspects of the efficient treatment of PDEs, that is, discretisation, multilevel solution and parallelisation. We will treat the main features of each of the three distinct topics and cover the historical background and modern developments. We demonstrate how all three ingredients can be put together to give an adaptive and parallel multilevel approach for the solution of PDEs. Error estimators and adaptive grid refinement techniques for ordinary and for sparse grid discretisations are presented. Different types of additive and multiplicative multilevel solvers are discussed with respect to parallel implementation and application to adaptive refined grids. Efficiency issues are treated both for the sequential multilevel methods and for the parallel version by hash table storage techniques. Furthermore, space-filling curve enumeration for parallel load balancing and processor cache efficiency are discussed. We will apply the method to elliptic boundary value problems. We are able to derive estimates for the quality of the partitions by space-filling curves and the load balancing of the numerical algorithms on the grids. Even for adaptive grid refinement within certain ranges we are able to prove that the partitions are quasi-optimal, i.e. the cut sizes of the dual graph are only a constant factor away from optimum independent of the mesh size. Hence we obtain asymptotic optimality of the parallel algorithms. This seems to be remarkable in comparison to graph based heuristics, where little is known about the quality. Furthermore we were able to demonstrate the performance of the method on a range of the world's largest parallel computers, namely ASCI Blue Pacific and a prototype Cray T3E (now presumably at NSA), which are each larger than any non-US system. We complement this data by simulations run on Parnass2, which was the first non-US self-made cluster in the list of the world's largest 500 computers (TOP500). We also demonstrate that this cluster is able to outperform many other commercial parallel computers on a per processor base.

The solution of partial differential equations on a parallel computer is usually done by a domain decomposition approach. The mesh is split into several partitions mapped onto the processors. However, partitioning of unstructured meshes and adaptive refined meshes in general is an NP-hard problem and heuristics are used. In this paper space-filling curve based partition methods are analysed and bounds for the quality of the partitions are given. Furthermore estimates for parallel numerical algorithms such as multigrid and wavelet methods on these partitions are derived.

Computer werden immer schneller und leistungsfähiger. Das gilt nicht nur für den Personalcomputer im Büro, sondern auch für die weltweit schnellsten Hochleistungs-Parallellrechner, die heute schon mehr als eine Billion Rechen-Operationen in nur einer Sekunde ausführen können. Insbesondere durch sie hat sich mit dem "Wissenschaftlichen Rechnen" und der "Numerischen Simulation" in den Naturwissenschaften neben dem traditionellen praktischen Weg (Experiment und Beobachtung) und dem theoretischen Ansatz (mathematische Formulierung) ein vielversprechender dritter Weg herausgebildet, um die Wirklichkeit zu beschreiben. In Bonn arbeiten die Spezialisten dieses Fachgebiets in der Abteilung für Wissenschaftliches Rechnen und Numerische Simulation im Institut für Angewandte Mathematik.

In October 1998 the tenth workshop in a series of biannual GAMM seminars on multigrid methods was held. Almost two decades have passed since the first one, and the topics of the seminars provide a good insight into the progress during this period. The series began in the former GDR and is nowadays organised in cooperation with the GAMM-Committees for “Discretization Methods in Solid Mechanics” and “Efficient Numerical Methods for PDEs”. As this was the tenth anniversary of the series, the rather general title was chosen “International GAMM-Workshop on Multigrid Methods”...

In this paper, we give a survey on the three main aspects of the efficient treatment of PDEs, i.e. adaptive discretization, multilevel solution and parallelization. We emphasize the abstract approach of subspace correction schemes and summarize its convergence theory. Then, we give the main features of each of the three distinct topics and treat the historical background and modern developments. Furthermore, we demonstrate how all three ingredients can be put together to give an adaptive and parallel multilevel approach for the solution of elliptic PDEs and especially of linear elasticity problems. We report on numerical experiments for the adaptive parallel multilevel solution of some test problems, namely the Poisson equation and Lamé's equation. Here, we emphasize the parallel efficiency of the adaptive code even for simple test problems with little work to distribute, which is achieved through hash storage techniques and space-filling curves.

In October 1998 the tenth workshop in a series of biannual GAMM seminars on multigrid methods was held. Almost two decades have passed since the first one, and the topics of the seminars provide a good insight into the progress during this period. The series began in the former GDR and is nowadays organised in cooperation with the GAMM-Committees for “Discretization Methods in Solid Mechanics” and “Efficient Numerical Methods for PDEs”. As this was the tenth anniversary of the series, the rather general title was chosen “International GAMM-Workshop on Multigrid Methods”...

In many cases the approximation of solutions to variational problems involving isotropic Sobolev spaces has a complexity which depends exponentially on the dimension. However, if the solutions possess dominating mixed derivatives one can find discretizations to the corresponding variational problems with a lower complexity - sometimes even independent of the dimension. In order to analyse these effects, we relate tensor products of Sobolev spaces with spaces with dominating mixed derivatives. Based on these considerations we construct families of finite dimensional anisotropic approximation spaces which generalize in particular sparse grids. The obtained estimates demonstrate, in which cases a complexity independent or nearly independent of the dimension can be expected. Finally numerical experiments demonstrate the usefulness of the suggested approximation spaces.

Sparse grids are an efficient approximation method for functions, especially in higher dimensions d >=3. Compared to regular, uniform grids of a mesh parameter h, which contain h^-d points in d dimensions, sparse grids require only h^-1|logh|^d-1 points due to a truncated, tensor-product multi-scale basis representation. The purpose of this paper is to survey some activities for the solution of partial differential equations with methods based sparse grid. Furthermore some aspects of sparse grids are discussed such as adaptive grid refinement, parallel computing, a space-time discretization scheme and the structure of a code to implement these methods.

A parallel version of a finite difference discretization of PDEs on sparse grids is proposed. Sparse grids or hyperbolic crosspoints can be used for the efficient representation of solutions of a boundary value problem, especially in high dimensions, because the number of grid points depends only weakly on the dimension. So far only the `combination' technique for regular sparse grids was available on parallel computers. However, the new approach allows for arbitrary, adaptively refined sparse grids. The efficient parallelisation is based on a dynamic load-balancing approach with space-filling curves.

The solution of many problems in science and engineering is based on computational kernels for the numerical treatment of partial differential equations (PDEs) or N-body problems. Traditional solution methods however reduce these to linear algebra or brute force algorithms on structured data sets. Larger and larger simulations require smarter algorithms to be tractable. Hierarchical tree algorithms represent such a class, both for PDEs and for N-body problems. However, their efficient parallelization is not straightforward. Some difficulties can be removed, if one can provide a fast dynamic load-balancing scheme to cope with the tree variations of the unstructured data sets. In this paper we propose a very cheap yet very efficient load-balancing scheme for tree algorithms based on space-filling curves. Furthermore we present the Parnass2 cluster, on which such parallel codes perform extremely well. The cluster consists of SMP PCs and a Myrinet network at Gigabit/s speed configured with full bisection bandwidth. It turns out that it does not only has the obvious price/performance advantage, but also an absolute performance, which is comparable to the latest commercial Cray T3E.

Partial differential equations can be solved efficiently by adaptive multigrid methods on a parallel computer. We report on the concept of hash-table storage techniques to set up such a program. The code requires substantial less amount of memory than implementations based on tree type data structures and is easier to program in the sequential case. The parallelization takes place by a space-filling curve domain decomposition intimately connected to the hash table. The new data structure simplifies the parallelization of the code substantially and introduces a cheap way to solve the load balancing and mapping problem. We report on the main features of the method and give the results of numerical experiments with the new parallel solver on a cluster of 64 Pentium II/400MHz connected by a Myrinet in a fat tree topology.

We report on numerical experiments using adaptive sparse grid discretization techniques for the numerical solution of scalar hyperbolic conservation laws. Sparse grids are an efficient approximation method for functions. Compared to regular, uniform grids of a mesh parameter h contain h^-d points in d dimensions, sparse grids require only h^-1|logh|^d-1 points due to a truncated, tensor-product multi-scale basis representation.
For the treatment of conservation laws two different approaches are taken: First an explicit time-stepping scheme based on central differences is introduced. Sparse grids provide the representation of the solution at each time step and reduce the number of unknowns. Further reductions can be achieved with adaptive grid refinement and coarsening in space. Second, an upwind type sparse grid discretization in d+1 dimensional space-time is constructed. The problem is discretized both in space and in time, storing the solution at all time steps at once, which would be too expensive with regular grids. In order to deal with local features of the solution, adaptivity in space-time is employed. This leads to local grid refinement and local time-steps in a natural way.

We report on a cluster with 96 CPUs (48 Dual-Processor PCs running Linux 2.1.127) at our department, called Parnass2. The computing nodes are connected by a Myrinet, a Gigabit per second switched LAN, and additionally by a Fast-Ethernet. A comparison of different message passing (MPI) libraries for the Myrinet is given. Furthermore, we present the performance results of Parnass2 for some of the parallel codes developed at our department, namely a sparse grid code for PDEs, a particle code for molecular dynamics, a finite difference code for the Navier-Stokes equation, and a parallel adaptive finite element / finite difference multi-grid code. We compare these results with the performance of these codes running on a Cray T3E-1200, a Cray T3E-600, a SGI Origin 200/2000 and Parnass [?], a cluster of SGI O2 workstations.

A parallel version of an adaptive multigrid solver for partial differential equations is considered. The main emphasis is put on the load balancing algorithm to distribute the adaptive grids at runtime. The background and some applications of space-filling curves are discussed, which are later on used as the basic principle of the load-balancing heuristic. A tight integration of space-filling curves as a memory addressing scheme into the numerical algorithm is proposed. Some experiments on a cluster of PCs demonstrates the parallel efficiency and scalability of the approach.

A parallel version of an adaptive multigrid solver for elliptic partial differential equations is described. It operates on a finite difference discretization on quad-tree and oct-tree meshes, which are obtained by adaptive mesh refinement. A fast parallel load balancing strategy for the parallel multigrid equation solver is proposed that is defined by a space-filling Hilbert curve and is applicable to arbitrary shaped domains. Some numerical experiments demonstrate the parallel efficiency and scalability of the approach.

... Domain decomposition and multilevel methods contain a variety of more standard numerical building blocks (linear solvers, matrix assembly, interpolation of fields etc.). Successful software for complicated applications must offer the user a flexible run-time combination of all these different components. The purpose of the present paper is to describe how one can achieve such flexible software. In particular, we present a unified framework for domain decomposition and multilevel methods, and show how this framework can be efficiently implemented in existing software packages for PDEs.
The unified framework about to be presented is in part well known from the analysis of overlapping and non-overlapping methods [M. Dryja O.B. Widlund 1990 ], as well as from theory for overlapping and multilevel schemes [J. Xu 1992]. In this context, the goal of this paper is to extend the known framework to cover even more methods in common use, especially some Schur complement and nonlinear schemes. We will formulate the framework in a novel way that encourages systematic implementation of a wide class of domain decomposition and multilevel methods. Finally, we report on the experiences gathered from a particular implementation in the Diffpack software.

Partial differential equations can be solved efficiently by adaptive multigrid methods on a parallel computer. We report on the concepts of hash-table storage techniques and space-filling curves to set up such a code. The hash-table storage requires substantial less amount of memory and is easier to code than tree data structures used in traditional adaptive multigrid codes, already for the sequential case. The parallelization takes place by a domain decomposition by space filling curves, which are intimately connected to the hash table. The new data structure simplifies the parallel version of the code substantially and introduces a cheap way to solve the load balancing and mapping problem....

Partial differential equations can be solved efficiently by adaptive multigrid methods on a parallel computer. We report on the concept of hash-table storage techniques to set up such a code. The code requires substantial less amount of memory and is easier to code in the sequential case. The parallelization takes place by a space filling curve domain decomposition intimately connected to the hash table. The new data structure simplifies the parallel version of the code substantially way and introduces a cheap way to solve the load balancing and mapping problem.

Sparse grids provide an efficient representation of discrete solutions of PDEs and are mainly based on specific tensor products of one-dimensional hierarchical basis functions. They easily allow for adaptive refinement and compression. We present special finite difference operators on sparse grids that possess nearly the same properties as full grid operators. Using this approach, partial differential equations of second order can be discretized straightforwardly. We report on an adaptive finite difference research code implementing this on sparse grids. It is structured in an object oriented way. It is based on hash storage techniques as a new data structure for sparse grids. Due to the direct access of arbitrary data traditional tree like structures can be avoided. The above techniques are employed for the solution of parabolic problems. We present a simple space-time discretization. Furthermore a time-stepping procedure for the solution of the Navier Stokes equations in 3D is presented. Here we discretize by a projection method and obtain Poisson problems and convection-diffusion problems.

We will report on a cluster of workstations at our department, called Parnass. It is based on different types of MIPS processor workstations and servers, connected by a Myrinet, a Gigabit per second switched LAN, and additionally a Fast Ethernet. We have ported some low level message passing libraries as well as MPI to the Myrinet. A comparison of the performance of various communication libraries on different networks will be presented.

The aim of this paper is to present some advanced techniques for monitoring thermocouples in the field of fire engineering. In a fire test structural elements like columns, beams or slabs, which are insulated by a fire protection material, are subjected to mechanical as well as thermal loadings. Whereas the mechanical loading is constant the mean temperature in the furnace varies - due to oil or gas burners - nearly monotonically as a function of time within 90 minutes between room temperature and 1000 ⁰C. New technical standards as well as research purposes require the monitoring of 30 to 60 thermocouples and more. Although versatile computer based data acquisition systems including necessary signal condition front-ends exist for handling such an amount of data at any required rate, there is a lack in representing these data during the test in their geometrical context, i.e. as a property of the steel surface. The method, which is proposed by the authors, uses some recent developments in computer graphics and numerical mathematics. By this method the monitoring of the thermocouples is understood as a representation of a time-dependent 1-dimensional field, which is based on discrete measured values on a curved surface in 3-D space. For this solution CAD and data visualization tools are under testing, which are originally designed for other purposes. In praxis a geometry file has to be created before the fire test for the structural element under consideration including the information on the position of the thermocouples. This file is used as an appropriate triangulation of the surface of the specimen. The corresponding grid together with the actual temperature readings are the basis for the real time visualization of the temperature field by continuous colors or iso-lines.

The report gives an introduction to the multigrid iterative solvers in Diffpack. It is meant as a tutorial for the use of iterative solvers, preconditioners and nonlinear solvers based on multigrid methods. The first steps towards this efficient equation solvers are guided by a couple of examples and exercises. Since multigrid is a recipe to construct solution algorithms rather than black-box algorithms itself, there is lots of freedom for the user to tailor the actual solver. Reflecting this fact there are lots of possibilities to use the appropriate classes in Diffpack. Hence there is much advice needed not to get started, but also to use the methods efficiently. The exercises are meant to give some experience needed for applications and questions not covered in this introductory report.

The report gives an introduction to the overlapping domain decomposition solvers of Schwarz type in Diffpack. It is meant as a tutorial for the use of iterative solvers, preconditioners and nonlinear solvers based on overlapping Schwarz methods for partial differential equations. Additive Schwarz methods serve as a standard method for solving equation systems on parallel computers. They are also useful for computations on complicated domains constructed from simple domains where efficient equations solvers are available. We provide an introduction to the implementation and use of such methods in Diffpack. The first steps are guided by a couple of examples and exercises. We also want to refer to an accompanied tutorial on multigrid methods in Diffpack, which methods and codes are quite related.

The report gives an introduction to the Schur complement domain decomposition solvers in Diffpack. It is meant as a tutorial for the use of iterative solution methods of equation systems arising in the discretization of partial differential equations. Schur complement iterative solvers are discussed, without and with preconditioners. They are also referred to as iterative sub-structuring methods or non-overlapping domain decomposition methods. Domain decomposition methods are well suited and efficient equation solvers on parallel computers. Schur complement methods are also advantageous if there are abrupt changes in the coefficients of the differential operator due to abrupt changes in material properties. We provide an introduction to the implementation and use of such methods in Diffpack. We cover the basic Schur complement method along with preconditioners of eigen-decomposition, BPS, wire-basket and Neumann-Neumann type (with coarse grid). The first steps are guided by a couple of examples and exercises. We also want to refer to the related tutorials on overlapping domain decomposition [?] and on multigrid [?] methods in Diffpack.

The report is a continuation of an introductory report on the multigrid iterative solvers in Diffpack. We consider the solution of systems of equations as arising in linear elasticity, non-symmetric equations as in convection-diffusion problems, anisotropic operators and bad conditioned equations as for jumping coefficients problems. In the introductory report only the Laplacian and smooth coefficients were treated. The first steps are guided by a couple of examples and exercises.

The report is a continuation of an introductory report on the multigrid iterative solvers in Diffpack. We consider the solution of equation systems arizing in the finite element discretization of partial differential equations on different grids. In the introductory report only uniform partitions of the unit square and unit cube were treated. Now we consider also multigrid for mapped elements, grids generated by the meshing of super elements and unstructured (and non nested) grids. The first steps are guided by a couple of examples and exercises.

The report is a continuation of an introductory report on the multigrid iterative solvers for finite differences in Diffpack. We consider the solution of partial differential equations discretized by finite differences. We consider varying coefficient and anisotropic operators and a variety of strategies for the convection-diffusion equation and the biharmonic equation. In the introductory report only the Laplacian was treated. We also discuss different multigrid restriction and prolongation operators arising in some special multigrid versions. The first steps are guided by a couple of examples.

The report serves as an alternative introductory report on the multigrid iterative solvers in Diffpack using finite differences instead of finite elements covered previously. We consider the solution of elliptic partial differential equations on different domains. We solve the resulting linear equation systems with a multigrid iteration or a Krylov iteration with a multigrid preconditioner. The multigrid restriction and prolongation are also implemented using finite “difference” type stencils. The first steps are guided by a couple of examples and exercises.

An important tool in engineering is the finite element method.... The combination of both methods, the h-p version, supplies the pre-asymptotic exponentially convergent p-version continuously with properly adapted grids. Hence it achieves the superior exponential convergence asymptotically, too, instead of algebraic convergence of its ingredients the h-version and the p-version. Although the first theoretical results claiming these convergence rates are quite classic, the number of codes using the h-p-version of finite elements is still rather limited. Reasons for that are the pure implementational complexity and the details, in conjunction with the rumor of engineers' low precision requirements. But the major reason is the lack of a robust (self-) adaptive control delivering the desired exponential convergence. ...
In the this thesis we present some steps towards an efficient implementation of the theoretically known exponential convergence. As it turns out, an efficient implementation requires additional theoretical considerations, which play a major role there as well. This includes both the fully automatic h-p-version and as a subset the p-version on suitable grids. We present some details concerning our approach implementing an adaptive h-p-version based on an adaptive multilevel h-version code named Kaskade. This software package uses unstructured grids of triangles in two dimensions and tetrahedra in three dimensions.

The h-p-version of finite-elements delivers a sub-exponential convergence in the energy norm. A step towards a full adaptive implementation is taken in the context of unstructured meshes of simplices with variable order p in space. Both assumptions lead to desirable properties of shape functions like symmetry, p-hierarchy and simple coupling of elements.
In a first step it is demonstrated that for standard polynomial vector spaces on simplices not all of these features can be obtained simultaneously. However, this is possible if these spaces are slightly extended or reduced. Thus a new class of polynomial shape functions is derived, which are especially well suited for three dimensional tetrahedra.
The construction is completed by directly minimizing the condition numbers of the arising preconditioned local finite element matrices. The preconditioner is based on two-step domain decomposition techniques using a multigrid solver for the global linear problem p=1 and direct solvers for local higher order problems.
Some numerical results concerning an adaptive (feedback) version of h-p finite elements are presented.

I våre dager er det viktig å profilere seg gjennom Internett. En av de siste nyvinningene i denne forbindelse, er muligheten for å legge inn applikasjoner på Web-sider, som gir mulighet for interaksjon mellom Websiden og publikum. Dette har tidligere vært mulig ved hjelp av CGI, The Common Gateway Interface. Ved hjelp av denne teknologien kan man kjøre script, programmer etc. på Server, det vil si “hos seg selv,” relativi til hvem som har laget Websiden. Ved hjelp av slike verktøy, kan man hente ut informasjon, lage datasett ved hjelp av programmer ol. Den siste nyskapningen er imidlertid Java. Dette er et programeringsspråk spesialdesignet for å ha en dynamisk interaksjon med publikum på Web-sider. I motsetning til CGI, vil et Java program kjøre hos klient, det vil si lokalt hos den som ser på Web-siden. Man er dermed ikke begrenset av at data skal sendes over nettet. Dette gjør det for eksempel mulig å ha mus-interaksjon på Websider. Bakdelen er at man ikke kan ha optimalisert kode, med hensyn på arkitektur, siden koden skal kunne kjøres på mange forskjellige arkitekturer. Koden som kjøres er derfor“halv-kompilert”, slik at den må tolkes endelig av Web-brouseren hos klienten. Dette gjør at hastigheten ikke er svært stor, men absolutt brukbar. ...

A theoretical investigation of the dynamic properties of integrated optical Erbium doped waveguide lasers is presented. It includes the construction of a physical model and of numerical techniques which allow reliable simulations of the dynamical behaviour of the laser signal depending on essential parameters of the laser device and on its external, time-dependent pump radiation. Therefore, a physical theory is developed which describes the propagation of light and its interaction with the active substrate in the laser cavity. This is realized in two steps. First, a fundamental model based on Maxwell's equations and on rate equations for the transitions in the active medium is constructed. Since this turns out to prohibit reliable simulations, it is, in a second step, reformulated via averaging in time and space which suppresses the fluctuations on the fastest time scales but represents them correctly. For this reduced model reliable and efficient simulation techniques using adaptive control schemes are designed and implemented. We apply the linear implicit Euler discretization with extrapolation in time and a multilevel quadrature scheme in space. Finally the model is justified in comparison with experimental observations in four cases of technological relevance.

A set of adaptive algorithms for quadrature on multi-dimensional polyhedral domains is presented. Several kinds of refinement are discussed, covering local improvement of quadrature order and splitting the domain into sub-domains, resulting in isotropic, graded or anisotropic grids. The algorithms are pure local heuristics using no a priori knowledge or tuning parameters. This approach was motivated by results from finite element theory for optimal approximation results. Numerical experiments show the optimality of pure local greedy-like algorithms for singularity-type functions typically occurring in finite element computations.

An important tool in engineering is the finite element method.... The combination of both methods, the h-p version, supplies the pre-asymptotic exponentially convergent p-version continuously with properly adapted grids. Hence it achieves the superior exponential convergence asymptotically, too, instead of algebraic convergence of its ingredients the h-version and the p-version. Although the first theoretical results claiming these convergence rates are quite classic, the number of codes using the h-p-version of finite elements is still rather limited. Reasons for that are the pure implementational complexity and the details, in conjunction with the rumor of engineers' low precision requirements. But the major reason is the lack of a robust (self-) adaptive control delivering the desired exponential convergence. ...
In the this thesis we present some steps towards an efficient implementation of the theoretically known exponential convergence. As it turns out, an efficient implementation requires additional theoretical considerations, which play a major role there as well. This includes both the fully automatic h-p-version and as a subset the p-version on suitable grids. We present some details concerning our approach implementing an adaptive h-p-version based on an adaptive multilevel h-version code named Kaskade. This software package uses unstructured grids of triangles in two dimensions and tetrahedra in three dimensions.

Results from finite-element-calculations are usually visualized by colored surface- and contour-line-plots or polygonal patches or simply displaced lines and grids. In computer graphics however more advanced techniques like texture-mapping and NURBS are well established and there exist efficient algorithms and implementations. We show that these techniques are not only easy to use, but form a very natural and efficient approach for visualization of higher order finite-element's solutions like in p- and h-p-version. Texture-mapping is useful for displaying vector-valued data, too.

Adaptive numerical methods using the h-p-version of finite elements require special kinds of shape functions. Desirable properties of them are symmetry, hierarchy and simple coupling. In a first step it is demonstrated that for standard polynomial vector spaces not all of these features can be obtained simultaneously. However, this is possible if these spaces are extended. Thus a new class of polynomial shape functions is derived, which is well-suited for the p- and h-p-version of finite elements on unstructured simplices. The construction is completed by minimizing the condition numbers of the arising finite element matrices. The new shape functions are compared with standard functions widely used in the literature.

Multilevel Methoden sind die zur Zeit effizientesten Verfahren zur Lösung großer symmetrischer schwachbesetzter linearer Gleichungssysteme, die aus der Diskretisierung selbstadjungierter elliptischer Randwertprobleme mit Finiten-Elementen entstehen. Im folgenden wird die Parallelisierung eines von Bramble, Pasciak und Xu vorgeschlagenen vorkonditionierten Verfahrens der konjugierten Gradienten, eingebettet in ein adaptives Finite-Elemente-Programm wie etwa Kaskade, diskutiert. Dabei müssen zur effizienten Lastverteilung zusätzliche Forderungen an Triangulierungen, Finite-Elemente-Räume und Gittermanipulationsalgorithmen gestellt werden. Es werden Standardverfahren der Lastverteilung mit einem neuen Aufteilungsverfahren, das auf einem statistischen Ansatz beruht, verglichen. Mit einer hier vorgestellten gemischten Strategie der Aufteilung von Gitterpunkten und Dreiecken kann ein Gesamtverfahren von optimaler Ordnung erreicht werden. Die experimentellen Ergebnisse auf einigen Parallelrechnern zeigen eine hohe Übereinstimmung mit einem hergeleiteten Kostenfunktional und eine ideale Parallelisierbarkeit des Verfahrens. Unterschiede zu anderen bekannten Multilevelverfahren werden in den einzelnen Abschnitten herausgestellt.

Multilevel Methoden sind die zur Zeit effizientesten Verfahren zur Lösung großer linearer Gleichungssysteme, die aus der Diskretisierung elliptischer Randwertprobleme entstehen. Der Aufwand, mit Mehrgitterverfahren oder auch mit multilevel vorkonditionierten Verfahren der konjugierten Gradienten (CG) im symmetrisch positiv definiten Fall ein Gleichungssystem bis auf Diskretisierungsgenauigkeit zu lösen, ist unter geeigneten Voraus- setzungen proportional zur Zahl der Unbekannten oder nur um einen logarithmischen Term höher. ...
Die Ausführungsgeschwindigkeit kann durch adaptive Verfeinerungs- techniken, die die Zahl der notwendigen Unbekannten reduzieren, erhöht werden. Dazu existieren vollständige Programmpakete, wie PLTMG [Bank] und Kaskade [Leinen], [Deuflhard, Leinen, Yserentant], die die Ordnung des eingebauten iterativen Lösers durch Gitterverwaltung, Verfeinerung und Gittermanipulation nicht verschlechtern. Die Ordnung des Lösungsverfahrens kann nur durch parallele Ausführung gesenkt werden. In Hinblick auf sehr große lineare Gleichungssysteme, wie sie insbesondere auch durch Randwertprobleme in drei Raumdimensionen entstehen, liegt es nahe, beide Techniken zu verbinden. Bei der Lastverteilung adaptiv, also dynamisch erzeugter Strukturen, können allerdings nicht mehr alle Vorraussetzungen an die Finiten-Elemente-Räume und alle Algorithmen zur Gittermanipulation vom sequentiellen Programm übernommen werden. Existierende Ansätze, wie [Fox & Otto], [Berger & Bokhari] und [Bastian] führen zu Verfahren, deren Ordnung höher als die des iterativen Lösers ist, und nutzen die Multilevel-Struktur der Gitter nicht aus. Ansätze zur Parallelisierung von Standard-Mehrgitterverfahren wie [Briggs, Hart, McCormick & Quinlan] oder von adaptiven Mehrgitterverfahren wie [Mierendorff] können in dieser Form nicht auf adaptive Verfahren angewendet werden, obwohl sie für regulär verfeinerte Gitter optimale Ergebnisse liefern. ...
Wir werden im folgenden Parallelrechner mit verteiltem Speicher und Message-Passing-Kommunikation und Parallelrechner mit gemeinsamem Speicher und Semaphor-Synchronisation verwenden, um ein multilevel- vorkonditioniertes CG-Verfahren so zu implementieren, daß die Eigenschaften des sequentiellen Programms, soweit möglich, erhalten bleiben, und gleichzeitig eine effiziente Parallelisierung erreicht wird.