Time complexity analysis for distributed memory computers: implementation of parallel conjugate gradient method
Computing Science in the Netherlands : jaarbeurs Utrecht 7 en 8 november 1991 : proceedings
Stichting Mathematisch Centrum
Faculty of Science (FNWI)
Informatics Institute (IVI)
New developments in Computer Science, both hardware and software, offer researchers, such as physicists, unprecedented possibilities
to solve their computational intensive problems.However, full exploitation of e.g. new massively parallel computers, parallel
languages or runtime environments requires an approach that combines elements of computer science, numerical mathematics and,
in our case, physics. We call this b-computer science.Here we present an example of a computational intensive physical application,
the coupled dipole formulation of elastic light scattering from arbitrary shaped particles. The computational kernel of this
method is a large set of linear equations. We solve this set by means of a Conjugate Gradient (CG) method, implemented on
a coarse grain distributed memory computer (a Transputer network).This paper describes the parallelization of a CG method.
Two important choices are discussed; what is the best possible decomposition and which processor network topology is most
suited. We introduce a general method to answer these questions and investigate its usefulness by applying this method to
our application. It is concluded that implementation of the CG method, with a row-block decomposition of the coefficient matrix,
on a ring of Transputers is the most efficient choice.Finally the actual implementation is described, and preliminary experimental
timing results are compared with the theoretical time complexity analysis.
If you believe that digital publication of certain material infringes any of your rights or (privacy) interests, please let
the Library know, stating your reasons. In case of a legitimate complaint, the Library will make the material inaccessible
and/or remove it from the website. Please Ask the Library, or send a letter to: Library of the University of Amsterdam, Secretariat, Singel 425, 1012 WP Amsterdam, The Netherlands.
You will be contacted as soon as possible.