We will discuss parallelization techniques for the preconditioned iterative methods that use explicit preconditioners such as approximate inverses or factored approximate inverses. Applications of these preconditioners require sparse matrix-vector multiplication (SpMxV) operations. Roughly speaking, the problem reduces to partitioning two or more matrices together in order to efficiently parallelize the computations of the form . Note that the computations are performed as successive SpMxV operations, and hence there are dependencies among the input and output vectors of these SpMxV operations. Additional dependencies are imposed by the linear vector operations that take part in a full step of the chosen iterative method. We will first discuss how to analyze the preconditioned iterative methods to determine the dependencies between the inputs and outputs of the SpMxV operations. We will give a short account of such dependencies for a number of widely used methods including BiCGStab, preconditioned conjugate gradients, and GMRES. Next, we will develop hypergraph models which capture the dependencies among the input and output vectors of the SpMxV operations with different matrices. We will show that partitioning a single hypergraph amounts to simultaneous partitioning of the matrices in computations in such a way that the total volume of communication is minimized and an appropriate balance criterion among the processor loads is maintained. We will present experimental results obtained using a parallel implementation of the right preconditioned BiCGStab method on a PC cluster.

This is a joint work with Prof C. Aykanat of Bilkent University, Ankara, Turkey.