A multigrid perspective on the parallel full approximation scheme in space and time

From careful observations, scientists derive rules to describe phenomena in nature. These rules are implemented in form of algorithms in order to simulate these phenomena. Nowadays, simulations are a vital element of numerous research fields, which study not only natural phenomena, but also societal or macro-economical systems. For simulations of a certain size and complexity, an adequate amount of computing power is required. Such simulations are found in fields like molecular dynamics or material science, where sometimes billions of atoms need to be simulated to observe emergent structures. Other fields, which employ such simulations, include weather and climate sciences, where the degrees of freedom simply surpass the capacities of a personal computer. For these simulations a high performance computing approach is required. A more complete list of such fields and their current state of research is found in [1]. The task of the mathematician is to study the stability, accuracy, and cost of computation of the numerical methods used in these simulations. In the last decades, the rapid increase of processors per machine created a need for concurrent computation. This resulted in the reformulation of the existing algorithms and development of new algorithms, which in turn also need to be studied. Most of the fields mentioned above model their problems in the form of partial differential equations. For this class of equations many effective parallel methods already exist. Independent of the method chosen, the model of nature has to be transformed into a model that may be processed by a computer. Since computers are only able to process and store a finite number of quantities with a limited precision, the newly transformed model has to represent nature with this finite number of quantities. One way to do so is to decompose the computational domain of the problem into a finite grid. Imagine, for example, a simulation of the wing of an airplane. The computational domain consists of the wing itself and the floating air around it. A system of partial differential equations describes how the pressure, the temperature, and the speed of the air interact with the mechanical forces of the wing at every point in this computational domain. When we decompose this domain, we are only interested in the physical quantities on a finite number of grid points. With, for example, the finite difference scheme, we derive a set of rules from the partial differential equations. These rules describe how the values on [...