Distributed-memory, arbitrary-precision, dense and sparse-direct linear algebra, conic optimization, and lattice reduction
C++ Python CMake Objective-C C TeX Other
Permalink
Failed to load latest commit information.
cmake Replacing hardcoded 'lib' by the CMAKE variable in ElVars file Dec 19, 2016
compiler_bugs/MSVC/constexpr Adding missing commit. May 18, 2015
data The MPS reader now appears to work for sequential dense matrices Dec 30, 2016
debian Updating debian changelog to 0.87.4 Nov 23, 2016
examples Fixing several issues with the MPS readers. Several tweaks to the IPM… Jan 4, 2017
experimental/g3d Reorganizing the CMakeLists.txt a bit and attempting to add support f… Feb 19, 2015
external Merge pull request #197 from elemental/SuiteSparse_and_libm Nov 19, 2016
include Added an overloaded operator* for Ranges. Jan 16, 2017
octave Happy New Year Jan 2, 2015
package_example Improving find_package support for Elemental and adding an example of… Jun 5, 2016
python Beginning to add support for an MPS reader Dec 30, 2016
redhat fix the macro properly. Dec 6, 2016
sandbox Fixing clang build; adding a custom integer Pow and a unit test Nov 26, 2016
src Merge branch 'master' of https://github.com/elemental/Elemental Feb 19, 2017
tests Pullying secular fix into master Feb 19, 2017
travis Upgrade to Ubuntu 14.04 Trusty to test with a non-obsolete MPICH Aug 3, 2016
vagrant Simplifying bootstrap vagrant scripts May 10, 2015
.appveyor.yml added half-baked appveyor.yml to master Dec 3, 2016
.gitignore Reorganizing single python file into the beginnings of a proper packa… Oct 4, 2014
.gitmodules Removing submodules and switching METIS to ExternalProject_Add Apr 18, 2015
.travis.yml Revert "Temporarily disable tests while building up the cache on Trav… Aug 3, 2016
AUTHORS Adding a helper routine for carefully solving a 2x2 secular equation … Jul 17, 2016
CMakeLists.txt Upgrading to C++14 and tagging as 0.88-dev Dec 17, 2016
LICENSE Updating debian/copyright file and linking to it from the main LICENS… Nov 17, 2016
PUBLICATIONS.bib Updating the README and PUBLICATIONS Jul 13, 2016
README.md Reordering README unique features Nov 24, 2016
REFERENCES.bib Extending tests/lapack_like/Eig driver to non-standard datatypes Oct 29, 2016

README.md

Build Status Join the chat at https://gitter.im/elemental/chat

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.

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 DistMultiVec in favor of the newly extended DistMatrix
  • (1b) Extend DistSparseMatrix to 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

OpenBLAS is automatically downloaded and installed if no vendor/tuned BLAS/LAPACK is detected.

Intranodal graph partitioning

  • METIS
  • ParMETIS (Note: commercial users must disable this option during configuration)

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

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

Python interface

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:

Related open-source projects

Distributed dense linear algebra:

Distributed sparse-direct linear algebra:

Distributed linear algebra Frameworks

Convex optimization

Lattice reduction and number theory