4
$\begingroup$

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?

$\endgroup$

1 Answer 1

5
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.