SIFEL kernel

Program's name: SIFEL kernel
Available version(s):

SIFEL kernel (master)

SIFEL kernel (factorization by math library)

Programming language(s): C++ ·

SIFEL (SImple Finite ELements) is an open source computer finite element (FE) code that has been developing since 2001 at the Department of Mechanics of the Faculty of Civil Engineering of the Czech Technical University in Prague. It is C/C++ code parallelized with MPI. This is the SIFEL kernel, which implement the LDL matrix factorization from a sparse matrix in symmetric skyline format and the computation of the Schur complement matrix.

As the SIFEL application solves mechanical problems using domain decomposition and Schur complement approach, a given problem is transformed into a global linear system

\[K u = f\]

with symmetric positive definite matrix \(K\). Matrix \(K\) is called stiffness matrix, vectors \(u\) and \(f\) represent displacement and forces. After the domain decomposition, the matrix is arranged such that local interior degrees of freedom are in the first block (denoted by \(o\)) and interface degrees of freedom are placed at the end (denoted by \(r\)):

\[K = \begin{pmatrix} K_{oo} & K_{or} \\ K_{ro} & K_{rr} \end{pmatrix}, u = \begin{pmatrix} u_o \\ u_r \end{pmatrix}, f = \begin{pmatrix} f_o \\ f_r \end{pmatrix}.\]

Then the matrix can be decomposed into the following \(LDL^\top\) factors,

\[K = \begin{pmatrix} L_{11} & 0 \\ L_{21} & I \end{pmatrix}\begin{pmatrix} I & 0 \\ 0 & S \end{pmatrix}\begin{pmatrix} L_{11}^\top & L_{21}^\top \\ 0 & I \end{pmatrix},\]

where

\[K_{oo} = L_{11}L_{11}^\top; \quad K_{ro} = L_{21}L_{11}^\top; \quad S=K_{rr} - K_{ro}K_{oo}^{-1}K_{or}.\]

Applying this decomposition, the original linear can be solved by the following Algorithm called Schur complement method.

Schur complement algorithm:

compute local factors and Schur complement: \(L,L^\top,S \gets K\)
modify right hand side (forward substitution): \(L \hat{f} = f\)
solve global problem with dense matrix: \(S u_r = \hat{f}_r\)
use the global solution for the global part of rhs: \(\hat{f}_r = u_r\)
solve local problems (backward substitution) \(L^\top u = \hat{f}\)

In the SIFEL application, the system matrix is stored in the symmetric skyline format, and then the above \(LDL^\top\)matrix factorization is applied. The factorization is implemented manually using straightforward math formulas. It is well-known that such a basic implementation is not optimal and may not be compared to optimized algorithms implemented in math libraries making use of minimal degree reordering and pivoting, such as the Pardiso within the Math Kernel Library (MKL).

How to build

extract data by runing the ‘prepare_data.sh’ script (be aware that extracted data require ~50 GB of memory)
create directory ‘obj’

mkdir obj
set environment - set the appropriate paths into environment variables
- Make sure, you have a C++ compiler installed and properly set
- MPI (tested with OpenMPI 4.1.1 and GCC 10.3.0)
  - PATH: path to mpicxx binary
  - CPATH: path to MPI header file mpi.h
- ‘MKL’ (tested with MLK 2020.0.166)
  - CPATH: path to MKL header file mkl_pardiso.h
  - LIBRARY_PATH: path to MKL libraries
compile by running Makefile

make

Note: if you want to reduce the amount of data and required memory, modify the ‘prepare_data.sh’ script and keep uncommented only a subset of available datasets.

How to execute

set environment variables
- PATH: path to mpiexec binary
- LD_LIBRARY_PATH: path to MKL libraries
run the executable with appropriate data set, for example:

mpiexec -n 36 ./sifel data/scaling

Available datasets and number of processes are:

data/scaling with 16 and 36 MPI ranks,
data/schur with 4 and 16 MPI ranks.

Related reports: SImple Finite Elements (SIFEL) ·