Search

Multigrid solvers face multiple challenges on parallel computers. Two fundamental ones read as follows: Multiplicative solvers issue coarse grid solves which exhibit low concurrency and many multigrid implementations suffer from an expensive coarse grid identification phase plus adaptive mesh refinement overhead. We propose a new additive multigrid variant for spacetrees, that is, meshes as they are constructed from octrees and quadtrees: It is an additive scheme, that is, all multigrid resolution levels are updated concurrently. This ensures a high concurrency level, while the transfer operators between the mesh levels can still be constructed algebraically. The novel flavor of the additive scheme is an augmentation of the solver with an additive, auxiliary damping parameter per grid level per vertex that is in turn constructed through the next coarser level—an idea which utilizes smoothed aggregation principles or the motivation behind AFACx: Per level, we solve an additional equation whose purpose is to damp too aggressive solution updates per vertex which would otherwise, in combination with all the other levels, yield an overcorrection and, eventually, oscillations. This additional equation is constructed additively as well, that is, is once more solved concurrently to all other equations. This yields improved stability, closer to what is seen with multiplicative schemes, while pipelining techniques help us to write down the additive solver with single‐touch semantics for dynamically adaptive meshes.

The accurate assembly of the system matrix is an important step in any code that solves partial differential equations on a mesh. We either explicitly set up a matrix, or we work in a matrix‐free environment where we have to be able to quickly return matrix entries upon demand. Either way, the construction can become costly due to nontrivial material parameters entering the equations, multigrid codes requiring cascades of matrices that depend upon each other, or dynamic adaptive mesh refinement that necessitates the recomputation of matrix entries or the whole equation system throughout the solve. We propose that these constructions can be performed concurrently with the multigrid cycles. Initial geometric matrices and low accuracy integrations kickstart the multigrid iterations, while improved assembly data is fed to the solver as and when it becomes available. The time to solution is improved as we eliminate an expensive preparation phase traditionally delaying the actual computation. We eliminate algorithmic latency. Furthermore, we desynchronize the assembly from the solution process. This anarchic increase in the concurrency level improves the scalability. Assembly routines are notoriously memory‐ and bandwidth‐demanding. As we work with iteratively improving operator accuracies, we finally propose the use of a hierarchical, lossy compression scheme such that the memory footprint is brought down aggressively where the system matrix entries carry little information or are not yet available with high accuracy.

Multigrid algorithms are among the most efficient solvers for elliptic partial differential equations. However, we have to invest into an expensive matrix setup phase before we kick off the actual solve. This assembly effort is non-negligible; particularly if the fine grid stencil integration is laborious. Our manuscript proposes to start multigrid solves with very inaccurate, geometric fine grid stencils which are then updated and improved in parallel to the actual solve. This update can be realised greedily and adaptively. We furthermore propose that any operator update propagates at most one level at a time, which ensures that multiscale information propagation does not hold back the actual solve. The increased asynchronicity, i.e. the laziness improves the runtime without a loss of stability if we make the grid update sequence take into account that multiscale operator information propagates at finite speed.