The Nonlinear Solvers and Differential Equations (NSDE) project is focused on research and development of nonlinear solvers and sensitivity analysis techniques for nonlinear, time-dependent, and steady-state partial differential equations. We are implementing our methods into a suite of software codes: CVODE/PVODE for systems of ordinary differential equations, IDA for differential-algebraic systems, and KINSOL for nonlinear systems of equations. Current and future research is concentrating on the use of our nonlinear solvers and sensitivity techniques in the development of uncertainty quantification, model evaluation, and optimization techniques for nonlinear systems, as well as the combination of optimization under uncertainty.
Our research is sponsored by the DOE Office of Science through the Mathematical, Information, and Computer Sciences Division Applied Mathematics Sciences Program and through the Scientific Discovery through Advanced Computing program. We are also funded by the DOE's Accelerated Strategic Computing Initiative (ASCI) as part of the DOE's stockpile stewardship program.
For software, see the current SUNDIALS project.
Overview of Nonlinear Solvers Research
Scope of the Project
With the advent of powerful, massively parallel supercomputers and highly effective solution methods, the solution to fully implicit formulations of many application models has become possible, whereas in the recent past, solving these formulations had been considered intractable. Solutions to fully implicit formulations provide more accuracy and, due to the ability to take larger time steps in resolving time-dependent behavior, can be faster to solve than explicit formulations.
NSDE project members conduct research in the solution of implicit nonlinear differential equations discretized on large, three-dimensional meshes and arising in the LLNL mission areas of radiation transport and groundwater flow. Both of these applications require the solution of large systems of coupled, nonlinear equations. Current project research leverages advances in each application area to develop better solvers for both. This work examines parallel solution strategies for nonlinear discrete systems arising from solving a steady-state problem or from solving a time step within an implicit, time-dependent problem. Investigators also pursue solution strategies for the linear systems arising in each nonlinear iteration.
Algorithmic Research Areas
A primary focus has been in the application of Newton-Krylov methods for solving the nonlinearities in the applications of interest. These methods can result in quadratic convergence of the nonlinear iteration, provided the linear systems have been solved sufficiently accurately. One difficulty, however, arises in iterating the linear solver to a low enough tolerance, a requirement that often necessitates an efficient and scalable preconditioner for the Krylov method.
Project members have been investigating various multigrid methods applied as preconditioners in the solution of the linear Jacobian systems at each nonlinear iteration. In particular, they are studying the choice of approximation of the Jacobian as a preconditioning matrix, and ways of selecting the best approximation. They have also been investigating the use of stale values of tabulated data in the Krylov method matrix-vector multiply.
Additionally, for both applications under consideration, NSDE project members are investigating the viability of nonlinear multigrid schemes such as the Full Approximation Storage (FAS) method, for problems of interest at the laboratory. These schemes provide an alternative to the Newton-Krylov approach for solving nonlinear systems. While FAS methods may require less storage than Newton-Krylov schemes, they are not as fully understood.
Project members are examining these methods for the specified applications, and comparing the resulting performance to that of the Newton-Krylov-multigrid methods. As the success of FAS methods can be problem-dependent, project researchers are trying to determine the best method for each of the application areas noted earlier. Specific research topics include: determining the radius of convergence of the FAS method; developing techniques for choosing the coarse grid operators, and coarsening grid-related data as part of the coarse grid operator formulation.
Overview of Sensitivity Analysis Research
Computer-modeled simulations are used widely in the investigation of complex physical systems. These models typically contain parameters, and the numerical results can be highly sensitive to small changes in the parameter values. NSDE investigators evaluate two main approaches for estimating the first-order sensitivity of simulations with respect to model parameters: the forward sensitivity or tangent linear model method, and the backward or adjoint method.
For models comprised of ordinary differential equations and/or nonlinear algebraic equations, the project is developing forward sensitivity variants of the CASC parallel solvers PVODE, IDA and KINSOL. Forward sensitivity methods can be formulated in terms of an ODE, differential-algebraic equation or algebraic equation (for steady problems) for the solution sensitivities with respect to a fixed set of parameters. These new equations can be appended to the original system, and the resulting augmented system can be solved by the respective solver code. The additional sensitivity equations contain terms involving Jacobian matrix-vector products and partial derivatives. Finite differences can be used to estimate these terms.
For some problems, however, this technique does not work. In particular, difficulties can arise in applications where the solution components are badly scaled. Such shortcomings motivate researchers to use automatic differentiation (AD) as an efficient and exact technique for evaluating various terms in the sensitivity equations. AD can also be used to compute the forward sensitivities in a general simulation code by differentiating the entire code with respect to a specified set of parameters. This more general approach, however, is usually less efficient because it does not exploit the user's knowledge of the computational requirements of the simulation.
In cases where the sensitivity of the solution is needed with respect to a large number of parameters, adjoint methods may prove more useful. For the PVODE solver suite, part of this approach involves formulating and solving adjoint sensitivity equations for the respective solver. Analogous to the approach for the forward sensitivities, finite differences or AD can be used to evaluate the adjoint sensitivity equations within the solver. Alternatively, a reverse-mode of AD can be applied to differentiate a simulation code with respect to the model parameters. Both approaches rely on the ability to efficiently store or recompute the simulation in the forward direction (e.g., using some type of interpolation scheme). In particular, it may be possible to store only a subset of the simulation results (a reduced basis) and to develop interpolation schemes that express the interpolated solution as a member of this reduced basis.