Elemental is a modern C++ library for distributed-memory dense and sparse-direct linear algebra, conic optimization, and lattice reduction. The library was initially released in Elemental: A new framework for distributed memory dense linear algebra and absorbed, then greatly expanded upon, the functionality from the sparse-direct solver Clique, which was originally released during a project on Parallel Sweeping Preconditioners.
Deprecation notice
Elemental has not been maintained since 2016. But the project was forked by Lawrence Livermore National Lab. The author stopped being interested in volunteering to develop MPI codes and no one has stepped up after three years.
Software consists of teams of people. If you want people to continue developing a project after it ceases to be their personal interest, fund them for it.
The developer is now volunteering time towards high-performance math software for workstations at hodgestar.com.
Documentation
The (now outdated) documentation for Elemental is built using Sphinx and the Read the Docs Theme
Unique features
Elemental supports a wide collection of sequential and distributed-memory functionality, including sequential and distributed-memory support for the datatypes:
float,El::Complex<float>double,El::Complex<double>El::DoubleDouble,El::Complex<El::DoubleDouble>(on top of QD's dd_real)El::QuadDouble,El::Complex<El::QuadDouble>(on top of QD's qd_real)El::Quad,El::Complex<El::Quad>(on top of GCC's __float128)El::BigFloat,El::Complex<El::BigFloat>(on top of MPFR's mpfr_t and MPC's mpc_t)
Linear algebra:
- Dense and sparse-direct (generalized) Least Squares
problems
- Least Squares / Minimum Length
- Tikhonov (and ridge) regression
- Equality-constrained Least Squares
- General (Gauss-Markov) Linear Models
- High-performance pseudospectral computation and visualization
- Aggressive Early Deflation Schur decompositions (currently sequential only)
- Blocked column-pivoted QR via Johnson-Lindenstrauss
- Quadratic-time low-rank Cholesky and LU modifications
- Bunch-Kaufman and Bunch-Parlett for accurate symmetric factorization
- LU and Cholesky with full pivoting
- Column-pivoted QR and interpolative/skeleton decompositions
- Quadratically Weighted Dynamic Halley iteration for the polar decomposition
- Many algorithms for Singular-Value soft-Thresholding (SVT)
- Tall-skinny QR decompositions
- Hermitian matrix functions
- Prototype Spectral Divide and Conquer Schur decomposition and Hermitian EVD
- Sign-based Lyapunov/Ricatti/Sylvester solvers
- Arbitrary-precision distributed SVD (QR and D&C support), (generalized) Hermitian EVPs (QR and D&C support), and Schur decompositions (e.g., via Aggressive Early Deflation)
Convex optimization:
- Dense and sparse Interior Point Methods for
Linear, Quadratic, and Second-Order Cone Programs (Note: Scalability for sparse IPMs will be lacking until more general sparse matrix distributions are introduced into Elemental)
- Basis Pursuit
- Chebyshev Points
- Dantzig selectors
- LASSO / Basis Pursuit Denoising
- Least Absolute Value regression
- Non-negative Least Squares
- Support Vector Machines
- (1D) Total Variation
- Jordan algebras over products of Second-Order Cones
- Various prototype dense Alternating Direction Method of Multipliers routines
- Sparse inverse covariance selection
- Robust Principal Component Analysis
- Prototype alternating direction Non-negative Matrix Factorization
Lattice reduction:
- An extension of Householder-based LLL to real and complex linearly-dependent bases (currently sequential only)
- Generalizations of BKZ 2.0 to complex bases (currently sequential only) incorporating "y-sparse" enumeration
- Integer images/kernels and relation-finding (currently sequential only)
The current development roadmap
Core data structures:
- (1a) Eliminate
DistMultiVecin favor of the newly extendedDistMatrix - (1b) Extend
DistSparseMatrixto support elementwise and blockwise 2D distributions
Linear algebra:
- (2a) Distributed iterative refinement tailored to two right-hand sides [weakly depends on (1a)]
- (2b) Extend black-box iterative refinement to
DistMatrix - (2c) Incorporate iterative refinement into linear solvers via optional control structure [weakly depends upon (2b)]
- (2d) Support for the Fix-Heiberger method for accurate generalized Hermitian-definite EVPs
Convex optimization:
- (3a) Add support for homogeneous self-dual embeddings [weakly depends on (2a)]
- (3b) Enhance sparse scalability via low edge-degree plus low-rank decompositions [depends on (1b); weakly depends on (1a)]
- (3c) Distributed sparse semidefinite programs via chordal decompositions [weakly depends on (3b)]
License
The vast majority of Elemental is distributed under the terms of the New BSD License. Please see the debian/copyright file for an overview of the copyrights and licenses for the files in the library.
The optional external dependency METIS is distributed under the (equally permissive) Apache License, Version 2.0, though ParMETIS can only be used for research purposes (and can be easily disabled). libquadmath is distributed under the terms of the GNU Lesser General Public License, version 2.1 or later, while, QD is distributed under the terms of the LBNL-BSD-License.
Dependencies
Intranodal linear algebra
- BLAS
- LAPACK
- libflame (optional for faster bidiagonal SVDs)
- Elemental is packed with a greatly modified version of the Alternating Minimum Degree (AMD) reordering and unblocked sparse LDL factorization from SuiteSparse (Note: The used portions of SuiteSparse are licensed under the GNU Lesser General Public License, version 2.1 or later)
OpenBLAS is automatically downloaded and installed if no vendor/tuned BLAS/LAPACK is detected.
Intranodal graph partitioning
If ParMETIS is not disabled and cannot be found (including access to internal APIs), then it is automatically downloaded and installed; otherwise, if METIS support is not detected, METIS is downloaded and installed.
Internodal linear algebra
- Parallel MRRR (packaged with Elemental)
- ScaLAPACK (optional for benchmarking)
If ScaLAPACK support is not explicitly disabled, then Elemental looks for a previous installation and, failing that, attempts to automatically download and install the library.
Internodal communication
Auxiliary libraries
-
QD for efficient software analogues of 128-bit and 256-bit floating-point arithmetic (Note: QD is licensed under the LBNL-BSD-License, which is a slight modification of the BSD License)
-
libquadmath for quad-precision support (especially for iterative refinement). (Note: libquadmath is licensed under the GNU Lesser General Public License, version 2.1 or later)
-
MPFR for arbitrary-precision real arithmetic. (Note: MPFR is licensed under the GNU Lesser General Public License, v3 or later)
-
MPC for arbitrary-precision complex arithmetic. (Note: MPC is licensed under the GNU Lesser General Public License, v3 or later)
Python interface
- matplotlib (optional for Python matrix visualization)
- NetworkX (optional for Python graph visualization)
- NumPy
C++ visualization
- Qt5 (optional for visualization from C++)
Build system
Third-party interfaces
In addition to the C++11, C, and Python interfaces included within the project, three external interfaces are currently being externally developed:
-
R-El is an R interface to Elemental developed by Rodrigo Canales and Paolo Bientinesi
-
Elemental.jl is an (in-progress) Julia interface to Elemental being developed by Jake Bolewski, Jiahao Chen, and Andreas Noack.
-
CVXPY is a Python-embedded modeling language for convex optimization problems with an (in-progress) interface to Elemental's distributed Interior Point Methods. This effort is being led by Steven Diamond.
Related open-source projects
Distributed dense linear algebra:
Distributed sparse-direct linear algebra:
Distributed linear algebra Frameworks
Convex optimization
Lattice reduction and number theory