A Note on Fill for Sparse Matrices
Alan D. George, Wai-Hung Liu · SIAM Journal on Numerical Analysis · 1975
Suppose the sparse matrix A has a triangular factorization $LU$, where L is lower triangular and U is upper triangular. With the usual assumption that exact numerical cancellation does not occur during the factorization, $L + U$ is generally fuller than A. It is well known that this fill is confined to the envelope of A; that is, to positions which are to the right of the first nonzero component in each row and also below the first nonzero component in each column. If the envelope of $L + U$ is full, we say A has suffered maximal fill. In this paper we give some simple easily tested properties of A which indicate when fill will be maximal.