Fill-in

From Glossary

Jump to: navigation, search

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}
</p>
<ul><li> & 0 & 0 \\ * & * & 0 \\ * & * & *
</li></ul>
<p>\end{array} \right]
=
\left[ \begin{array}{ccc}
</p>
<ul><li> & 0 & 0 \\ * & 1 & 0 \\ * & 0 & 1
</li></ul>
<p>\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}
</p>
<ul><li> & 0 & * \\ * & * & 0 \\ * & * & *
</li></ul>
<p>\end{array} \right]
=
\left[ \begin{array}{ccc}
</p>
<ul><li> & 0 & 0 \\ * & 1 & 0 \\ * & 0 & 1
</li></ul>
<p>\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.


Views
Personal tools