Sparse direct solvers for linear equations

ALGLIB, a free and commercial open source numerical library, provides one of the best open-source suites of 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, and direct and iterative. This article discusses ALGLIB's sparse direct solvers. Other solver types are discussed in the separate article on the subject.

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.

Problem types

Sparse symmetric positive definite linear equations

ALGLIB includes a sparse Cholesky-based solver which can solve systems of linear equations with positive definite matrices. This functionality is provided by the sparsespdsolve function.

Internally, this solver uses the following improvements:

• Supernodal Cholesky factorization with SIMD kernels. This feature is present in both the commercial and free editions of ALGLIB, although different editions may have different sets of SIMD kernels.
• Fill-in reducing reordering - based on the Approximate Minimum Degree (AMD) with several additional improvements. This feature is present in all ALGLIB editions.
• Multithreading support - which is present only in the commercial edition. Multithreading speed-up depends heavily on the specific sparsity pattern of the problem.

Sparse nonsymmetric linear equations

Sparse nonsymmetric systems can be solved with the sparse LU-based solver which uses LU decomposition with dynamic pivoting. This functionality is provided by the sparsesolve function.

This article is licensed for personal use only.