Supernodal symbolic Cholesky factorization on a local-memory multiprocessor (Q1208511)

An improvement in the author's algorithm [(1) cf. \textit{A. George}, \textit{M. T. Heath}, \textit{E. Ng} and \textit{J. W-H. Liu} ibid. 5, 85-95 (1987; Zbl 0618.65023)] is described. First, a symbolic factorization algorithm for serial machines is presented. This is followed by a description of the parallel version of the sequential algorithm (1) and the proposed improvements. These improvements exploit the supernodal structure. The improved algorithm is compared with the original one using an Intel iPSC/2 on two sets of test problems. The programs are written in Fortran and compiled with optimization turned on. More than \(50\%\) improvement is observed for matrices of order greater than 5,000 on 16 or more processors.