Dense and sparse linear solvers

ALGLIB, a free and commercial open source numerical library, provides one of the best open-source suites of dense and sparse linear equations solvers. ALGLIB is available in multiple programming languages, including C++, C#, Java, and Python.

The library supports various types of problems and solvers: dense and sparse, nonsymmetric and symmetric, direct and iterative ones. Both free and commercial editions of the ALGLIB are scalable to problems with millions of variables.

Programming languages supported

ALGLIB supports many programming languages, including C++, C#, Java, Python, and others:

• C++ version. Highly optimized, portable, self-contained library (x86/x64/ARM; works on Windows, Linux, and POSIX systems)
• C# version. Unified C# API for two backends: a fully managed C# implementation and a high-performance native computational core written in C
• Java, Python, and other languages. A wrapper for a high-performance native computational core written in C. Seamless integration with the target programming language

A distinctive feature of ALGLIB is that it provides the same API in all programming languages. This is achieved through our exclusive automatic code translation and wrapper generation technology.

Problems and solvers

Dense solvers

Dense linear equations are traditionally solved by direct solvers (ones that factorize the system matrix to find a solution). The directdensesolvers subpackage of ALGLIB includes many dense solvers intended for various kinds of problems.

The subpackage is discussed in greater detail in the separate article; here, we merely briefly outline the problem types supported:

• Nonsymmetric real and complex systems. The most general case, usually solved with LU decomposition and optional iterative refinement
• Symmetric/Hermitian positive definite systems. An important special case, solved with Cholesky decomposition
• Linear least squares problems. Solved with SVD decomposition

The ALGLIB Reference Manual entry for the subpackage (directdensesolvers) includes several examples in all programming languages supported by ALGLIB.

Sparse iterative solvers

Iterative methods are a popular approach to large sparse systems of linear equations. They usually have modest memory requirements (often linear with respect to the problem size) and predictable iteration costs that do not depend on the specific sparsity pattern of the system being solved. The only downside is that their convergence speed depends heavily on the system's condition number.

ALGLIB includes several sparse iterative solvers provided by various ALGLIB subpackages:

• The generalized minimum residual method (GMRES) - probably, the most popular method for general (nonsymmetric) linear equations. The solver is provided by the iterativesparse subpackage and supports both in-core (sparse matrix A is provided explicitly) and out-of-core (sparse matrix A is given as a matrix-vector product operator) modes. The GMRES solver is discussed in greater detail in the separate article.
• The linear conjugate gradient method (CG) - is a popular choice for symmetric positive definite linear equations systems. The CG solver is provided by the lincg subpackage (see the link for examples in all programming languages supported by ALGLIB). The article about sparse iterative solvers provides some additional information about linear CG method.
• The LSQR method - a powerful and accurate iterative method for sparse linear least squares provided by the linlsqr subpackage (see the link for examples in all programming languages supported by ALGLIB). It is discussed in the separate article.

Sparse direct solvers

Direct (factorization-based) sparse solvers are, in some sense, complementary to iterative ones. The running time of direct solvers shows no dependency on the condition number of the system being solved. They also tend to find solutions with very high accuracy. By contrast, their running time and memory requirements depend strongly on the sparsity pattern of the system's matrix.

ALGLIB includes several sparse direct solvers provided by the directsparsesolvers subpackage (see the link for examples):

• The sparse positive definite direct solver, which relies on the supernodal sparse Cholesky decomposition with approximate minimum degree ordering (AMD). This solver is available through the sparsespdsolve function.
• The sparse nonsymmetric direct solver, which utilizes the sparse LU decomposition with dynamic pivoting. This solver is available through the sparsesolve function.
• The sparse skyline-based solver, which is intended for low-profile positive definite matrices stored in the SKS (Skyline storage) format. This can be a good alternative for a more general Cholesky-based solver when the matrix has a very small profile. This solver is available through the sparsespdsolvesks function.