# Algorithms for sparse linear systems

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?

• There are some newer matrix decompositions you don't generally see - Non-negative matrix factorizations and the interpolative decomposition are newer. The interpolative decomposition is good for sparse problems - amath.colorado.edu/faculty/martinss/Pubs/…. Feb 21 at 18:59