Editing Sparse matrix (section)

===Reducing fill-in===

The ''fill-in'' of a matrix are those entries that change from an initial zero to a non-zero value during the execution of an algorithm. To reduce the memory requirements and the number of arithmetic operations used during an algorithm, it is useful to minimize the fill-in by switching rows and columns in the matrix. The [[symbolic Cholesky decomposition]] can be used to calculate the worst possible fill-in before doing the actual [[Cholesky decomposition]].

There are other methods than the [[Cholesky decomposition]] in use. Orthogonalization methods (such as QR factorization) are common, for example, when solving problems by least squares methods. While the theoretical fill-in is still the same, in practical terms the "false non-zeros" can be different for different methods. And symbolic versions of those algorithms can be used in the same manner as the symbolic Cholesky to compute worst case fill-in.