Robust Algebraic Multigrid Methods and Their Parallelization

Since the pioneer works by A. Brandt, S. McCormick, J.W. Ruge, K. Stüben and others at the beginning of the 80`s the Algebraic Multigrid (AMG) methods have been developed to a powerful solver tool for large-scale finite element, finite difference, or finite volume equations. There are at least two typical situations where the AMG methods can be successfully used: The discretization provides no hierarchy of meshes that is typical for commercial finite element packages, or the coarsest grid in a geometrical Multigrid method is too large to be solved efficiently by some standard method that is typical for complex practical applications. In both cases there is a need for efficient and robust AMG methods. It is certainly an unrealistic dream to construct an universal AMG method for all situations arising in practical applications. However, it is possible to develop highly efficient and robust AMG methods for well defined classes of practical important problems. For instance, problems leading to M- matrices are the classical class of problems for which AMG works well. In the presented project, we will develop a general approach to the construction of AMG methods that allow us to build highly efficient and robust AMG methods for special classes of problems such as large-scale systems arising from the discretization of Maxwell`s equations, structural mechanical problems with bad parameters etc. For the problem classes just mentioned, the standard AMG methods will definitely fail in the sense that the rate is bad, or even deteriorates. In order to close the gap between symmetric and positive definite (SPD) M-matrices and general SPD matrices, we proposed the element preconditioning technique that will be further developed in this project too. From a practical point of view, the parallelization of the AMG methods is a very important task because the parallelization is the main source for a further enhancement of the efficiency. The limit is only defined by the number of available processors. We will use our generalized domain decomposition data distribution concept for the parallelization of the AMG methods developed in this project. Last but not least, the AMG software package PEBBLES will be developed to a powerful tool kit that can be used in other research and commercial packages as a part of the solver kernel.

The computer simulation of many practical problems in Mechanics, Electrodynamics, Life Sciences etc are based on mathematical models described by Partial Differential Equations (PDEs) or even systems of PDEs. In general, these PDEs cannot be solved analytically. The numerical treatment of the PDEs by some discretization methods usually leads to large-scale systems of algebraic equations with many thousand or even millions of unknowns. The fast solution of these systems of algebraic equations is the heart of all such simulation systems. The classical geometrical multigrid methods have approved to be very fast for specific classes of problems. They need a sequence of finer and finer grids. In commercial finite element codes this sequence is often not available. Furthermore, many real-life problems are geometrically so complicated that the available computer resources do not allow refining the mesh. In these cases, Algebraic Multigrid (AMG) methods can be very helpful. They start from a given mesh and the corresponding system of algebraic equations, and generate automatically coarser and coarser systems in a pure algebraic way. Thus, the AMG solver is a black box that can replace every other solver in some given codes. This fact makes the AMG solvers very valuable for commercial codes. In the present research project we have developed efficient and robust AMG methods for special classes of problems. The source reconstruction problem in Computational Medicine (arising for instance in the treatment of epilepsy) leads to the solution of anisotropic potential problems with many right-hand sides. Our special parallel AMG solver for this class of problems is now part of the NeuroFEM-PEBBLES code used in medical research and applications. Another important class of problems arises in Computational Electromagnetics (CEM) where special finite element discretization techniques are required. Our contribution is a new AMG solver for the so-called edge finite element discretization of Maxwell`s equations. This solver is now used in many CEM codes. In Computational Fluid Dynamics (CFD), fast solvers for the Navier-Stokes equations are very crucial. We developed new AMG solvers for special mixed finite element equations typically arising in the solution procedure for the Navier-Stokes equations. The Boundary Element Method (BEM) is another discretization technique for certain classes of PDEs transforming the PDEs first into boundary integral equations. This technique has some advantages not only in unbounded computational domains but also in some other situations. The classical BEM produces dense matrices. Here we propose so-called data-sparse AMG solvers and preconditioners which can be used for solving large scale boundary element equations and even coupled finite and boundary element equations in a domain decomposition framework.