Kompetenznetzwerk für wissenschaftliches Höchstleistungsrechnen in Bayern


Algorithms and data structures for matrix-free finite element multigrid operators with MPI-parallel sparse multi-vectors


Dr. Denis Davydov
Chair of Applied Mechanics
University of Erlangen-Nürnberg


In recent years there has been a growing interest in using the Finite Element (FE) discretization for problems in quantum mechanics. The FE basis has the following advantages: (i) it is a locally adaptive basis with variational convergence; (ii) it has welldeveloped rigorous error estimates; (iii) a hierarchy of nested functional spaces can be used to formulate multigrid solvers and geometric multigrid (GMG) preconditioners, that are crucial for the computationally efficient solution of source problems and can also improve convergence of direct minimization methods; (iv) MPI parallel implementation of operators within the FEM is achieved by domain decomposition of the mesh and does not require global communication; (v) it can be applied with both periodic and non-periodic boundary conditions; (vi) high order polynomial bases can be efficiently employed using matrix-free sum factorization approaches. Being a real-space method it is also suitable for orbital minimization (OM) approaches which can be combined with localization in real space to achieve linear scaling with respect to the number of unknown vector M in electronic structure calculations. In this case the solution is sought in terms of non-orthogonal orbitals with local support. Note that traditional eigensolver based solution strategies have O(M^3) computational complexity and O(M^2) memory requirement.

Although the FE method have been used with localized orbitals [3], to the best of our knowledge the implementation details of the underlying linear algebra have not been discussed. In the context of finite difference (FD) approach, the authors of [31] address this problem by “packing together several nonoverlapping localized orbitals into a single global array that represents a grid-based function over the whole discretization grid” using graph-coloring algorithm.

In this proposal we aim to further develop algorithms and data structures for multilevel matrix-free finite element operators with MPI-parallel sparse multi-vectors within the deal.II FE library.