Krylov-Newton algorithm

BifurcationKit is built upon the newton algorithm for solving (large-dimensional) nonlinear equations

\[F(x)=0\in\mathbb R^n,\quad x\in\mathbb R^n.\]

Writing $J(x)\in\mathcal L(\mathbb R^n)$ the jacobian, the algorithm reads

\[x_{n+1} = x_n - J(x_n)^{-1}F(x_n)\]

with initial guess $x_0$.

The crux of the algorithm is to solve the linear system in $y$:

\[J(x_n)\cdot y = F(x_n).\]

To this end, we never form $J^{-1}$ like with pinv(J) but solve the linear system directly.

Space of solutions

For the algorithm to be defined, a certain number of operations on x need to be available. If you pass x::AbstractArray, you should not have any problem. Otherwise, your x must comply with the requirements listed in Requested methods for Custom State.

Different Jacobians

There are basically two ways to specify the jacobian:

  1. Matrix based
  2. Matrix-free.

In case you pass a matrix (in effect an AbstractMatrix like a sparse one,...), you can use the default linear solver from LinearAlgebra termed the backslash operator \. This is a direct method. This is the case 1 above.

Another possibility is to pass a function J(dx) and to use iterative linear solvers. In this case, this is termed a Krylov-Newton method. This is the case 2 above. In comparison to the Matrix-based case, there is no restriction to the number of unknowns $n$.

The available linear solvers are explained in the section Linear solvers (LS).

One can find a full description of the Krylov-Newton method in the API.

Simple example

Here is a quick example to show how the basics work. In particular, the problem generates a matrix based jacobian using automatic differentiation.

using BifurcationKit
F(x, p) = x.^3 .- 1
x0 = rand(10)
prob = BifurcationProblem(F, x0, nothing)
sol = newton(prob, NewtonPar(verbose = true))
NonLinearSolution{Vector{Float64}, BifurcationProblem{BifFunction{typeof(Main.F), BifurcationKit.var"#6#21"{typeof(Main.F)}, Nothing, BifurcationKit.var"#4#19"{typeof(Main.F)}, Nothing, BifurcationKit.var"#9#25"{BifurcationKit.var"#d1Fad#23"{typeof(Main.F)}}, BifurcationKit.var"#11#27", BifurcationKit.var"#13#29", BifurcationKit.var"#15#31", Bool, Float64}, Vector{Float64}, Nothing, Setfield.IdentityLens, typeof(BifurcationKit.plotDefault), typeof(BifurcationKit.recordSolDefault)}, Vector{Float64}, Int64}([1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.00000000000028, 1.0], ┌─ Bifurcation Problem with uType Vector{Float64}
├─ inplace:  false
├─ Symmetric: false
└─ Parameter: p, [2.9105792260443564, 2.145048373170016e6, 635569.5817749642, 188316.60654993585, 55797.206492829384, 16532.19909699455, 4898.122909613257, 1450.989429991425, 429.6171074142654, 126.98989008025356, 37.327443610429114, 10.773800934397054, 2.934531571808459, 0.6657133092242015, 0.08469006290812812, 0.0021850079681468115, 1.5875655763331054e-6, 8.399947404313934e-13], true, 17, 17)

Example

The (basic) tutorial Temperature model (Simplest example) presents all cases (direct and iterative ones).