7.1. Introduction
KINSOL is part of a software family called SUNDIALS: SUite of Nonlinear and DIfferential/ALgebraic equation Solvers [81]. This suite consists of CVODE, ARKODE, KINSOL, and IDA, and variants of these with sensitivity analysis capabilities.
KINSOL is a general-purpose nonlinear system solver based on Newton-Krylov solver technology. A fixed point iteration is also included with the release of KINSOL v.2.8.0 and higher.
7.1.1. Historical Background
The first nonlinear solver packages based on Newton-Krylov methods were written in Fortran. In particular, the NKSOL package, written at LLNL, was the first Newton-Krylov solver package written for solution of systems arising in the solution of partial differential equations [28]. This Fortran code made use of Newton’s method to solve the discrete nonlinear systems and applied a preconditioned Krylov linear solver for solution of the Jacobian system at each nonlinear iteration. The key to the Newton-Krylov method was that the matrix-vector multiplies required by the Krylov method could effectively be approximated by a finite difference of the nonlinear system-defining function, avoiding a requirement for the formation of the actual Jacobian matrix. Significantly less memory was required for the solver as a result.
In the late 1990s, there was a push at LLNL to rewrite the nonlinear solver in C and port it to distributed memory parallel machines. Both Newton and Krylov methods are easily implemented in parallel, and this effort gave rise to the KINSOL package. KINSOL is similar to NKSOL in functionality, except that it provides for more options in the choice of linear system methods and tolerances, and has a more modular design to provide flexibility for future enhancements.
At present, KINSOL may utilize a variety of Krylov methods provided in SUNDIALS. These methods include the GMRES (Generalized Minimal RESidual) [122], FGMRES (Flexible Generalized Minimum RESidual) [121], Bi-CGStab (Bi-Conjugate Gradient Stabilized) [157], TFQMR (Transpose-Free Quasi-Minimal Residual) [64], and PCG (Preconditioned Conjugate Gradient) [76] linear iterative methods. As Krylov methods, these require little matrix storage for solving the Newton equations as compared to direct methods. However, the algorithms allow for a user-supplied preconditioner, and, for most problems, preconditioning is essential for an efficient solution. For very large nonlinear algebraic systems, the Krylov methods are preferable over direct linear solver methods, and are often the only feasible choice. Among the Krylov methods in SUNDIALS, we recommend GMRES as the best overall choice. However, users are encouraged to compare all options, especially if encountering convergence failures with GMRES. Bi-CGStab and TFQMR have an advantage in storage requirements, in that the number of workspace vectors they require is fixed, while that number for GMRES depends on the desired Krylov subspace size. FGMRES has an advantage in that it is designed to support preconditioners that vary between iterations (e.g., iterative methods). PCG exhibits rapid convergence and minimal workspace vectors, but only works for symmetric linear systems.
For the sake of completeness in functionality, direct linear system solvers are included in KINSOL. These include methods for both dense and banded linear systems, with Jacobians that are either user-supplied or generated internally by difference quotients. KINSOL also includes interfaces to sparse direct solvers, including KLU [4, 44] and the threaded sparse direct solver, SuperLU_MT [9, 46, 102], among others (see Chapter §10 for further details).
In the process of translating NKSOL into C, the overall KINSOL organization has been changed considerably.
One key feature of the KINSOL organization is that a separate module devoted to vector operations was created.
This module facilitated extension to multiprosessor environments with minimal impact on the rest of the solver. The
vector module design is shared across the SUNDIALS suite. This N_Vector module is written in terms of
abstract vector operations with the actual routines attached by a particular implementation (such as serial or parallel)
of N_Vector. This abstraction allows writing the SUNDIALS solvers in a manner independent of the actual
N_Vector implementation (which can be user-supplied), as well as allowing more than one N_Vector module linked
into an executable file. SUNDIALS (and thus KINSOL) is supplied with serial, MPI-parallel, OpenMP
and Pthreads thread-parallel N_Vector implementations, as well as multiple N_Vector
implementations designed to leverage GPU architectures (see Chapter §8 for
further details).
There are several motivations for choosing the C language for KINSOL. First, a general movement away from Fortran and toward C in scientific computing was apparent. Second, the pointer, structure, and dynamic memory allocation features in C are extremely useful in software of this complexity, with the great variety of method options offered. Finally, we prefer C over C++ for KINSOL because of the wider availability of C compilers, the potentially greater efficiency of C, and the greater ease of interfacing the solver to applications written in Fortran.
7.1.2. Changes to SUNDIALS in release 7.7.0
New Features and Enhancements
The default number of stages for the SSP Runge-Kutta methods
ARKODE_LSRK_SSP_S_2 and ARKODE_LSRK_SSP_S_3 in
LSRKStep were changed from 10 and 9, respectively, to their minimum allowable
values of 2 and 4. Users may revert to the previous values by calling
LSRKStepSetNumSSPStages().
Added the optional function ARKodeInit() to ARKODE to enable data
allocation before the first call to ARKodeEvolve() (but after all other
optional input routines have been called), to support users who measure memory
usage before beginning a simulation.
Added the function ARKodeGetStageIndex() that returns the index of the
stage currently being processed, and the total number of stages in the method,
for users who wish to compute auxiliary quantities in their IVP right-hand side
functions during some stages and not others (e.g., in all but the first or last
stage).
Added the functions ARKodeGetLastTime() and ARKodeGetLastState()
to return the last successful time and state achieved by ARKODE, respectively.
ARKODE now allows users to supply functions that will be called before each
internal time step attempt (ARKodeSetPreStepFn()), after each successful
time step (ARKodeSetPostStepFn()), before right-hand side routines are
called on an updated state (ARKodeSetPreRhsFn()), and/or once each
internal step/stage is computed (ARKodeSetPostprocessStepFn()/
ARKodeSetPostprocessStageFn()). These are considered advanced
functions, as they should treat the state vector as read-only, otherwise all
theoretical guarantees of solution accuracy and stability will be lost. As a
result of these new functions, the values of multiple ARKODE return codes (e.g.,
ARK_INTERP_FAIL) have been updated; users who key off of the named constants
will not be affected, but users who rely on the values themselves should update
their codes accordingly.
Note to users utilizing the previously undocumented
ARKodeSetPostprocessStepFn() function, the supplied function is now
called on the newly computed state vector for all step attempts not just
successful steps. To obtain the previous behavior of only calling a function on
successful steps, switch to using ARKodeSetPostStepFn().
Added SUNLogger_Set{Error,Warning,Info,Debug}File functions to allow setting
logger output streams with a FILE*.
Updated the Kokkos N_Vector to support Kokkos 5.x versions.
Bug Fixes
Fixed a CMake bug where the SuperLU_MT interface would not be built and
installed without setting the SUPERLUMT_WORKS option to TRUE.
Fixed the embedded coefficients for the ARKODE_TSITOURAS_7_4_5 Butcher
table.
Fixed a bug in LSRKStep where an incorrect state vector could be passed to a
user-supplied dominant eigenvalue function on the first step unless the output
vector passed to ARKodeEvolve() contained the initial condition and when
an eigenvalue estimate is requested on the first step in a subsequent call to
ARKodeEvolve() unless the output vector passed contained the most
recently returned solution.
Fixed a potential bug in LSRKStep’s ARKODE_LSRK_SSP_S_3 method,
where a real number was used instead of an integer, potentially resulting in a
rounding error.
Fixed a bug in MRIStep for estimating the first “slow” time step in an adaptive multirate calculation.
Fixed a bug in MRIStep when using a custom inner integrator that relies on the
input state being the initial condition for the fast integration rather than
retaining the result from the last inner integration or most recent reset call
and the output vector passed to ARKodeEvolve() does not contain the
initial condition on the first call or the last returned solution on subsequent
calls.
Added a missing call to SUNNonlinSolSetup() in MRIStep when using an
IMEX-MRI-SR method.
Fixed a bug in the ARKODE discrete adjoint checkpointing where an incorrect
state would be stored on the first step if the output vector passed to
ARKodeEvolve() did not contain the initial condition on the first call.
Removed extraneous copy of output vector when using ARKODE in ARK_ONE_STEP
mode.
Removed an extraneous copy of the output vector in each step with SplittingStep.
Fixed a bug in logging output from ARKODE, where for some time stepping modules, the current “time” output in the logger was incorrect.
Fixed a bug where passing an empty string to
SUNLogger_Set{Error,Warning,Info,Debug}Filename did not disable the
corresponding logging stream Issue #844.
Deprecation Notices
The CVodeSetMonitorFn and CVodeSetMonitorFrequency functions have been
deprecated and will be removed in the next major release.
Several CMake options have been deprecated in favor of namespaced versions
prefixed with SUNDIALS_ to avoid naming collisions in applications that
include SUNDIALS directly within their CMake builds. Additionally, a consistent
naming convention (SUNDIALS_ENABLE) is now used for all boolean options. The
table below lists the old CMake option names and the new replacements.
Old Option |
New Option |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Following the updated CMake options, the macros listed below have been deprecated and replaced with versions that align with the new CMake options.
Old Macro |
New Macro |
|
|
|
|
|
|
For changes in prior versions of SUNDIALS see §18.
7.1.3. Reading this User Guide
This user guide is a combination of general usage instructions and specific examples. We expect that some readers will want to concentrate on the general instructions, while others will refer mostly to the examples, and the organization is intended to accommodate both styles.
There are different possible levels of usage of KINSOL. The most casual user, with a small nonlinear system, can
get by with reading all of Chapter §7.2, then Chapter :numref:KINSOL.Usage.CC through
§7.4 only, and looking at examples in [42]. In a different
direction, a more expert user with a nonlinear system may want to (a) use a package preconditioner
(§7.4.5), (b) supply his/her own Jacobian or preconditioner routines
(§7.4.4), (c) supply a new N_Vector module
(Chapter §8), or even (d) supply a different linear solver module
(§7.4.3.2 and Chapter §10).
The structure of this document is as follows:
In Chapter §7.2, we provide short descriptions of the numerical methods implemented by KINSOL for the solution of nonlinear systems.
The following chapter describes the software organization of the KINSOL solver (§7.3).
Chapter :numref:KINSOL.Usage.CC is the main usage document for KINSOL for C applications. It includes a complete description of the user interface for the solution of nonlinear algebraic systems.
Chapter §8 gives a brief overview of the generic
N_Vectormodule shared among the various components of SUNDIALS, and details on the fourN_Vectorimplementations provided with SUNDIALS.Chapter §9 gives a brief overview of the generic
SUNMatrixmodule shared among the various components of SUNDIALS, and details on theSUNMatriximplementations provided with SUNDIALS.Chapter §10 gives a brief overview of the generic
SUNLinearSolvermodule shared among the various components of SUNDIALS. This chapter contains details on theSUNLinearSolverimplementations provided with SUNDIALS. The chapter also contains details on theSUNLinearSolverimplementations provided with SUNDIALS that interface with external linear solver libraries.Finally, in the appendices, we provide detailed instructions for the installation of KINSOL, within the structure of SUNDIALS (Appendix §1.1), as well as a list of all the constants used for input to and output from KINSOL functions (Appendix §7.5).
Finally, the reader should be aware of the following notational conventions in this user guide: program listings and
identifiers (such as KINInit) within textual explanations appear in typewriter type style; fields in C
structures (such as content) appear in italics; and packages or modules are written in all capitals. Usage and
7.1.4. SUNDIALS License and Notices
All SUNDIALS packages are released open source, under the BSD 3-Clause license for more details see the LICENSE and NOTICE files provided with all SUNDIALS packages.
7.1.5. Acknowledgments
We wish to acknowledge the contributions to previous versions of the KINSOL code and user guide by Allan G. Taylor.