A SUPERNODAL CHOLESKY FACTORIZATION ALGORITHM FOR SHARED-MEMORY MULTIPROCESSORS

This paper presents a parallel sparse Cholesky factorization algorithm for shared-memory MIMD multiprocessors. The algorithm is particularly well suited for vector supercomputers with multiple processors, such as the Cray Y-MR The new algorithm is a straightforward parallelizatio n of the left-looking supernodal sparse Cholesky factorization algorit hm. Like its sequential predecessor, it improves performance by reduci ng indirect addressing and memory traffic. Experimental results on a C ray Y-MP demonstrate the effectiveness of the new algorithm. On eight processors of a Cray Y-MP, the new routine performs the factorization at rates exceeding one Gflop for several test problems from the Harwel l-Boeing sparse matrix collection.