γₙ constants for floating point error estimation, as in [Higham, Accuracy and Stability of Numerical Algorithms]

Estimate ||I + Q + Q^2 + … || (infinite sum) using a list of computed norm bounds norms[k] ≥ ||Q^k||.

Returns the maximum number of (structural) nonzeros in a row of A

Estimates the norms ||Q||, ||Q^2||, ... ||Q^m|| on U^0.

U is the matrix [ones(1,n-1); -I_(n-1,n-1)]. It is currently assumed that f*U==0 (i.e., all elements of f are equal).

f must be an interval vector.

The following constants may be specified as keyword arguments:

normQ, normE, normv0, normEF, normIEF, normN

otherwise they are computed (which may be slower).

e and f must be specified in case isintegralpreserving==false In case isintegralpreserving is true, they may be specified but they are then ignored.

Implementation note: currently we perform this computation one column at a time, to be able to scale (slowly) to cases with large size; for moderate sizes, it would indeed be better to do the computation all columns at the same time, in BLAS level 3.

Estimates ||Q||, ||Q^2||, ... ||Q^m|| on U^0 using L2 norm via BallArithmetic.

Computes matrix powers as BallMatrices, which automatically track rounding errors. Uses upperboundL2_opnorm for rigorous spectral norm bounds.

Arrays of bounds to $||Q^k||_{w → s} = \sup_{||f||_w=1} ||Q^k f||_s$ and to $||Q^k||_{w}$ coming theoretically from iterated DFLY inequalities (the "small matrix method").

Returns two arrays (strongs, norms) of length m: strongs[k] bounds $||Q^k f||_s$, norms[k] bounds $||Q^k f||$)

Estimate norms of powers from those on a coarser grid (see paper for details)

norms_of_powers_resolvent(m, ρ, M_inf)

Compute power norm bounds via certified resolvent on a contour. Returns norms[k] ≥ ||Q^k|_{complement of eigenvalue 1}||₂.

Uses the Cauchy integral bound: ||Q^k(I-P₁)|| ≤ ρ^{k+1} · M_∞

where ρ is the radius of the certified contour (must satisfy max|λⱼ| < ρ < 1 for j≥2) and M_∞ = sup_{z∈Γ} ||(zI-Q)⁻¹|| is the certified resolvent bound from certify_spectral_gap.

Array of "trivial" bounds for the powers of a DiscretizedOperator (on the whole space) coming from from ||Q^k|| ≤ ||Q||^k

Compute better and/or more estimates of power norms using the fact that $||Q^{k+h}|| ≤ ||Q^k|| \cdot ||Q^h||$. This uses multiplicativity, so it will not work for mixed norms, e.g., $||Q^k||_{s → w}$, or $||M^k|_{U^0}||$ (unless M preserves $U^0$, which is the case for $Q|_{U^0}$).

Restrict a matrix to the average-zero subspace. Default implementation: requires specialization per basis type.

Bounds rigorously the distance of w from the fixed point of Q (normalized with integral = 1), using a vector of bounds norms[k] ≥ ||Qh^k|{U_h^0}||.

Uses power norm bounds already computed for a coarse operator to estimate the same norms for a finer operator

Return a numerical approximation to the (hopefully unique) invariant vector of the dynamic with discretized operator Q.

The vector is normalized so that integral_covector(B)*w ≈ 1

Arrays of bounds to ||Q^k||{w → s} = sup{||f||w=1} ||Q^k f||s and to ||Q^k||_{w} coming theoretically from iterated DFLY inequalities (the "small matrix method").

Returns two arrays (strongs, norms) of length m: strongs[k] bounds ||Q^k f||_s, norms[k] bounds ||Q^k f||)

Estimate norms of powers from those on a coarser grid (see paper for details) TODO: Check if it works for other basis types

Estimates the norms ||Q||, ||Q^2||, ... ||Q^m|| on U^0.

U is the matrix [ones(1,n-1); -I_(n-1,n-1)]. It is currently assumed that f*U==0 (i.e., all elements of f are equal).

f must be an interval vector.

The following constants may be specified as keyword arguments:

normQ, normE, normv0, normEF, normIEF, normN

otherwise they are computed (which may be slower).

e and f must be specified in case isintegralpreserving==false In case isintegralpreserving is true, they may be specified but they are then ignored.

Array of "trivial" bounds for the powers of a DiscretizedOperator (on the whole space) coming from from ||Q^k|| ≤ ||Q||^k

Return an upper bound to Q_h*w - w in the given norm

'Absolute value' definition that returns mag(I) for an interval and abs(x) for a real

Computes a rigorous upper bound for z*z'

Rigorous upper bound on a vector norm. Note that Linf, L1 are the "analyst's" norms

Rigorous upper bound on the L2 norm of a vector, using Parseval identity.

Certified upper bound to ||A|| (of specified NormKind)

Certified upper bound to the L2 operator norm of a matrix via BallArithmetic. Uses Collatz + sqrt(L1·L∞) interpolation for a tight bound.

These functions compute a rigorous upper bound for the 2-norm of a vector; we have a specialized version for complex numbers to avoid taking the sqrt root and squaring again

Types to compute norms iteratively by "adding a column at a time".

Create a new NormCacher to compute the normbound of the empty matrix with n rows

Update a NormCacher to add one column to the matrix it is computing a norm of. This column may be affected by an error ε (in the same norm).

Return the norm of the matrix the NormCacher is working on.

convergencerateabstract(Bas::Ulam, D::Dynamic, norms)

Estimate the strong norm of $||L^n|_{U_0}||_s$ from norms, the bounds on the weak norm of the discretized operator

$||L_{h}^n|_{U_0}||_w$

This method was developed in Stefano Galatolo, Isaia Nisoli, Benoît Saussol. An elementary way to rigorously estimate convergence to equilibrium and escape rates. Journal of Computational Dynamics, 2015, 2 (1) : 51-64. doi: 10.3934/jcd.2015.2.51

eig_costants_small_matrix(A)

Return the dominant eigenvalue and associated left eigenvector of the small matrix