Parallel Software for Implicit Differential Equations
by Henk Nieland
'Faster' and 'more efficient' are lasting computing requirements in order to deal with the ever increasing complexity and scale of problems whose solution the computer is expected to provide. Computer manufacturers go along with these requirements by developing computers with several processors operating in parallel. However, the development of suitable software is still lagging behind. At CWI, in a project supported by the Dutch Technology Foundation STW, parallel computing methods for the solution of implicit differential equations are developed and applied in a wide range of industrial problems.
Computer simulations based on mathematical modeling are increasingly taking over laboratory experiments or the use of scale models. Examples include the design of aircraft wings and testing electric circuits related to chips production. In several cases, where experiments are not feasible, for example in large-scale environmental problems, such simulations are even the only possibility. For most simulations computing speed is of crucial importance, for example for simulating the smooth motion of a robot arm (real-time computing) or for checking the effects of changes in the design of chips.
Evolution processes described by a set of partial differential equations are solved in approximation on a digital computer by stepwise integration in time. An integration method is called explicit if the computation of the next time step solely depends on the outcome of the previous one. In stiff problems, where several phenomena occurring on different time scales act simultaneously (electric currents in complex circuits display such behaviour), explicit methods are often of no avail. An important cause of failure is the accumulation of rounding errors, leading to a rapid loss of accuracy. Implicit methods are free of such drawbacks. Here the formula for the outcome of the next time step contains this outcome itself and, hence, requires the solution of a non-linear equation. As this is an expensive step in the computation, its speeding up is of the utmost importance.
CWI researcher Jacques de Swart discovered that such implicit methods are very well suited to parallelization. (Not every process in nature can be parallelized equally well: one sultan can have a rich offspring within a year through his harem, but each single harem lady can in that period have only one child no matter how many sultans were around.) He tested his method on a set of problems taken from industrial practice. Already with 4 processors a gain in computation speed with a factor 2 to 5 was realized.
An example representative for the power of De Swart's approach is a problem formulated already in the 1920s by the Hungarian mathematician Fekete (that 'zwart' and 'fekete' both mean 'black' could be more than a coincidence): distribute a set of points on the surface of a sphere such that they are optimally spread or, more precise, such that the product of their mutual distances is maximized. This problem turns up in various settings, for example in locating branches of a large company world-wide. An application in a very different field is the study of 'buckyballs' molecules consisting of a large number of carbon atoms, which are ordered in a spherical pattern resembling a football. (The discovery of C60 was awarded a Nobel Prize last year.) This stable configuration is in fact the solution of the Fekete problem. One of the several open questions here is the possible existence of even larger molecules of this type. Efficient solution of the Fekete problem for a large set of points would then be a useful research tool. De Swart's first step was to translate it into a physical problem, where the points are mutually repulsive 'charges' confined to the sphere's surface and subject to friction. The motion under the action of the various forces of the charges from an arbitrary initial state to a final state of minimal potential energy (the Fekete solution) is described by a set of differential equations. De Swart's parallel numerical software turns out to be very efficient compared with the optimization software (based on quite different methods) which is usually applied to such problems, and the relative efficiency rapidly increases with the number of points. Moreover, De Swart's method can easily accomodate to model extensions and changes, such as insertion of a different atom. For more information, see Jacques De Swart's homepage at http://www.cwi.nl/~jacques/
Please contact:
Jacques de Swart - CWI
Tel: +31 20 592 4176
E-mail: Jacques.de.Swart@cwi.nl
