fill-in and reordering

Sparse direct methods would be wonderful if elimination kept the matrix sparse — but it does not, on its own. When you subtract a multiple of one row from another to clear an entry, you can turn a position that was zero into a nonzero. Those newly-created nonzeros are called fill-in, and they make the factors L and U denser than the original A. Reordering is the art of permuting the rows and columns BEFORE elimination so that as little fill-in as possible occurs.

Here is the intuition for why order matters. Picture a 'star' matrix where one variable couples to all the others. If you eliminate that hub variable FIRST, clearing its column creates connections between every pair of its former neighbours — the factor fills in completely, a catastrophe. If instead you eliminate the hub LAST, the spokes are cleared cheaply and almost no fill appears. So the same matrix, factored in two different orders, can produce factors that differ by orders of magnitude in size and cost. Reordering algorithms — minimum-degree, nested dissection, reverse Cuthill-McKee — are heuristics that choose an elimination order to keep the factors sparse. Crucially this is a SYMBOLIC step: it depends only on the pattern of nonzeros, not their values, so it can be done once and reused.

Getting the ordering right is the single biggest lever in sparse direct solving: a good ordering can be the difference between a factorization that fits in memory and finishes in seconds and one that fills in densely and exhausts the machine. This is why sparse solvers split into an analyze phase (choose the ordering and predict the fill) and a factorize phase. The honest caveat: finding the truly fill-minimizing ordering is an NP-hard combinatorial problem, so the orderings used are clever heuristics, not optima — and for hard 3D problems even the best ordering leaves enough fill that an iterative method may win.