Parallel Preconditioning and Approximate Inverses on the Connection Machine

摘要

We present a new parallel approach to preconditioning for very large, sparse, unsymmetric, linear svstems. We explicitly compute an approximate inverse to our original matrix. This new preconditioning matrix can be applied most efficiently for iterative methods on massively parallel machines, since the preconditioning phase involves only a matrix-vector multiplication, with possibly a dense matrix. Furthermore the actual computation of the preconditioning matrix has natural parallelism. For a problem of size n, the preconditioning matrix can be computed by solving n independent small least squares problems. The algorithm and its implementation on the Connection Machine CM-2 are discussed in detail and supported by extensive timings obtained from real problem data.