sparse factorization and fill-in

Most large matrices from real applications are sparse: almost all their entries are zero, because each variable couples to only a few others (a node touches its neighbors in a mesh, a web page links to a few others). Storing and computing with only the nonzeros is what makes million-by-million problems tractable. The trouble is what happens to those zeros during factorization.

When you eliminate a column in Gaussian elimination, subtracting a multiple of the pivot row can turn a structural zero into a nonzero. That newly created nonzero is called fill-in. A matrix that started 99 percent zero can have a factor L that is far denser, exhausting memory and time. Fill-in, not the original sparsity, is what limits a sparse direct solve.

The crucial insight is that the amount of fill-in depends drastically on the order in which you eliminate. Permuting the rows and columns first, M -> P M P^T, can be the difference between almost no fill and catastrophic fill. The classic bad case is a matrix whose first row and column are dense (an arrow pointing into a sparse body): eliminate that variable first and you fill the entire matrix; eliminate it last and you barely fill at all.

Finding the truly optimal ordering is NP-hard, so practitioners use heuristics: minimum degree (eliminate the variable with the fewest connections next) and nested dissection (recursively split the graph by small separators). These reorderings are why sparse Cholesky and sparse LU can solve enormous structured systems that would be hopeless if treated as dense.