Time Integration Methods for Large-scale Scientific Simulations
Glandon Jr, Steven Ross
MetadataShow full item record
The solution of initial value problems is a fundamental component of many scientific simulations of physical phenomena. In many cases these initial value problems arise from a method of lines approach to solving partial differential equations, resulting in very large systems of equations that require the use of numerical time integration methods to solve. Many problems of scientific interest exhibit stiff behavior for which implicit methods are favorable, however standard implicit methods are computationally expensive. They require the solution of one or more large nonlinear systems at each timestep, which can be impractical to solve exactly and can behave poorly when solved approximately. The recently introduced ``lightly-implicit'' K-methods seek to avoid this issue by directly coupling the time integration methods with a Krylov based approximation of linear system solutions, treating a portion of the problem implicitly and the remainder explicitly. This work seeks to further two primary objectives: evaluation of these K-methods in large-scale parallel applications, and development of new linearly implicit methods for contexts where improvements can be made. To this end, Rosenbrock-Krylov methods, the first K-methods, are examined in a scalability study, and two new families of time integration methods are introduced: biorthogonal Rosenbrock-Krylov methods, and linearly implicit multistep methods. For the scalability evaluation of Rosenbrock-Krylov methods, two parallel contexts are considered: a GPU accelerated model and a distributed MPI parallel model. In both cases, the most significant performance bottleneck is the need for many vector dot products, which require costly parallel reduce operations. Biorthogonal Rosenbrock-Krylov methods are an extension of the original Rosenbrock-Krylov methods which replace the Arnoldi iteration used to produce the Krylov approximation with Lanczos biorthogonalization, which requires fewer vector dot products, leading to lower overall cost for stiff problems. Linearly implicit multistep methods are a new family of implicit multistep methods that require only a single linear solve per timestep; the family includes W- and K-method variants, which admit arbitrary or Krylov based approximations of the problem Jacobian while maintaining the order of accuracy. This property allows for a wide range of implementation optimizations. Finally, all the new methods proposed herein are implemented efficiently in the MATLODE package, a Matlab ODE solver and sensitivity analysis toolbox, to make them available to the community at large.
General Audience Abstract
Differential equations are a fundamental building block of the mathematical description of many physical phenomena. Thus, solving problems involving complex differential equations is necessary for construction of scientific models of these phenomena, which can then be used to make useful predictions, such as weather forecasts. Aside from some simplified cases, complex differential equations cannot be solved exactly. Time integration methods are a class of numerical algorithms used to compute approximate solutions to differential equations, by stepping a given initial solution forward in time, producing a new solution at each timestep. Time integration methods are generally categorized as either explicit or implicit methods. Explicit methods are simpler, but have significant restrictions on the size of timesteps for challenging differential equations. Implicit methods relax this timestep restriction, but are much more expensive to compute. The recently introduced ``lightly-implicit'' K-methods provide a way to fuse the advantages of both implicit and explicit methods, by effectively treating a portion of the problem implicitly and the remainder explicitly. This work seeks to further two primary objectives: evaluation of these K-methods on very large problems, and development of new time integration methods. To this end, Rosenbrock--Krylov methods, the first K-methods, are applied to a large-scale problem and examined in a scalability study, and two new families of time integration methods are introduced: biorthogonal Rosenbrock--Krylov methods, and linearly implicit multistep methods. Ultimately, the goal is to develop new methods which allow for the creation of larger, more detailed, and more accurate scientific models, in order to get better and faster predictions.
- Doctoral Dissertations