A Real QZ Algorithm for Structured Companion Pencils

Abstract

We design a fast implicit real QZ algorithm for eigenvalue computation of structured companion pencils arising from linearizations of polynomial rootfinding problems. The modified QZ algorithm computes the generalized eigenvalues of an $N\times N$ structured matrix pencil using $O(N)$ flops per iteration and $O(N)$ memory storage. Numerical experiments and comparisons confirm the effectiveness and the stability of the proposed method.

arXiv admin note: text overlap with arXiv:1401.5606

References in corpus (1)

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