Raf Vandebril

Leonardo Robol, Raf Vandebril, Paul Van Dooren

We present a framework for the construction of linearizations for scalar and matrix polynomials based on dual bases which, in the case of orthogonal polynomials, can be described by the associated recurrence relations. The framework provides an extension of the classical linearization theory for polynomials expressed in non-monomial bases and allows to represent polynomials expressed in product families, that is as a linear combination of elements of the form $ϕ_i(λ) ψ_j(λ)$, where $\{ ϕ_i(λ) \}$ and $\{ ψ_j(λ) \}$ can either be polynomial bases or polynomial families which satisfy some mild assumptions. We show that this general construction can be used for many different purposes. Among them, we show how to linearize sums of polynomials and rational functions expressed in different bases. As an example, this allows to look for intersections of functions interpolated on different nodes without converting them to the same basis. We then provide some constructions for structured linearizations for $\star$-even and $\star$-palindromic matrix polynomials. The extensions of these constructions to $\star$-odd and $\star$-antipalindromic of odd degree is discussed and follows immediately from the previous results.

Daan Camps, Karl Meerbergen, Raf Vandebril

We propose a rational QZ method for the solution of the dense, unsymmetric generalized eigenvalue problem. This generalization of the classical QZ method operates implicitly on a Hessenberg, Hessenberg pencil instead of on a Hessenberg, triangular pencil. Whereas the QZ method performs nested subspace iteration driven by a polynomial, the rational QZ method allows for nested subspace iteration driven by a rational function, this creates the additional freedom of selecting poles. In this article we study Hessenberg, Hessenberg pencils, link them to rational Krylov subspaces, propose a direct reduction method to such a pencil, and introduce the implicit rational QZ step. The link with rational Krylov subspaces allows us to prove essential uniqueness (implicit Q theorem) of the rational QZ iterates as well as convergence of the proposed method. In the proofs, we operate directly on the pencil instead of rephrasing it all in terms of a single matrix. Numerical experiments are included to illustrate competitiveness in terms of speed and accuracy with the classical approach. Two other types of experiments exemplify new possibilities. First we illustrate that good pole selection can be used to deflate the original problem during the reduction phase, and second we use the rational QZ method to implicitly filter a rational Krylov subspace in an iterative method.

Jared L. Aurentz, Thomas Mach, Leonardo Robol et al.

This work is a continuation of "Fast and backward stable computation of roots of polynomials" by J.L. Aurentz, T. Mach, R. Vandebril, and D.S. Watkins, SIAM Journal on Matrix Analysis and Applications, 36(3): 942--973, 2015. In that paper we introduced a companion QR algorithm that finds the roots of a polynomial by computing the eigenvalues of the companion matrix in $O(n^{2})$ time using $O(n)$ memory. We proved that the method is backward stable. Here we introduce, as an alternative, a companion QZ algorithm that solves a generalized eigenvalue problem for a companion pencil. More importantly, we provide an improved backward error analysis that takes advantage of the special structure of the problem. The improvement is also due, in part, to an improvement in the accuracy (in both theory and practice) of the turnover operation, which is the key component of our algorithms. We prove that for the companion QR algorithm, the backward error on the polynomial coefficients varies linearly with the norm of the polynomial's vector of coefficients. Thus the companion QR algorithm has a smaller backward error than the unstructured QR algorithm (used by MATLAB's \texttt{roots} command, for example), for which the backward error on the polynomial coefficients grows quadratically with the norm of the coefficient vector. The companion QZ algorithm has the same favorable backward error as companion QR, provided that the polynomial coefficients are properly scaled.

Bernhard Beckermann, Clara Mertens, Raf Vandebril

Matrices whose adjoint is a low rank perturbation of a rational function of the matrix naturally arise when trying to extend the well known Faber-Manteuffel theorem, which provides necessary and sufficient conditions for the existence of a short Arnoldi recurrence. We show that an orthonormal Krylov basis for this class of matrices can be generated by a short recurrence relation based on GMRES residual vectors. These residual vectors are computed by means of an updating formula. Furthermore, the underlying Hessenberg matrix has an accompanying low rank structure, which we will investigate closely.

Michele Rinelli, Raf Vandebril

We study the connection between block Krylov subspaces and matrix orthogonal functions. Under a no-deflation assumption, we show that polynomial block Krylov subspaces are isometrically isomorphic to spaces of matrix polynomials of bounded degree, providing a unified framework for the analysis and construction of orthonormal bases and recurrence relations. The same correspondence holds for rational block Krylov subspaces and matrix-valued rational functions, and in the extended Krylov setting this leads naturally to Laurent matrix polynomials. When the matrix $A$ is normal, we prove that the induced inner product admits a representation in terms of a discrete spectral matrix measure, extending a classical result for Hermitian matrices. In the unitary case, where the measure is supported on the unit circle, this connection allows us to transfer the Szegő recurrence for orthogonal matrix polynomials and the CMV framework for Laurent matrix polynomials to the block Krylov setting, yielding efficient procedures for the orthogonalization of polynomial and extended block Krylov subspaces.

Jared Aurentz, Thomas Mach, Leonardo Robol et al.

In the last decade matrix polynomials have been investigated with the primary focus on adequate linearizations and good scaling techniques for computing their eigenvalues and eigenvectors. In this article we propose a new method for computing a factored Schur form of the associated companion pencil. The algorithm has a quadratic cost in the degree of the polynomial and a cubic one in the size of the coefficient matrices. Also the eigenvectors can be computed at the same cost. The algorithm is a variant of Francis's implicitly shifted QR algorithm applied on the companion pencil. A preprocessing unitary equivalence is executed on the matrix polynomial to simultaneously bring the leading matrix coefficient and the constant matrix term to triangular form before forming the companion pencil. The resulting structure allows us to stably factor each matrix of the pencil as a product of $k$ matrices of unitary-plus-rank-one form, admitting cheap and numerically reliable storage. The problem is then solved as a product core chasing eigenvalue problem. A backward error analysis is included, implying normwise backward stability after a proper scaling. Computing the eigenvectors via reordering the Schur form is discussed as well. Numerical experiments illustrate stability and efficiency of the proposed methods.