Algorithms and Data Structures for Matrix-Free Finite Element Operators with MPI-Parallel Sparse Multi-Vectors

Davydov D, Kronbichler M (2020)

Publication Type: Journal article

Publication year: 2020

Journal

ACM Transactions on Parallel Computing Association for Computing Machinery (ACM)

Book Volume: 7

Pages Range: 1-30

Issue: 3

DOI: 10.1145/3399736

Abstract

Traditional solution approaches for problems in quantum mechanics scale as O(M3), where M is the number of electrons. Various methods have been proposed to address this issue and obtain a linear scaling O(M). One promising formulation is the direct minimization of energy. Such methods take advantage of physical localization of the solution, allowing users to seek it in terms of non-orthogonal orbitals with local support.


This work proposes a numerically efficient implementation of sparse parallel vectors within the open-source finite element library deal.II. The main algorithmic ingredient is the matrix-free evaluation of the Hamiltonian operator by cell-wise quadrature. Based on an a-priori chosen support for each vector, we develop algorithms and data structures to perform (i) matrix-free sparse matrix multivector products (SpMM), (ii) the projection of an operator onto a sparse sub-space (inner products), and (iii) post-multiplication of a sparse multivector with a square matrix. The node-level performance is analyzed using a roofline model. Our matrix-free implementation of finite element operators with sparse multivectors achieves a performance of 157 GFlop/s on an Intel Cascade Lake processor with 20 cores. Strong and weak scaling results are reported for a representative benchmark problem using quadratic and quartic finite element bases.

Authors with CRIS profile

Denis Davydov Lehrstuhl für Technische Mechanik

Additional Organisation(s)

Graduiertenkolleg 2423 Skalenübergreifende Bruchvorgänge: Integration von Mechanik, Materialwissenschaften, Mathematik, Chemie und Physik

Involved external institutions

Technische Universität München (TUM) DE Germany (DE)

How to cite

APA:

Davydov, D., & Kronbichler, M. (2020). Algorithms and Data Structures for Matrix-Free Finite Element Operators with MPI-Parallel Sparse Multi-Vectors. ACM Transactions on Parallel Computing, 7, 1-30. https://dx.doi.org/10.1145/3399736

MLA:

Davydov, Denis, and Martin Kronbichler. "Algorithms and Data Structures for Matrix-Free Finite Element Operators with MPI-Parallel Sparse Multi-Vectors." ACM Transactions on Parallel Computing 7 (2020): 1-30.

BibTeX: Download