Author jagot
Popularity
8 Stars
Updated Last
1 Year Ago
Started In
November 2019

# MatrixPolynomials.jl

This package aids in the computation of the action of a matrix polynomial on a vector, i.e. `p(A)v`, where `A` is a (square) matrix (or a linear operator) that is supplied to the polynomial `p`. The matrix polynomial `p(A)` is never formed explicitly, instead only its action on `v` is evaluated. This is commonly used in time-stepping algorithms for ordinary differential equations (ODEs) and discretized partial differential equations (PDEs) where `p` is an approximation of the exponential function (or the related `φ` functions: `φ₀(z) = exp(z)`, `φₖ₊₁ = [φₖ(z)-φₖ(0)]/z`, `φₖ(0)=1/k!`) on the field-of-values of the matrix `A`, which for the methods in this package needs to be known before-hand.

## Alternatives

Other packages with similar goals, but instead based on matrix polynomials found via Krylov iterations are

Krylov iterations do not need to know the field-of-values of the matrix `A` before-hand, instead, an orthogonal basis is built-up on-the-fly, by repeated action of `A` on test vectors: `Aⁿ*v`. This process is however very sensitive to the condition number of `A`, something that can be alleviated by iterating a shifted and inverted matrix instead: `(A-σI)⁻¹` (rational Krylov). Not all matrices/linear operators are easily inverted/factorized, however.

Moreover, the Krylov iterations for general matrices (then called Arnoldi iterations) require long-term recurrences with mutual orthogonalization along with inner products, all of which can be costly to compute. Finally, a subspace approximation of the polynomial `p` of a upper Hessenberg matrix needs to computed. The real-symmetric/complex-Hermitian case (Lanczos iterations) reduces to three-term recurrences and a tridiagonal subspace matrix. In contrast, the polynomial methods of this packages two-term recurrences only, no orthogonalization (and hence no inner products), and finally no evaluation of the polynomial on a subspace matrix. This could potentially mean that the methods are easier to implement on a GPU.

### Used By Packages

No packages found.