Limits on Parallelism in the Numerical Solution of Linear Partial Differential Equations
Patrick H Worley · SIAM Journal on Scientific and Statistical Computing · 1991
The problem considered is that of approximating the solution of a linear scalar partial differential equation (PDE) at one or more locations in its domain. A lower bound on the amount of data required to satisfy a given error tolerance in the approximation is described. Using this bound, a lower bound on the execution time of parallel algorithms that approximate the solution is derived. The lower bound on the execution time has the form $\alpha \cdot f_{( + )} \cdot \log _2 \epsilon^{ - 1} $, where a is a problem-dependent constant, $f_{( + )} $ is a measure of the speed of floating point arithmetic, and $ \epsilon$ is an upper bound on the error. Thus, when $\alpha > 0$, the execution time increases as $ \epsilon $ decreases, independent of the number of processors, the interconnection topology, and the algorithm used. Lower bounds on the execution time are also given for the cases where the interconnection network or the number of processors is specified. Recent research has established that it is often possible to use a large number of processors efficiently when calculating the numerical solution of a PDE if the problem is sufficiently large. In this paper, it is shown that increasing the size of such a problem will usually come at the cost of increasing the execution time. Two examples are described that verify this conclusion, an algorithm-independent analysis of an elliptic PDE and an analysis of a specific algorithm for the approximation of a hyperbolic PDE.