Elimination Structures in Scientific Computing
Alex Pothen, Sivan Toledo · 2004
Alex Pothen Old Dominion University Sivan Toledo Tel-Aviv University The most fundamental computation in numerical linear algebra is the factorization of a matrix as a product of two or more matrices with simpler structure. An important example is Gaussian elimination, in which a matrix is written as a product of a lower triangular matrix and an upper triangular matrix. The factorization is accomplished by elementary operations in which two or more rows (columns) are combined together to transform the matrix to the desired form. In Gaussian elimination, the desired form is an upper triangular matrix, in which nonzero elements below the diagonal have been transformed to be equal to zero. We say that the subdiagonal elements have been eliminated. (The transformations that accomplish the elimination yield a lower triangular matrix.) The input matrix is usually sparse, i.e., only a few of the matrix elements are nonzero to begin with; in this situation, row operations constructed to eliminate nonzero elements in some locations might create new nonzero elements, called fill, in other locations, as a side-effect. Data structures that predict fill from graph models of the numerical algorithm, and algorithms that attempt to minimize fill, are key ingredients of efficient sparse matrix algorithms. This chapter surveys these data structures, known as elimination structures, and the algorithms that construct and use them. We begin with the elimination tree, a data structure associated with symmetric Gaussian elimination, and we then describe its most important applications. Next we describe other data structures associated with symmetric Gaussian elimination, the clique tree, the clique cover, and the quotient graph. We then consider data structures that are associated with unsymmetric Gaussian elimination, the column elimination tree and the elimination directed acyclic graph. This survey has been written with two purposes in mind. First, we introduce the algorithms community to these data structures and algorithms from