DGGHR3 swMATH ID: 13050 Software Authors: Karlsson, Lars; Tisseur, Françoise Description: Algorithms for Hessenberg-triangular reduction of Fiedler linearization of matrix polynomials. Small- to medium-sized polynomial eigenvalue problems can be solved by linearizing the matrix polynomial and solving the resulting generalized eigenvalue problem using the QZ algorithm. The QZ algorithm, in turn, requires an initial reduction of a matrix pair to Hessenberg-triangular (HT) form. In this paper, we discuss the design and evaluation of high-performance parallel algorithms and software for HT reduction of a specific linearization of matrix polynomials of arbitrary degree. The proposed algorithm exploits the sparsity structure of the linearization to reduce the number of operations and improve the cache reuse compared to existing algorithms for unstructured inputs. Experiments on both a workstation and a high-performance computing system demonstrate that our structure-exploiting parallel implementation can outperform both the general LAPACK routine DGGHRD and the prototype implementation DGGHR3 of a general blocked algorithm Homepage: http://epubs.siam.org/doi/10.1137/140970458 Keywords: Hessenberg-triangular reduction; polynomial eigenvalue problem; linearization; blocked algorithm; parallelization Related Software: DGGHRD; NLEVP; NLEIGS; Chebfun; RKToolbox; StratiGraph; Matlab; quadeig; LAPACK Cited in: 7 Documents all top 5 Cited by 12 Authors 2 Dmytryshyn, Andrii R. 1 Chen, Hongjia 1 de Terán, Fernando 1 Kågström, Bo 1 Karlsson, Lars 1 Mackey, D. Steven 1 Noferini, Vanni 1 Pérez, Javier J. 1 Perović, Vasilije 1 Tisseur, Françoise 1 Van Dooren, Paul M. 1 Xu, Kuan all top 5 Cited in 7 Serials 1 Mathematics of Computation 1 BIT 1 SIAM Journal on Matrix Analysis and Applications 1 Journal of Scientific Computing 1 Linear Algebra and its Applications 1 SIAM Journal on Scientific Computing 1 Foundations of Computational Mathematics Cited in 5 Fields 6 Linear and multilinear algebra; matrix theory (15-XX) 6 Numerical analysis (65-XX) 2 Operator theory (47-XX) 1 Approximations and expansions (41-XX) 1 Computer science (68-XX) Citations by Year