A from-scratch implementation of the ILUT algorithm — incomplete LU factorization with a
dual dropping rule (threshold tau + fill-in cap) — for sparse matrices in CSR format,
parallelized with OpenMP and MPI.
The algorithm follows Y. Saad, Iterative Methods for Sparse Linear Systems (see ILUT.pdf).
ILUT builds an approximate A ≈ L·U factorization that is cheap to compute and store, and is
widely used as a preconditioner to accelerate the convergence of iterative Krylov solvers
(GMRES, BiCGStab) on large sparse linear systems. The threshold tau and the fill-in limit p
trade factorization accuracy against memory and runtime.
| Directory | Language | Parallelism | Notes |
|---|---|---|---|
ILUT_OpenMP/ |
C++ | OpenMP | Shared-memory version. Most loops over a CSR structure are not thread-safe; parallelism is applied to the one loop in SparseMatrix that allows it safely. |
ILUT_MPI/ |
C++ | MPI | Distributed-memory version. |
ILUT_MPI_Python/ |
Python | MPI (mpi4py) | Reference/readable port with custom SparseMatrix / SparseVector classes. |
All versions implement their own sparse storage (SparseVector, SparseMatrix in CSR) rather
than relying on a library — including a bounds-checked operator[] that inserts missing entries on
demand.
cd ILUT_OpenMP
g++ -O2 -fopenmp ILUT_omp.cpp -o ilut_omp
OMP_NUM_THREADS=4 ./ilut_ompcd ILUT_MPI
mpicxx -O2 ILUT_MPI.cpp -o ilut_mpi
mpirun -np 4 ./ilut_mpicd ILUT_MPI_Python
mpirun -np 4 python ILUT.py- Hand-written sparse linear algebra (CSR) in C++ and Python — no external numerics dependency.
- The same numerical algorithm expressed across three parallel programming models (OpenMP, MPI C++, MPI Python).
- Honest treatment of the limits of parallelizing irregular sparse loops.
Course project in high-performance / numerical computing, Faculty of Computational Mathematics and Cybernetics, Lomonosov MSU.