Prof. Dr. Ulrich Rüde
Computer Science 10 – System simulation (LSS)
Due to their optimal complexity, multigrid methods are among the fastest solvers for linear systems to date. They are employed successfully to solve large problems that arise from the discretization of partial differential equations. Simulation of Earth Mantle convection is an example application, where efficient parallel solvers are required. Resolving the mantle uniformly with a resolution of 1 km results in linear systems with about a trillion (10^12) unknowns. To date, only matrix-free solvers with near-optimal convergence, such as geometric multigrid methods, are capable to handle the corresponding computational task with a still acceptable memory consumption.
While relaxation and inter-grid transfer kernels can be realized very efficiently on modern architectures, the design of a fast coarse grid solver is often the main bottleneck in a massively parallel setting. The system size of the coarse grid problem is usually several magnitudes smaller than on the fine grid. Thus, if no further optimizations are performed, the individual processes only work on a small number of unknowns and the relation of communication to computation becomes extremely unbalanced. Only a careful design of the coarse grid solver that is tailored to the data structures can avoid unnecessary communication and data conversion. Adapting these solvers to the underlying problem can alleviate the natural (and fundamentally unavoidable) bottleneck of multigrid on coarse grids. This is essential to improve the efficiency of these methods on modern supercomputers and help to save precious resources.