Large-scale scientific computation
The increasing speed of computers and advances in
numerical methods have made it possible to solve most
small problems rapidly by means of readily available
software, and the attention of many numerical analysts
has turned to the solution of problems so large that
they require inordinate amounts of computer time.
The use of the most efficient method has much greater
importance in large problems than it does in small ones.
In the latter the flexibility of human use of the
program may be of much greater importance. One measure
of the efficiency of a numerical method is the number of
arithmetic operations needed to solve a problem. (Others
include the amount of memory used and the order in which
it is used, but these issues are more properly subjects
of computer science.) Computational complexity is
the study of the inherent computational cost (measured
by number of operations) of solving a problem. The
result of a complexity analysis is an estimate of how
rapidly the solution time increases as the problem size
increases. It can be used to analyze problems and assist
in the design of algorithms for their solution.
On a serial computer, which is one with a
single processor capable of performing only one
arithmetic operation at a time, the time needed to solve
a problem is proportional to the number of operations,
so that this is the number that the numerical analyst
tries to reduce in algorithm design. Because parallel
computers have more than one processor, they are capable
of performing several arithmetic operations
simultaneously. To make effective use of a parallel computer,
an algorithm must have parallelism; that is, it must
require the simultaneous performance of certain
operations. For example, evaluation of the expression a
b + c requires two operations, but the
multiplication must be completed before the addition can
be started: they must be done serially. On the other
hand, in evaluating the expression w + x +
y + z, two of the additions can be
performed in parallel, for example w + x
and y + z, and then their results can be
added. In this case there are three arithmetic
operations, but a suitably organized parallel computer
can complete the sum in the time it takes to do two
additions. In the design of numerical algorithms for
parallel computers, one relevant criterion is the number
of nonoverlapped operations needed.
|