7.1. Introduction

KINSOL is part of a software family called SUNDIALS: SUite of Nonlinear and DIfferential/ALgebraic equation Solvers [70]. 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 [25]. 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) [106], FGMRES (Flexible Generalized Minimum RESidual) [105], Bi-CGStab (Bi-Conjugate Gradient Stabilized) [131], TFQMR (Transpose-Free Quasi-Minimal Residual) [56], and PCG (Preconditioned Conjugate Gradient) [65] 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, 40] and the threaded sparse direct solver, SuperLU_MT [9, 42, 89], 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.1.0

Major Features

Created shared user interface functions for ARKODE to allow more uniform control over time-stepping algorithms, improved extensibility, and simplified code maintenance. The corresponding stepper-specific user-callable functions are now deprecated and will be removed in a future major release.

Added CMake infrastructure that enables externally maintained addons/plugins to be optionally built with SUNDIALS. See Contributing for details.

New Features and Enhancements

Added support for Kokkos Kernels v4.

Added the following Runge-Kutta Butcher tables

  • ARKODE_FORWARD_EULER_1_1

  • ARKODE_RALSTON_EULER_2_1_2

  • ARKODE_EXPLICIT_MIDPOINT_EULER_2_1_2

  • ARKODE_BACKWARD_EULER_1_1

  • ARKODE_IMPLICIT_MIDPOINT_1_2

  • ARKODE_IMPLICIT_TRAPEZOIDAL_2_2

Added the following MRI coupling tables

  • ARKODE_MRI_GARK_FORWARD_EULER

  • ARKODE_MRI_GARK_RALSTON2

  • ARKODE_MRI_GARK_RALSTON3

  • ARKODE_MRI_GARK_BACKWARD_EULER

  • ARKODE_MRI_GARK_IMPLICIT_MIDPOINT

  • ARKODE_IMEX_MRI_GARK_EULER

  • ARKODE_IMEX_MRI_GARK_TRAPEZOIDAL

  • ARKODE_IMEX_MRI_GARK_MIDPOINT

Added ARKodeButcherTable_ERKIDToName() and ARKodeButcherTable_DIRKIDToName() to convert a Butcher table ID to a string representation.

Added the function ARKodeSetAutonomous() in ARKODE to indicate that the implicit right-hand side function does not explicitly depend on time. When using the trivial predictor, an autonomous problem may reuse implicit function evaluations across stage solves to reduce the total number of function evaluations.

Users may now disable interpolated output in ARKODE by passing ARK_INTERP_NONE to ARKodeSetInterpolantType(). When interpolation is disabled, rootfinding is not supported, implicit methods must use the trivial predictor (the default option), and interpolation at stop times cannot be used (interpolating at stop times is disabled by default). With interpolation disabled, calling ARKodeEvolve() in ARK_NORMAL mode will return at or past the requested output time (setting a stop time may still be used to halt the integrator at a specific time). Disabling interpolation will reduce the memory footprint of an integrator by two or more state vectors (depending on the interpolant type and degree) which can be beneficial when interpolation is not needed e.g., when integrating to a final time without output in between or using an explicit fast time scale integrator with an MRI method.

Added “Resize” capability to ARKODE’s SPRKStep time-stepping module.

Enabled the Fortran interfaces to build with 32-bit sunindextype.

Bug Fixes

Updated the CMake variable HIP_PLATFORM default to amd as the previous default, hcc, is no longer recognized in ROCm 5.7.0 or newer. The new default is also valid in older version of ROCm (at least back to version 4.3.1).

Renamed the DPCPP value for the SUNDIALS_GINKGO_BACKENDS CMake option to SYCL to match Ginkgo’s updated naming convention.

Changed the CMake version compatibility mode for SUNDIALS to AnyNewerVersion instead of SameMajorVersion. This fixes the issue seen here.

Fixed a CMake bug that caused an MPI linking error for our C++ examples in some instances. Fixes GitHub Issue #464.

Fixed the runtime library installation path for windows systems. This fix changes the default library installation path from CMAKE_INSTALL_PREFIX/CMAKE_INSTALL_LIBDIR to CMAKE_INSTALL_PREFIX/CMAKE_INSTALL_BINDIR.

Fixed conflicting .lib files between shared and static libs when using MSVC on Windows

Fixed invalid SUNDIALS_EXPORT generated macro when building both shared and static libs.

Fixed a bug in some Fortran examples where c_null_ptr was passed as an argument to a function pointer instead of c_null_funptr. This caused compilation issues with the Cray Fortran compiler.

Fixed a bug in the HIP execution policies where WARP_SIZE would not be set with ROCm 6.0.0 or newer.

Fixed a bug that caused error messages to be cut off in some cases. Fixes GitHub Issue #461.

Fixed a memory leak when an error handler was added to a SUNContext. Fixes GitHub Issue #466.

Fixed a bug where MRIStepEvolve() would not handle a recoverable error produced from evolving the inner stepper.

Added missing SetRootDirection and SetNoInactiveRootWarn functions to ARKODE’s SPRKStep time-stepping module.

Fixed a bug in ARKodeSPRKTable_Create() where the coefficient arrays were not allocated.

Fix bug on LLP64 platforms (like Windows 64-bit) where KLU_INDEXTYPE could be 32 bits wide even if SUNDIALS_INT64_T is defined.

Check if size of SuiteSparse_long is 8 if the size of sunindextype is 8 when using KLU.

Fixed several build errors with the Fortran interfaces on Windows systems.

Deprecation Notices

Numerous ARKODE stepper-specific functions are now deprecated in favor of ARKODE-wide functions.

Deprecated the ARKStepSetOptimalParams function. Since this function does not have an ARKODE-wide equivalent, instructions have been added to the user guide for how to retain the current functionality using other user-callable functions.

The unsupported implementations of N_VGetArrayPointer and N_VSetArrayPointer for the hypre and PETSc vectors are now deprecated. Users should access the underlying wrapped external library vector objects instead with N_VGetVector_ParHyp and N_VGetVector_Petsc, respectively.

For changes in prior versions of SUNDIALS see §15.

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 [39]. 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_Vector module shared among the various components of SUNDIALS, and details on the four N_Vector implementations provided with SUNDIALS.

  • Chapter §9 gives a brief overview of the generic SUNMatrix module shared among the various components of SUNDIALS, and details on the SUNMatrix implementations provided with SUNDIALS.

  • Chapter §10 gives a brief overview of the generic SUNLinearSolver module shared among the various components of SUNDIALS. This chapter contains details on the SUNLinearSolver implementations provided with SUNDIALS. The chapter also contains details on the SUNLinearSolver implementations 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.