SUNDIALS: Suite of nonlinear and differential/algebraic equation solvers

ABSTRACT

SUNDIALS is a suite of advanced computational codes for solving large-scale problems that can be modeled as a system of nonlinear algebraic equations, or as initial-value problems in ordinary differential or differential-algebraic equations. The basic versions of these codes are called KINSOL, CVODE, and IDA, respectively. The codes are written in ANSI standard C and are suitable for either serial or parallel machine environments. Common and notable features of these codes include inexact Newton-Krylov methods for solving large-scale nonlinear systems; linear multistep methods for time-dependent problems; a highly modular structure to allow incorporation of different preconditioning and/or linear solver methods; and clear interfaces allowing for users to provide their own data structures underneath the solvers. We describe the current capabilities of the codes, along with some of the algorithms and heuristics used to achieve efficiency and robustness. We also describe how the codes stem from previous and widely used Fortran 77 solvers, and how the codes have been augmented with forward and adjoint methods for carrying out first-order sensitivity analysis with respect to model parameters or initial conditions.

REFERENCES

• 1: Brenan, K. E., Campbell, S. L., and Petzold, L. R. 1996. Numerical Solution of Initial-Value Problems in Differential-Algebraic Equations. SIAM Press, Philadelphia, PA.
• 2: Peter N. Brown, A local convergence theory for combined inexact-Newton/finite-difference projection methods, SIAM Journal on Numerical Analysis, v.24 n.2, p.407-434, April 1987 [doi>10.1137/0724031]
• 3: Peter N. Brown , G. D. Byrne , A. C. Hindmarsh, VODE: a variable-coefficient ODE solver, SIAM Journal on Scientific and Statistical Computing, v.10 n.5, p.1038-1051, Sept. 1989 [doi>10.1137/0910062]
• 4: Brown, P. N. and Hindmarsh, A. C. 1989. Reduced storage matrix methods in stiff ODE systems. J. Appl. Math. Comp. 31, 49--91.
• 5: Peter N. Brown , Alan C. Hindmarsh , Linda R. Petzold, Using Krylov methods in the solution of large-scale differential-algebraic systems, SIAM Journal on Scientific Computing, v.15 n.6, p.1467-1488, Nov. 1994 [doi>10.1137/0915088]
• 6: Peter N. Brown , Alan C. Hindmarsh , Linda R. Petzold, Consistent Initial Condition Calculation for Differential-Algebraic Systems, SIAM Journal on Scientific Computing, v.19 n.5, p.1495-1512, Sept. 1998 [doi>10.1137/S1064827595289996]
• 7: Peter N. Brown , Youcef Saad, Hybrid Krylov methods for nonlinear systems of equations, SIAM Journal on Scientific and Statistical Computing, v.11 n.3, p.450-481, May 1990 [doi>10.1137/0911026]
• 8: Peter N. Brown , Carol S. Woodward, Preconditioning Strategies for Fully Implicit Radiation Diffusion with Material-Energy Transfer, SIAM Journal on Scientific Computing, v.23 n.2, p.499-516, 2001 [doi>10.1137/S106482750037295X]
• 9: Byrne, G. D. 1992. Pragmatic experiments with Krylov methods in the stiff ODE setting. In Computational Ordinary Differential Equations, J. Cash and I. Gladwell, Eds. Oxford University Press, Oxford, U.K., 323--356.
• 10: G. D. Byrne , A. C. Hindmarsh, A Polyalgorithm for the Numerical Solution of Ordinary Differential Equations, ACM Transactions on Mathematical Software (TOMS), v.1 n.1, p.71-96, March 1975 [doi>10.1145/355626.355636]
• 11: Byrne, G. D. and Hindmarsh, A. C. 1998. User documentation for PVODE, an ODE solver for parallel computers. Tech. rep. UCRL-ID-130884. Lawrence Livermore National Laboratory, Livermore, CA.
• 12: George D. Byrne , Alan C. Hindmarsh, PVODE, an ODE Solver for Parallel Computers, International Journal of High Performance Computing Applications, v.13 n.4, p.354-365, November 1999 [doi>10.1177/109434209901300405]
• 13: Yang Cao , Shengtai Li , Linda Petzold , Radu Serban, Adjoint Sensitivity Analysis for Differential-Algebraic Equations: The Adjoint DAE System and Its Numerical Solution, SIAM Journal on Scientific Computing, v.24 n.3, p.1076-1089, 2002 [doi>10.1137/S1064827501380630]
• 14: Cohen, S. D. and Hindmarsh, A. C. 1994. CVODE user guide. Tech. rep. UCRL-MA-118618. Lawrence Livermore National Laboratory, Livermore, CA.
• 15: Scott D. Cohen , Alan C. Hindmarsh, CVODE, a stiff/nonstiff ODE solver in C, Computers in Physics, v.10 n.2, p.138-143, March/April 1996
• 16: Collier, A. M., Hindmarsh, A. C., Serban, R., and Woodward, C. S. 2004. User documentation for KINSOL v2.2.1. LLNL Tech. rep. UCRL-SM-208116. Lawrence Livermore National Laboratory, Livermore, CA.
• 17: Curtis, A. R., Powell, M. J. D., and Reid, J. K. 1974. On the estimation of sparse Jacobian matrices. J. Inst. Math. Applic. 13, 117--119.
• 18: Dembo, R. S., Eisenstat, S. C., and Steihaug, T. 1982. Inexact Newton methods. SIAM J. Numer. Anal. 19, 400--408.
• 19: J. E. Dennis, Jr. , Robert B. Schnabel, Numerical Methods for Unconstrained Optimization and Nonlinear Equations (Classics in Applied Mathematics, 16), Soc for Industrial & Applied Math, 1996
• 20: Stanley C. Eisenstat , Homer F. Walker, Choosing the forcing terms in an inexact Newton method, SIAM Journal on Scientific Computing, v.17 n.1, p.16-32, Jan. 1996 [doi>10.1137/0917003]
• 21: William F. Feehery , John E. Tolsma , Paul I. Barton, Efficient sensitivity analysis of large-scale differential-algebraic systems, Applied Numerical Mathematics, v.25 n.1, p.41-54, Oct. 1997 [doi>10.1016/S0168-9274(97)00050-0]
• 22: Hairer, E. and Wanner, G. 1991. Solving Ordinary Differential Equations II, Stiff and Differential-Algebraic Problems. Springer-Verlag, Berlin, Germany.
• 23: Hiebert, K. L. and Shampine, L. F. 1980. Implicitly defined output points for solutions of ODEs. Tech. rep. SAND80-0180. Sandia National Laboratories, Albuquerque, NM.
• 24: Hindmarsh, A. C. 1992. Detecting stability barriers in BDF solvers. In Computational Ordinary Differential Equations, J. Cash and I. Gladwell, Eds. Oxford University Press, Oxford, U.K., 87--96.
• 25: Alan C. Hindmarsh, Avoiding BDF stability barriers in the MOL solution of advection-dominated problems, Applied Numerical Mathematics, v.17 n.3, p.311-318, July 1995 [doi>10.1016/0168-9274(95)00036-T]
• 26: Hindmarsh, A. C. 2000. The PVODE and IDA algorithms. Tech. rep. UCRL-ID-141558. Lawrence Livermore National Laboratory, Livermore, CA.
• 27: Hindmarsh, A. C. and Serban, R. 2004a. User documentation for CVODE v2.2.1. LLNL Tech. rep. UCRL-SM-208108. Lawrence Livermore National Laboratory, Livermore, CA.
• 28: Hindmarsh, A. C. and Serban, R. 2004b. User documentation for CVODES v2.2.1. LLNL Tech. rep. UCRL-SM-208111. Lawrence Livermore National Laboratory, Livermore, CA.
• 29: Hindmarsh, A. C. and Serban, R. 2004c. User documentation for IDA v2.2.1. LLNL Tech. rep. UCRL-SM-208112. Lawrence Livermore National Laboratory, Livermore, CA.
• 30: K. R. Jackson , R. Sacks-Davis, An Alternative Implementation of Variable Step-Size Multistep Formulas for Stiff ODEs, ACM Transactions on Mathematical Software (TOMS), v.6 n.3, p.295-318, Sept. 1980 [doi>10.1145/355900.355903]
• 31: Jones, J. E. and Woodward, C. S. 2001. Newton-Krylov-multigrid solvers for large-scale, highly heterogeneous, variably saturated flow problems. Adv. Water Resourc. 24, 763-- 774.
• 32: Kelley, C. T. 1995. Iterative Methods for Solving Linear and Nonlinear Equations. SIAM Press, Philadelphia, PA.
• 33: Lee, S. L., Hindmarsh, A. C., and Brown, P. N. 2000. User documentation for SensPVODE, a variant of PVODE for sensitivity analysis. Tech. Rep. UCRL-MA-140211. Lawrence Livermore National Laboratory, Livermore, CA.
• 34: Steven L. Lee , Carol S. Woodward , Frank Graziani, Analyzing radiation diffusion using time-dependent sensitivity-based techniques, Journal of Computational Physics, v.192 n.1, p.211-230, 20 November 2003 [doi>10.1016/j.jcp.2003.07.031]
• 35: Timothy Maly , Linda R. Petzold, Numerical methods and software for sensitivity analysis of differential-algebraic systems, Applied Numerical Mathematics, v.20 n.1-2, p.57-79, Feb. 1996 [doi>10.1016/0168-9274(95)00117-4]
• 36: Radhakrishnan, K. and Hindmarsh, A. C. 1993. Description and use of LSODE, the Livermore solver for ordinary differential equations. Tech. rep. UCRL-ID-113855. Lawrence Livermore National Laboratory, Livermore, CA.
• 37: T. D. Rognlien , X. Q. Xu , A. C. Hindmarsh, Application of parallel implicit methods to edge-plasma numerical simulations, Journal of Computational Physics, v.175 n.1, p.249-268, January 1, 2002 [doi>10.1006/jcph.2001.6944]
• 38: Youcef Saad , Martin H Schultz, GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM Journal on Scientific and Statistical Computing, v.7 n.3, p.856-869, July 1986 [doi>10.1137/0907058]
• 39: Serban, R. and Hindmarsh, A. C. 2005. CVODES, the Sensitivity-enabled ODE solver in SUNDIALS. In Proceedings of the 2005 ASME International Design Engineering Technical Conference (Long Beach, CA, Sep. 24--28). Also published as 2005 LLNL Tech. rep. UCRL-PROC-21030, Lawrence Livermore National Laboratory, Livermore, CA.
• 40: Woodward, C. S. 1998. A Newton-Krylov-multigrid solver for variably saturated flow problems. In Proceedings of the Twelfth International Conference on Computational Methods in Water Resources, vol. 2. Computational Mechanics Publications, Southampton, U.K., 609--616.
• 41: Woodward, C. S., Grant, K. E., and Maxwell, R. 2002. Applications of sensitivity analysis to uncertainty quantification for variably saturated flow. In Computational Methods in Water Resources, S. M. Hassanizadeh, R. J. Schotting, W. G. Gray, and G. F. Pinder, Eds. Elsevier, Amsterdam, The Netherlands, 73--80.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.5 Roots of Nonlinear Equations
          Subjects: Iterative methods; Convergence
      G.1.7 Ordinary Differential Equations
          Subjects: Differential-algebraic equations; Stiff equations; Multistep and multivalue methods

Keywords:
DAEs, ODEs, nonlinear systems, sensitivity analysis