Operations Research Stack Exchange is a question and answer site for operations research and analytics professionals, educators, and students. It only takes a minute to sign up.
Sign up to join this community
I've long wondered this, but what is the algorithm(s) implemented in modern linear equation solvers for sparse systems?
The obvious answer I can think of is Gauss-Jordan with a bunch of tricks to make it computationally efficient and exploit sparsity, or LU decompositions (e.g. the ones in Eigen), but are there any different algorithms that are commonly used?
The following isn't meant to be exhaustive. It usually depends on the structure of the matrix because that impacts the way you choose it. In general there are sparse variants for many of the general matrix decompositions you see LU, QR, SVD and what not. There are also sparse Kyrlov methods such as the shifted Block Lanczos method. If it isn't symmetric then there is the Arnoldi algorithm which they use in GMRES (there is a sparse variant). There are a bunch of tricks they do use like
Usually the reasoning for choosing one over the other is a combination of the size of the matrix, the conditioning and any relevant structure. MATLAB has a detailed explanation of how the backslash operator works which you can see below. If you look on a website like the NETLIB it has the actual code for most of LAPACK (https://www.netlib.org/).
