Change search
ReferencesLink to record
Permanent link

Direct link
Algorithms for Hessenberg-Triangular Reduction of Fiedler Linearization of Matrix Polynomials
Umeå University, Faculty of Science and Technology, Department of Computing Science.
2015 (English)In: SIAM Journal on Scientific Computing, ISSN 1064-8275, E-ISSN 1095-7197, Vol. 37, no 3, C384-C414 p.Article in journal (Refereed) Published
Abstract [en]

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.

Place, publisher, year, edition, pages
2015. Vol. 37, no 3, C384-C414 p.
Keyword [en]
Hessenberg-triangular reduction, polynomial eigenvalue problem, linearization, blocked algorithm, rallelization
National Category
Computer Engineering
URN: urn:nbn:se:umu:diva-106625DOI: 10.1137/140970458ISI: 000357406500012OAI: diva2:842960
Available from: 2015-07-24 Created: 2015-07-24 Last updated: 2015-07-24Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Karlsson, Lars
By organisation
Department of Computing Science
In the same journal
SIAM Journal on Scientific Computing
Computer Engineering

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 41 hits
ReferencesLink to record
Permanent link

Direct link