Multilevel BDDC solver library (BDDCML)

About the project

The goal of this project is to develop and provide a scalable parallel solver of linear equations for systems originating from the finite element computations. The implementation is based on the (Adaptive) Multilevel BDDC method, while reflecting some recent advancements in the field. Codes are written in Fortran 95 with MPI library. A library is provided, which is supposed to be called from users' applications. The library provides a simple interface callable from Fortran and C.

Some remarkable features of the solver include imlementation of the multilevel version of BDDC [1] with adaptively generated weighted averages on faces on each level [2]. The solver uses a robust face-based selection of corners based on [3], arbitrary number of levels of the multilevel method, or continuity of arithmetic averages among subdomains on all faces and edges. The solver is applicable to nonsymmetric problems [4], it can employ GPUs for acceleration through the MAGMA library [5], and it can be used for repeated solves with changing right-hand sides by recycling of Krylov subspaces [6].

Adaptive-Multilevel BDDC

Balancing Domain Decomposition by Constraints (BDDC) has quickly evolved into a very popular method. However, for very large numbers of subdomain, the coarse problem becomes a large problem to be solved in its own right. In Multilevel BDDC, the coarse problem is solved only approximately by recursive application of BDDC to higher levels.
Adaptive selection of constraints aims at difficult problems. By analysis of the interface between each pair of substructures in the set-up phase, it enriches the coarse space by suitable constraints, which almost optimally reduce the condition number of BDDC.
Their combination, the Adaptive-Multilevel BDDC method, performs the adaptive selection on each level. In this way, it helps to keep the iteration counts low even when using several levels, for which the convergence of the simple Multilevel BDDC method deteriorates.

Contributors

Jakub Šístek (main contributor, Institute of Mathematics of the AS CR)
Bedřich Sousedík (University of Maryland, Baltimore County)
Jan Mandel (University of Colorado Denver)
Martin Hanek (Czech Technical University in Prague)
Marta Čertíková (Czech Technical University in Prague)
Jaroslav Novotný (Czech Technical University in Prague)
Pavel Burda (Czech Technical University in Prague)
Zhang Changgeng (Nankai University)

Support

We greatly acknowledge the support of

Czech Science Foundation (23-06159S, 18-09628S, 14-02067S, 106/08/0403)
Academy of Sciences of the Czech Republic (RVO:67985840, AV0Z10190503)
IT4Innovations national supercomputing centre (several projects providing supercomputing time)
Ministry of Education, Youth and Sports and American Science Information Center (AMVIS-MŠMT LH11004)
National Science Foundation DMS-0713876 and CNS-0719641
European Commission through HPC-Europa2 project
PRACE research infrastructure through DECI projects HIFLY and HIGHERFLY

Part of the work was done while Jakub Šístek was visiting the University of Colorado Denver in 2007 and 2009.

License

The library is distributed under the GNU Lesser General Public License v3.

Download

The most recent version can be tracked and downloaded at Git repository

https://github.com/sistek/bddcml, simply by typing

git clone https://github.com/sistek/bddcml.git bddcml

Alternatively, you can download the source codes of an older version below

version 2.6 - bddcml-2.6.tar.gz (11/2/2019), see main changes.

version 2.5 - bddcml-2.5.tar.gz (8/6/2015), see main changes.
version 2.4 - bddcml-2.4.tar.gz (12/3/2014), see main changes.
version 2.3 - bddcml-2.3.tar.gz (10/10/2013), see main changes.
version 2.2 - bddcml-2.2.tar.gz (26/6/2013), see main changes.
version 2.1 - bddcml-2.1.tar.gz (1/5/2013), see main changes.
version 2.0 - bddcml-2.0.tar.gz (23/8/2012), see main changes.
version 1.3 - bddcml-1.3.tar.gz (13/4/2012)
version 1.2 - bddcml-1.2.tar.gz (8/11/2011)
version 1.1 - bddcml-1.1.tar.gz
version 1.0 - bddcml-1.0.tar.gz

Users' manual

version 2.6 - manual_bddcml-2.6.pdf

version 2.5 - manual_bddcml-2.5.pdf
version 2.4 - manual_bddcml-2.4.pdf
version 2.3 - manual_bddcml-2.3.pdf
version 2.2 - manual_bddcml-2.2.pdf
version 2.1 - manual_bddcml-2.1.pdf
version 2.0 - manual_bddcml-2.0.pdf
version 1.3 - manual_bddcml-1.3.pdf
version 1.2 - manual_bddcml-1.2.pdf
version 1.1 - manual_bddcml-1.1.pdf

Getting help

Users are welcome to contact the main developer at sistek@math.cas.cz.

External software

Apart of standard numerical packages (LAPACK, BLAS), the library relies on the following external packages. See their websites for licensing info.

MUMPS: a MUltifrontal Massively Parallel sparse direct Solver
ParMETIS - Parallel Graph Partitioning and Fill-reducing Matrix Ordering
blopex - parallel preconditioned eigenvalue solvers Matrix Algebra on GPU and Multi-core Architectures (MAGMA) - optional for GPU acceleration

Users

The solver has been incorporated into:

OpenFTL (Open Finite element Template Library) package for finite element computations developed at the Computational Structural Mechanics group at the University of Cambridge

AMDiS adaptive finite element solver developed at TU Dresden

Flow123d solver for subsurface flow developed at TU Liberec

References

If you use the package for research that leads to scientific publications, you can acknowledge this contribution by referring to the following papers.

[1] B. Sousedík, J. Šístek, and J. Mandel. Adaptive-Multilevel BDDC and its parallel implementation. Computing, 95(12):1087-1119, 2013. [paper] [preprint]

[2] J. Mandel, B. Sousedík, and J. Šístek. Adaptive BDDC in three dimensions. Math. Comput. Simulation, 82(10):1812-1831, 2012. [paper] [preprint]

[3] J. Šístek, M. Čertíková, P. Burda, and J. Novotný. Face-based selection of corners in 3D substructuring. Math. Comput. Simulation, 82(10):1799-1811, 2012. [paper] [preprint]

[4] M. Hanek, J. Šístek, and P. Burda. Multilevel BDDC for incompressible Navier-Stokes equations. SIAM Journal on Scientific Computing, 42(6):C359--C383, 2020. [open access paper]

[5] J. Šístek and T. Oberhuber. Acceleration of a parallel BDDC solver by using graphics processing units on subdomains. The International Journal of High Performance Computing Applications, 37(2):151–164, 2023. [paper] [preprint]

[6] M. Hanek, J. Papež, and J. Šístek. Speeding up an unsteady flow simulation by adaptive BDDC and Krylov subspace recycling. Computer Methods in Applied Mechanics and Engineering, 452:118788, 2026. [final version] [preprint]

[1]	B. Sousedík, J. Šístek, and J. Mandel. Adaptive-Multilevel BDDC and its parallel implementation. Computing, 95(12):1087-1119, 2013. [paper] [preprint]
[2]	J. Mandel, B. Sousedík, and J. Šístek. Adaptive BDDC in three dimensions. Math. Comput. Simulation, 82(10):1812-1831, 2012. [paper] [preprint]
[3]	J. Šístek, M. Čertíková, P. Burda, and J. Novotný. Face-based selection of corners in 3D substructuring. Math. Comput. Simulation, 82(10):1799-1811, 2012. [paper] [preprint]
[4]	M. Hanek, J. Šístek, and P. Burda. Multilevel BDDC for incompressible Navier-Stokes equations. SIAM Journal on Scientific Computing, 42(6):C359--C383, 2020. [open access paper]
[5]	J. Šístek and T. Oberhuber. Acceleration of a parallel BDDC solver by using graphics processing units on subdomains. The International Journal of High Performance Computing Applications, 37(2):151–164, 2023. [paper] [preprint]
[6]	M. Hanek, J. Papež, and J. Šístek. Speeding up an unsteady flow simulation by adaptive BDDC and Krylov subspace recycling. Computer Methods in Applied Mechanics and Engineering, 452:118788, 2026. [final version] [preprint]