##
Efficient sparse Cholesky factorization on a parallel SIMD computer

####
Abstract

We investigate the effect of load balancing when performing Cholesky factorization
on a SIMD computer. In particular we describe a supernodal algorithm for
performing sparse Cholesky factorization. The way the matrix is mapped
onto the processors has significant effect on its efficiency. We show that
this assignment problem can be modeled as a graph coloring problem in a
weighted graph. By a simple greedy algorithm, we obtain substantial speed-up
compared to previously suggested data mapping schemes. Experimental runs
have been made on a 16K processor MasPar MP-2 parallel computer using symmetric
test matrices with irregular sparsity structure. On these problems our
implementation achieves performance rates of well above 200 Mflops in double
precision arithmetic.