Communication reduction for distributed sparse matrix factorization on a processor mesh

The problem of reducing the amount of interprocessor communication during the distributed factorization of a sparse matrix on a mesh-connected processor network is investigated. Two strategies are evaluated - 1) use of a fragmented distribution of row/columns of the matrix to limit the number of processors to which each row/column segment is transmitted, and 2) use of the elimination tree to permute the matrix so as to internalize as much of the communication as possible. Empirical evaluation of the schemes using matrices derived from circuit simulation shows significant reduction in the amount of communication for a 64 processor mesh.