Laura Grigori : May 23, 2002

Structure prediction for sparse LU factorization with partial pivoting.

Abstract

Usually, computations on sparse matrices have an initial phase that predicts the nonzero structure of the output, which helps with memory allocations, set up data structures and schedule parallel tasks prior to the numerical computation itself.

In LU factorization with partial pivoting, a square matrix A is factored as PA=LU, where P is a permutation matrix that depends on the values of the nonzeros of A and cannot be predicted only from the nonzero structure of A. In this presentation, we will discuss two structure prediction questions for this problem. The first is to predict bounds on the nonzero structure of the factors L and U. The second is to predict which columns of L and U depend directly or indirectly on which earlier columns. We restrict at the beginning our attention to the class of matrices that satisfy an irreducibility condition called the strong Hall property. We then extend the results to the class of matrices satisfying a weaker condition, called the Hall property.