Some results on sparse matrices

Abstract

A comparison in the context of sparse matrices is made between the Product Form of the Inverse PFI (a form of Gauss-Jordan elimination) and the Elimination Form of the Inverse EFI (a form of Gaussian elimination). The precise relation of the elements of these two forms of the inverse is given in terms of the nontrivial elements of the three matrices L, U, U˜l associated with the triangular factorization of the coefficient matrix A; i.e., A = L- U, where L is lower triangular and U is unit upper triangular. It is shown that the zero- nonzero structure of the PFI always has more nonzeros than the EFI. It is proved that Gaussian elimination is a minimal algorithm with respect to preserving sparseness if the diagonal elements of the matrix A are nonzero. However, Gaussian elimination is not nec essarily minimal if A has some zero diagonal elements. The same statements hold for the PFI as well. A probabilistic study of fill-in and computing times for the PFI and EFI sparse matrix algorithms is presented. This study suggests quantitatively how rapidly sparse matrices fill up for increasing densities, and emphasizes the necessity for reordering to minimize fill-in. ome Results on Sparse Matrices* By Robert K. Brayton, Fred G. Gustavson and Ralph A. Willoughby Abstract. A comparison in the context of sparse matrices is made between the Product Form of the Inverse PFI (a form of Gauss-Jordan elimination) and the Elimination Form of the Inverse EFI (a form of Gaussian elimination). The precise relation of the elements of these two forms of the inverse is given in terms of the nontrivial elements of the three matrices L, Ul associated with the triangular factorization of the coefficient matrix A; i.e., A L- U, where L is lower triangular and U is unit upper triangular. It is shown that the zero- nonzero structure of the PFI always has more nonzeros than the EFI. It is proved that Gaussian elimination is a minimal algorithm with respect to preserving sparseness if the diagonal elements of the matrix A are nonzero. However, Gaussian elimination is not necessarily minimal if A has some zero diagonal elements. The same statements hold for the PFI as well. A probabilistic study of fill-in and computing times for the PFI and EFI sparse matrix algorithms is presented. This study suggests quantitatively how rapidly sparse matrices fill up for increasing densities, and emphasizes the necessity for reordering to minimize fill-in. © 1970 American Mathematical Society.