Fill-in

Arises in the context of sparse matrices subjected to certain operations. In particular, a basis may be factored in a product of elementary matrices to represent Gaussian elimination. The nonzeroes that appear in positions that were not in the original matrix are called fill-in coefficients. An example of a matrix that has no fill-in for this factorization is one that is lower triangular. In that case the factors appear as:

$LaTeX: \left[ \begin{array}{ccc}

• & 0 & 0 \\ * & * & 0 \\ * & * & *

\end{array} \right] = \left[ \begin{array}{ccc}

• & 0 & 0 \\ * & 1 & 0 \\ * & 0 & 1

\end{array} \right] \left[ \begin{array}{ccc} 1 & 0 & 0 \\ 0 & * & 0 \\ 0 & * & 1 \end{array} \right] \left[ \begin{array}{ccc} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & * \end{array} \right]$

On the other hand, a lower triangular matrix could cause fill-in for some other factorization, such as the Cholesky factorization. A completely dense matrix also has no fill-in since there were no zeroes to begin with. Here is an example of fill-in, taking the original order of rows and columns in the product form:

$LaTeX: \left[ \begin{array}{ccc}

• & 0 & * \\ * & * & 0 \\ * & * & *

\end{array} \right] = \left[ \begin{array}{ccc}

• & 0 & 0 \\ * & 1 & 0 \\ * & 0 & 1

\end{array} \right] \left[ \begin{array}{ccc} 1 & 0 & 0 \\ 0 & * & 0 \\ 0 & * & 1 \end{array} \right] \left[ \begin{array}{ccc} 1 & 0 & * \\ 0 & 1 & \# \\ 0 & 0 & * \end{array} \right],$

where $LaTeX: \#$ is fill-in.