Expand description
Solvers of F(z) = 0 in double-, quad- and octo-double precision, written over a Problem: a problem gives its
residual and its exact Jacobian in one of multidouble’s precisions (Precision: Double, Quad, Octo),
and the solvers here need nothing else of it. The multiple-shooting layout of the crate multishoot is one such
problem.
newton: the Newton step and the damped Newton loop, and the chord and Shamanskii methods that reuse its factors;gcr: a preconditioned Krylov solver (GMRES in its GCR form) on exact Jacobian-vector products, and the Newton method whose steps it refines from an approximate factorization;lm: the Levenberg-Marquardt method, for starts where Newton’s method stalls or its Jacobian is singular;anm: the asymptotic numerical method, the Taylor series of a solution branch in the problem’s parameter;predict: predictors for continuation: Lagrange extrapolation, the cubic Hermite, and the exact tangent;singularity: the nearest singularities of a series from its coefficients: Pade poles that recur across the approximants’ orders, the root test’s radius, the ratio method and a recurrence for a conjugate pair;subspace: the weakest singular directions of the Jacobian, Newton’s method with them removed from its steps, and the sensitivities of single unknowns to the residual;winding: the number and the places of the zeros of an analytic function inside a polygon, by the argument principle, and Muller’s method for one zero;prec: helpers for states held as part arrays in any of the precisions.
A problem is its residual and its exact Jacobian. Here x^2 = 2 in double-double, solved by the damped Newton loop:
use multisolver::multidouble::linalg::ld_for;
use multisolver::newton::{newton, NewtonOpts};
use multisolver::{Double, Problem, DD};
struct Sqrt2;
impl Problem<Double> for Sqrt2 {
fn len(&self) -> usize {
1
}
fn residual(&self, z: &[&[f64]], _par: bool) -> Result<Vec<DD>, String> {
let x = DD { hi: z[0][0], lo: z[1][0] };
Ok(vec![x * x - DD::from_f64(2.0)])
}
fn jacobian(&self, z: &[&[f64]], _par: bool) -> Result<(Vec<Vec<f64>>, usize), String> {
let ld = ld_for(1);
let d = DD { hi: z[0][0], lo: z[1][0] }.mul_f(2.0);
let (mut hi, mut lo) = (vec![0.0; ld], vec![0.0; ld]);
(hi[0], lo[0]) = (d.hi, d.lo);
Ok((vec![hi, lo], ld))
}
}
let mut z = vec![vec![1.0], vec![0.0]];
let report = newton::<Double, _>(&Sqrt2, &mut z, &NewtonOpts::default()).unwrap();
let x = DD { hi: z[0][0], lo: z[1][0] };
assert!(report.converged && (x * x - DD::from_f64(2.0)).hi.abs() <= 1e-30);Re-exports§
pub use newton::NewtonOpts;pub use newton::NewtonReport;pub use multidouble;
Modules§
- anm
- The asymptotic numerical method (ANM): the Taylor series z(h) = sum_k z_k h^k of a solution branch of F(z, p0 + h) = 0 in the problem’s parameter, from a solution z_0 at p0 (Cochelin, Comput. Struct. 53 (1994) 1181; Cochelin, Damil and Potier-Ferry, Int. J. Numer. Methods Eng. 37 (1994) 1187).
- gcr
- A preconditioned Krylov solver on exact matrix-vector products, and the Newton method whose steps it refines.
- lm
- The Levenberg-Marquardt method on F(z) = 0, for any
Problem: each step solves (G + mu D) dz = -J^T F with G = J^T J and Marquardt’s scaling D = diag(G), and mu adapts to how well the step’s predicted decrease of |F|^2 / 2 matched the real one (the gain ratio; Madsen, Nielsen and Tingleff, Methods for Non-Linear Least Squares Problems, DTU 2004, section 3.2, after Nielsen 1999). Small mu gives Newton’s step, large mu a short step along the scaled gradient, so the method keeps going where the Jacobian is singular or Newton’s step overshoots. Near the root it hands over to Newton’s method, whose rate is quadratic, with LM’s tolerance. If Newton fails there (a singular Jacobian, or no convergence), LM goes on from its last accepted state and does not hand over again. The gain ratio is formed in f64 from |F|^2, which underflows below about 1e-150, so a run asked for a smaller tolerance needs the handover. - newton
- Newton’s method on F(z) = 0 in any precision, for any
Problem: the step dz = -J^-1 F with the exact Jacobian and a dense LU, and a damped loop. - prec
- Helpers for states held as PARTS arrays of f64 (part q of unknown i at
z[q][i]), in any of multidouble’s precisions (precision::Precision:Double,Quad,Octo), which the residual, the Jacobian and Newton’s method are written over. - predict
- Predictors for continuation in a parameter p: the start of the corrector at the next value of p, from the
solutions already found.
lagrangeextrapolates through the last few (p_i, z_i),hermiteis the cubic through two solutions and their tangents dz/dp, andtangentgives dz/dp at a solution exactly, as order 1 of the branch’s series (crate::anm): -J^-1 dF/dp with dF/dp from the residual’s series, not a difference quotient. - singularity
- The nearest singularities of a function from its Taylor coefficients: what limits the radius of a branch’s series
(
crate::anm::Branch). The root test’s radius from the coefficients’ envelope, the ratio method of Domb and Sykes (Proc. R. Soc. Lond. A 240 (1957) 214) with the singularity’s exponent, a two-term recurrence for a conjugate pair, and the poles of Pade approximants (Baker and Graves-Morris, Pade Approximants, 2nd ed., Cambridge University Press, 1996), which recur across the approximants’ orders where the function has a singularity and wander where it has none. - subspace
- The weakly determined directions of a problem at a point, and what uses them: the w weakest right singular directions of the Jacobian by inverse subspace iteration on (J^T J)^-1 and Rayleigh-Ritz, Newton’s method with its steps’ components along such a subspace removed, and the sensitivities y = J^-T e_k of single unknowns to the residual (a change dF of the residual moves unknown k by -y . dF).
- winding
- Counting and locating the zeros of an analytic function g(lambda) inside a closed polygon by the argument principle, from its values as (ln|g|, arg g): such as the mode count of a linearization’s determinant det M(lambda), whose zeros are the growth rates of a background’s modes (multishoot’s mode matrix).
Structs§
- DD
- Double
- Double-double:
DD,DV,Du,Jet<N>,DDLu; its dot product is the plain sum of double-double products - Octo
- Octo-double:
OD,OV,Ou,OJet<N>,ODLu,OdAcc - Quad
- Quad-double:
QD,QV,Qu,QJet<N>,QDLu,QdAcc - Recompute
JetOrdersbyResidualJet::residual_jet: each call evaluates the series of orders 0..=k on every vector given so far and returns its order k.
Traits§
- JetOrders
- The residual’s series in the parameter formed one order at a time, as the series of a branch needs it: order k once z_0..z_(k-1) are known, with z_k left out.
- Jvp
- A problem whose Jacobian-vector product J v can be formed without the Jacobian, exact to the precision P
- Precision
- One multi-double precision on the backend
S: its types, and the operations whose names differ between precisions. Every method delegates to the precision’s own method and returns its result bit for bit. - Problem
- A system F(z) = 0 of
len()equations in as many unknowns, evaluated in the precision P. The state z is held as P::PARTS part arrays of f64 (part q of unknown i atz[q][i]). - Residual
Jet - A problem whose equations depend on a parameter p, with the residual’s Taylor series in it: the coefficients of F(sum_k z_k h^k, p0 + h) in h, exact to the precision P
Type Aliases§
- Native
- The backend the build’s target features select at compile time (the cargo feature
portableforces the plain array).