Solution of sparse positive definite systems on a hypercube (Q1124265)

The paper provides a detailed overview of an experimental package for solving large sparse positive definite systems of the form \(Ax=b\) on multiprocessors with a hypercube interconnection network. The method of Cholesky factorization \(A=LL^ T\) is used, involving four steps: (1) ordering: determine a permutation matrix P so that \(PAP^ T\) has sparse Cholesky factor L; (2) symbolic factorization: determine the structure of L and set up a data structure that exploits the sparsity of L; (3) numerical factorization: place the nonzeros of A into the data structure and then compute L; (4) triangular solution: using L, solve the triangular systems \(Lu=Pb\), \(L^ Tv=u\) and set \(x=P^ Tv.\) The article treats all these steps in detail, explains the role of elimination trees in the exploitation of sparsity and the identification of parallelism, provides pseudo-code algorithms, and presents numerical experiments run on an Intel iPSC multiprocessor showing that the reduction in execution time as the number of processors increases is much less significant for steps 1, 2, and 4 above, compared to the numerical factorization (step 3).