Stanford 50: State of the Art and Future Directions of Computational Mathematics and Numerical Computing


  • March 29, 2007
  • 11:25 am - 11:50 am

Future directions in petascale computing: Explicit methods for implicit problems

Bill Gear (Princeton University)

A combination of circumstances is causing a renewed interest in explicit methods for what are traditionally viewed as implicit problems when those problems become sufficiently large that massive parallelism is the only realistic computational approach. The difficulty with problems that exhibit diffusion or similar phenomena that lead to stiffness is that conventional methods for handling stiffness with large time steps require the implicit solution of a system of nonlinear equations at each time step (although typically one solution of a linear system is sufficient to get the required accuracy in a Newton-like step). However, the heavy load of inter-processor communication of direct methods in most cases is a significant factor, so iterative methods must be used. Unless there are suitable fast preconditioners to reduce the number of iterations, these may also be sufficiently time-consuming that other methods become more attractive.

While implicit methods have to be used if a problem is arbitrarily stiff, if we have some knowledge of the location of the eigenvalues, there are explicit methods that can be competitive. The first work in this area that led to codes was probably the Runge-Kutta Chebyshev methods, although related ideas have been around for some time. In these methods, high-stage RK methods are used, not to get a high order of accuracy (since second order often suffices for many PDEs), but to get extended regions of stability. Recently we have been studying a related class of methods-telescopic projective methods-that can achieve similar goals and also place stability regions in desired locations. These are methods that have the potential to be adaptive and for which second order can be obtained.

A further advantage of these methods is that they can be "wrapped around" single-step legacy codes or microscopic simulators for which we want to explore macroscopic phenomena.

Stanford University Home Page