1 
Authors  A.G. Hoekstra, P.M.A. Sloot, M.J. Haan, L.O. Hertzberger  Title  Time complexity analysis for distributed memory computers: implementation of parallel conjugate gradient method 
Book/source title  Computing Science in the Netherlands : jaarbeurs Utrecht 7 en 8 november 1991 : proceedings 
Author/Editor  J. van Leeuwen 
Publisher  Stichting Mathematisch Centrum 
Place  Amsterdam 
Year  1991 
Pages  249266 
Faculty  Faculty of Science 
Institute/dept.  FNWI: Informatics Institute (II) 
Keywords  Distributed computing; Parallel computers 
Abstract  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 bcomputer 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 rowblock 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. 
Document type  Chapter 
Download  
Document finder 

Use this url to link to this page: http://dare.uva.nl/en/record/117623
Contact us about this recordNotify a colleague
Add to bookbag
