AMRVW

Implementation of core-chasing algorithms for finding eigenvalues of factored matrices.

This repository provides a Julia package implementing the methods, as applied to the problem of finding the roots of polynomials through the computation of the eigenvalues of a sparse factorization of the companion matrix in:

Fast and Backward Stable Computation of Roots of Polynomials. Jared L. Aurentz, Thomas Mach, Raf Vandebril, and David S. Watkins SIAM J. Matrix Anal. Appl., 36(3), 942–973. (2015) https://doi.org/10.1137/140983434

Fast and backward stable comptation of roots of polynomials, Part II: backward error analysis; companion matrix and companion pencil. By Jared L. Aurentz, Thomas Mach, utation of roots of polynomials, Part II: backward error analysis; companion matrix and companion pencil. By Jared L. Aurentz, Thomas Mach, Leonardo Robol, Raf Vandebril, David S. Watkins; arXiv:1611.02435

The methods are summarized in monograph format:

Core-Chasing Algorithms for the Eigenvalue Problem. by Jared L. Aurentz, Thomas Mach, Leonardo Robol, Raf Vandebril, and David S. Watkins; https://doi.org/10.1137/1.9781611975345

As well, the twisted algorithm from A generalization of the multishift QR algorithm by Raf Vandebril and David S. Watkins; https://doi.org/10.1137/11085219X is implemented here.

The core-chasing algorithms utilize Francis's QR algorithm on sparse factorizations of the respected companion matrix. For polynomials with real coefficients, the storage requirements are $O(n)$ and the algorithm requires $O(n)$ flops per iteration, or $O(n^2)$ flops overall. The basic QR algorithm applied to the full companion matrix would require $O(n^2)$ storage and $O(n^3)$ flops overall.

Reference

AMRVW.amrvw — Method

amrvw(vs, ws)

Computes a sparse factorization of of the companion matrix of a polynomial specified through a pencil decomposition.

A pencil decomposition of a polynomial, is a specification where if p = a0 + a1x^1 + ... + xn x^n then vs[1] = a0, vs[i+1] + ws[i] = ai, and ws[n] = an.

source

AMRVW.amrvw — Method

amrvw(ps)

For a polynomial specified by ps computes a sparse factorization of its companion matrix.

source

AMRVW.qr_factorization — Method

qr_factorization(H::Matrix; unitary=false)

For a Hessenberg matrix H return a factorization,Q⋅R, where Q is a QFactorization object of descending rotators and R is either a AMRVW.RFactorizationUnitaryDiagonal object (if unitary=true) or a RFactorizationUpperTriangular object.

H may be a full matrix or the .H component of a hessenberg factorization.

source

AMRVW.real_polynomial_roots — Method

real_polynomial_roots(ps)

Roots of a real polynomial with real coefficients.

source

AMRVW.roots — Method

roots(ps)
roots(vs, ws)

Use an algorithm of AMRVW to find roots of a polynomial over the reals or complex numbers.

ps: The coefficients, [p0, p1, p2, ...., pn], of the polynomial p0 + p1*x + p2*x^2 + ... + pn*x^n
[vs, ws]: If a second set of coefficients is passed, a pencil decomposition is used.

Returns a complex vector of roots. When the algorithm fails, a warning is issued about the number of non-identified roots.

A pencil decomposition satisfies vs[1]=p0; vs[i+1]+ws[i] = pi and ws[n] = pn.

A pencil can be used when there is a wide range in the coefficients of the polynomial, as though slower, it can be more stable.

The non-exported function basic_pencil implements the pencil which pulls off the leading coefficient a_n.

Examples:

import AMRVW as A
rs = rand(10)
A.roots(rs)      # uses Real double shift algorithm

rs = rand(Complex{Float64}, 10)
A.roots(rs)      # uses Complex Single Shift algorithm

rs = rand(10)
vs, ws = A.basic_pencil(rs)
A.roots(vs, ws)  # uses QZ pencil factorization

References:

Fast and backward stable computation of the eigenvalues of matrix polynomials. By Aurentz, Jared & Mach, Thomas & Robol, Leonardo & Vandebril, Raf & Watkins, David. (2016). Mathematics of Computation. 88. DOI: 10.1090/mcom/3338.

Fast and backward stable computation of roots of polynomials, Part II: backward error analysis; companion matrix and companion pencil. By

Jared L. Aurentz, Thomas Mach, Leonardo Robol, Raf Vandebril, David S. Watkins; arXiv:1611.02435

source