Lineal (a portmanteau of “Linear Algebra”, but also the measuring and drawing device “ruler” in German) is a C++23 linear algebra library designed to solve large sparse linear systems arising from PDE discretization on attainable hardware by optimizing runtime and, especially, memory consumption.
Main features:

• Very generic, template-heavy approach in which matrices and vectors are just characterized by a set of members they need to provide (i.e. named requirements in the jargon of the C++ standard).
• Support for matrix-free linear systems for stencil-based problems, which can store a single value per cell (which can be as little as one byte) to minimize memory use.
  Lineal’s generic approach allows the “matrix-free” matrix and vector classes to be used mostly interchangeably with more traditional CSR matrices or dense vectors.
• Supported methods:
  • Conjugate Gradients/BiCGStab,
  • Gauß-Seidel/SOR/SSOR and (damped) Jacobi,
  • MAMGO 🥭: Lineal’s Algebraic Multi-Grid (AMG) preconditioner based on the algorithm used in DUNE ISTL,
  • forward/backward substitution based on a Cholesky/LU decomposition.
  • Focus on Krylov subspace method (CG/BiCGStab) preconditioned using MAMGO 🥭.
• All methods support matrix-free linear systems
  • MAMGO 🥭 can be applied to a matrix-free linear system on the finest level while using CSR matrices and coarse vectors on coarser levels (which is required due to the unstructured nature of the AMG method).
    This drastically reduces memory consumption on the finest level, which (by nature of the AMG method) is the largest level by far, and is a novel approach, to the best of our knowledge.
• The aforementioned components (and most others) provide flexible support for mixed precision to minimize memory use as well as the effect of reduced precision on convergence, facilitated by Lineal’s heavy use of very generic templates.
• Almost all components are fully multithreaded with support for thread pinning
• Many components support explicit SIMD operations using Grex and/or tiling.

Further details about the design of Lineal, as well as an evaluation of various features and comparisons with hypre’s BoomerAMG, DUNE ISTL, and Ginkgo, are presented in Lineal: An Efficient Linear Algebra Library, a paper by Kurt Böhm (the author of this library) and Olaf Ippisch (the research supervisor). While the paper is currently under review, a preprint of this paper is already available on Research Square. The results shown there demonstrate Lineal’s much lower memory consumption compared to the aforementioned libraries, which makes it the only library tested to be able to handle the largest dataset used for the evaluation, as well as its very low runtimes, outperforming the other libraries in all but one case (in which its performance is still very comparable), often by large margins.

Lineal uses the Meson build system and includes a fairly extensive (yet incomplete) set of tests. These can be run by executing meson setup -C <build directory> followed by meson test -C <build directory>. Makefile contains targets for calling meson setup with different optimization and debug settings.

Lineal additionally provides fully-featured CMake build files, including the tests (which use CTest in this version).

Dependencies are handled using Meson subprojects (or FetchContent in the CMake version), which make it possible to use Lineal without installing any packages. The Meson subprojects are managed by Tlaxcaltin and are:

• Thesauros: Many basic components, from data structures to threading utilities to static ranges and many other things.
• Grex: Generic SIMD types and operations. Full vectorization is supported on x86-64 (including a subset of AVX-512) while scalar execution is supported on other platforms.
• ankerl::unordered_dense::{map, set}: A fast dense hash map/set.

The tests require the following additional dependencies:

• options: Compiler options to enable more warnings and optimization settings.
• argparse: Command-line argument parsing for modern C++.
• pcg-cpp: Efficient and high-quality pseudo-random number generation.

Lineal supports Linux, macOS (tested on macOS Tahoe), and Windows (tested on Windows 11, but Windows 10 should also work) when compiled using GCC 14 or later/Clang 17 or later. Both x86-64 (with Linux and Windows) and AArch64 (with Linux and macOS) have been tested, but since no special AArch64 support is implemented, Lineal should work on other architectures as well. Support for other operating systems or compilers (including MSVC) is not planned.

Lineal is licensed under the terms of the Mozilla Public Licence 2.0, which is provided in License.