Keywords: computational engineering, parallel processing, scalable parallel solution, asynchronous algorithms, multilevel methods.

This paper considers the parallel solution of linear systems of equations that arise from the discretization of one or more partial differential equations (PDEs). The motivation for this exposition is our desire to consider (i) very highly scalable parallelism that will be capable of exploiting future trends in multicore hardware, and (ii) the use of the most efficient numerical algorithms. The latter point is based upon the observation that the easiest algorithms to implement in parallel are not always the best algorithms in terms of their accuracy or their speed of convergence.

As computational hardware continues to evolve there is a need to develop new parallel numerical algorithms that are capable of exploiting many thousands of cores concurrently. Historically, good parallel efficiency has only been possible with very large numbers of cores for certain classes of algorithm, such as those based upon dense matrices. These algorithms have a large amount of computational work per unit of data and a large amount of computation relative to communication. Many important problems in computational engineering take a different form however, ultimately reducing to the solution of sparse systems of linear equations. For the solution of PDEs for example, the finite element or finite difference discretization schemes lead to precisely such sparse systems.

The current state-of-the-art provides a choice between parallelizing a fast and accurate sequential algorithm, but with only limited parallel scalability, or else implementing a highly scalable asynchronous iteration but with only a slow rate of convergence. In this review we provide an overview of both approaches: focusing particularly on parallel multigrid methods for the former and asynchronous relaxation schemes for the latter. Neither approach is likely to prove satisfactory in the future, where there will be a need to solve complex PDE models using large numbers of degrees of freedom, for high accuracy, and large numbers of computational cores, for high speed. Hence we also review those algorithms that we believe have the potential for combining both excellent convergence properties (e.g. multilevel solvers) and excellent parallel scalability (e.g. fault tolerant and asynchronous). Our long term goal is to find ways in which to develop these ideas further for the practical realization of highly scalable but near-optimal iterative techniques.

purchase the full-text of this paper (price £20)

go to the next paper
return to the table of contents
return to Computational Technology Reviews
purchase this volume (price £80 +P&P)