A Fan-In Algorithm for Distributed Sparse Numerical Factorization
Cleve Ashcraft, Stanley C. Eisenstat, Joseph W. H. Liu · SIAM Journal on Scientific and Statistical Computing · 1990
This paper presents a column-oriented distributed algorithm for factoring a large sparse symmetric positive definite matrix on a local-memory parallel processor. Processors cooperate in computing each column of the Cholesky factor by calculating independent updates to the corresponding column of the original matrix. These updates are sent in a fan-in manner to the processor assigned to the column, which then completes the computation. Experimental results on an Intel iPSC/2 hypercube demonstrate that the method is effective and achieves good speedups.