On symbolic factorization of partitioned sparse symmetric matrices

AbstractPartitioning a sparse matrix A is a useful device employed by a number of sparse matrix techniques. An important problem that arises in connection with some of these methods is to determine the block structure of the Cholesky factor L of A, given the partitioned A. For the scalar case, the problem of determining the structure of L from A, so-called symbolic factorization, has been extensively studied. In this paper we study the generalization of this problem to the block case. The problem is interesting because an assumption relied on in the scalar case no longer holds; specifically, the product of two nonzero scalars is always nonzero, but the product of two nonnull sparse matrices may yield a zero matrix. Thus, applying the usual symbolic factorization techniques to a partitioned matrix, regarding each submatrix as a scalar, may yield a block structure of L which is too full. In this paper an efficient algorithm is provided for determining the block structure of the Cholesky factor of a partitioned matrix A, along with some bounds on the execution time of the algorithm