Newton polynomials

NewtonPolynomial(ζ, d)

The unique interpolation polynomial of a function in its Newton form, i.e.

\[f(z) \approx p(z) = \sum_{j=1}^m \divdiff(\zeta_{1:j})f \prod_{i=1}^{j-1}(z - \zeta_i),\]

where ζ are the interpolation points and d[j]=⏃(ζ[1:j])f is the $j$th divided difference of the interpolated function f.

NewtonPolynomial(f, ζ)

Construct the Newton polynomial interpolating f at ζ, automatically deriving the divided differences using ⏃.

NewtonMatrixPolynomial(np, pv, r, Ar, error, m)

This structure aids in the computation of the action of a matrix polynomial on a vector. np is the NewtonPolynomial, pv is the desired result, r and Ar are recurrence vectors, and error is an optional error estimator algorithm that can be used to terminate the iterations early. m records how many matrix–vector multiplications were used when evaluating the matrix polynomial.

mul!(w, p::NewtonMatrixPolynomial, A, v)

Compute the action of the NewtonMatrixPolynomial p evaluated for the matrix (or linear operator) A acting on v and storing the result in w, i.e. w ← p(A)*v.

NewtonMatrixPolynomialDerivative(np, p′v, r′, Ar′, m)

This strucyture aids in the computation of the first derivative of the NewtonPolynomial np. It is to be used in lock-step with the evaluation of the polynomial, i.e. when evaluating the $m$th degree of np, this structure will provide the first derivative of the $m$th degree polynomial, storing the result in p′v. r′ and Ar′ are recurrence vectors. Its main application is in φₖResidualEstimator. m records how many matrix–vector multiplications were used when evaluating the matrix polynomial.

φₖResidualEstimator{T,k}(nmpd, ρ, vscaled, estimate, tol)

An implementation of the residual error estimate of the φₖ functions, as presented in

• Kandolf, P., Ostermann, A., & Rainer, S. (2014). A residual based error estimate for Leja interpolation of matrix functions. Linear Algebra and its Applications, 456(nil), 157–173. DOI: 10.1016/j.laa.2014.04.023

nmpd is a NewtonMatrixPolynomialDerivative that successively computes the time-derivative of the NewtonMatrixPolynomial used to interpolate $\varphi_k(tA)$ (the time-step $t$ is subsequently set to unity), ρ is the residual vector, vscaled an auxiliary vector for k>0, and estimate and tol are the estimated error and tolerance, respectively.