Abstract. This paper presents the design and implementation of a memory scalable parallel symbolic factorization algorithm for general sparse unsymmetric matrices. Our parallel algorithm uses a graph partitioning approach, applied to the graph of |A|+|A| T , to partition the matrix in such a way that is good for sparsity preservation as well as for parallel factorization. The partitioning yields a so-called separator tree which represents the dependencies among the computations. We use the separator tree to distribute the input matrix over the processors using a block cyclic approach and a subtree to sub-processor mapping. The parallel algorithm performs a bottom up traversal of the separator tree. With a combination of right-looking and left-looking partial factorizations, the algorithm obtains one column structure of L and one row structure of U at each step. The algorithm is implemented in C and MPI. From a performance study on large matrices, we show that the parallel algorithm significantly reduces the memory requirement of the symbolic factorization step, as well as the overall memory requirement of the parallel solver. It also often reduces the runtime of the sequential algorithm, which is already relatively small. In general, the parallel algorithm prevents the symbolic factorization step from being a time or memory bottleneck of the parallel solver. 1. Introduction. We consider solving a sparse unsymmetric system of linear equations Ax = b using a direct method, which first factorizes the matrix A into the product of a unit lower triangular matrix L and an upper triangular matrix U , then solves LU x = b via two triangular solutions. One distinct property of sparse LU factorization is the notion of fill-in. That is, a zero element in the original matrix A can become nonzero in L and U . The purpose of symbolic factorization is to compute the nonzero structure of the factors L and U , which contains the original nonzero elements in A as well as the filled elements. When there is no need to pivot during numerical factorization, the nonzero structure of L and U can be computed without referring to the numerical values of the matrix. This allows us to allocate sufficient memory and to organize computations before numerical factorization. Computationally, symbolic factorization is usually much faster than numerical factorization, and hence there has not been much motivation to parallelize this step. However, as numerical factorization has been made more and more scalable, symbolic factorization can become a serious bottleneck. In particular, a sequential algorithm requires the nonzero structure of the matrix A to be assembled onto one processor, which leads to a serious bottleneck in memory (if not timewise). We have therefore designed and implemented a memory-scalable symbolic factorization algorithm for distributed memory machines. The parallel algorithm and the software are suitable for sparse LU factorization with static pivoting [20] . We developed this parallel algorithm in the context of the SuperLU DIST [20] solver, which is a widely used sparse direct solver for distributed memory parallel computers. SuperLU DIST contains several distinct steps in the solution process: 1. Choose a permutation matrix P 1 and diagonal matrices D 1 and D 2 so that the diagonal entries of P 1 D 1 AD 2 are ±1 and the magnitudes of the off-diagonal entries are bounded by 1. The above equilibration and permutation help ensure accuracy of the computed solution. Currently, this is achieved using the HSL routine MC64 [6] . The purpose of the large-diagonal permutation is to decrease the probability of encountering small pivots during factorization. 2. Reorder the equations and variables by using a heuristic that chooses a per-
In REF , pivoting is employed to reduce the number of fill-ins for LU factorization.
PARALLEL SYMBOLIC FACTORIZATION FOR SPARSE LU WITH STATIC PIVOTING
ICS
Computer Science