Time complexity of a parallel conjugate gradient solver for light scattering simulations: theory and SPMD implementation
Peter M. A. Sloot, Alfons G. Hoekstra, W. Hoffmann, Louis O. Hertzberger · UvA-DARE (University of Amsterdam) · 1992
We describe parallelization for distributed memory computers of a preconditioned Conjugate Gradient method, applied to solve systems of equations emerging from Elastic Light Scattering simulations. The execution time of the Conjugate Gradient method is analyzed theoretically. First expressions for the execution time for three different data decompositions are derived. Next two processor network topologies are taken into account and the theoretical execution times are further specified as a function of these topologies. The Conjugate Gradient method was implemented with a rowblock data decomposition on a ring of transputers. The measured and theoretically calculated execution times agree within 5 %. Finally convergence properties of the algorithm are investigated and the suitability of a polynomial preconditioner is examined.