# How to RowReduce a sparse matrix?

I want to compute the reduced row echelon form of a sparse matrix, but RowReduce returns a dense matrix. Is there a build-in function that computes the reduced form as a sparse matrix?

The row echelon form of a general sparse matrix is not sparse.

However, there is a certain chance that the row echelon form of a suitable row/column permutation of the original matrix is sparse. This is what direct solvers for sparse arrays usually do when they perform a sparse LU-decomposition.

A sparse matrix:

G = GridGraph[{300, 300}];
A = KirchhoffMatrix[G] + IdentityMatrix[VertexCount[G], SparseArray];


Generating a LinearSolveFunction S that stores the factorization:

S = LinearSolve[A, Method -> "Multifrontal"];


Lower triangular factor L, upper triangular factor U and permutation p can be obtained by

Retrieving the

L = S["getL"];
U = S["getU"];
{p, q} = S["getPermutations"];


The "Multifrontal" solver (here it is UMFPACK that is used as backend) attempts to find p and q such that the factors have small density:

A["Density"]
L["Density"]
U["Density"]


0.0000554074

0.000361489

0.000361489

We see that there is indeed quite a bit of fill-in, i.e., the factors are not as sparse as the matrix A itself.

Here you see how the permutations and the factors reproduce A:

Max[Abs[A - (L.U)[[p, q]]]]
Max[Abs[A - (L[[p]].U[[All, q]])]]


3.55271*10^-15

3.55271*10^-15

So, up to the permutations (and the fact that pivots are not normalized), the sparse row echelon form is U.