Umeå universitets logga

umu.sePublikationer
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
A Householder-Based Algorithm for Hessenberg-Triangular Reduction
Department of Mathematics, Faculty of Science, University of Zagreb, Zagreb, Croatia.
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.ORCID-id: 0000-0002-4675-7434
Institute of Mathematics, EPFL, Lausanne, Switzerland.
2018 (Engelska)Ingår i: SIAM Journal on Matrix Analysis and Applications, ISSN 0895-4798, E-ISSN 1095-7162, Vol. 39, nr 3, s. 1270-1294Artikel i tidskrift (Refereegranskat) Published
Abstract [en]

The QZ algorithm for computing eigenvalues and eigenvectors of a matrix pencil $A - \lambda B$ requires that the matrices first be reduced to Hessenberg-triangular (HT) form. The current method of choice for HT reduction relies entirely on Givens rotations regrouped and accumulated into small dense matrices which are subsequently applied using matrix multiplication routines. A nonvanishing fraction of the total flop-count must nevertheless still be performed as sequences of overlapping Givens rotations alternately applied from the left and from the right. The many data dependencies associated with this computational pattern leads to inefficient use of the processor and poor scalability. In this paper, we therefore introduce a fundamentally different approach that relies entirely on (large) Householder reflectors partially accumulated into block reflectors, by using (compact) WY representations. Even though the new algorithm requires more floating point operations than the state-of-the-art algorithm, extensive experiments on both real and synthetic data indicate that it is still competitive, even in a sequential setting. The new algorithm is conjectured to have better parallel scalability, an idea which is partially supported by early small-scale experiments using multithreaded BLAS. The design and evaluation of a parallel formulation is future work.

Ort, förlag, år, upplaga, sidor
SIAM Publications , 2018. Vol. 39, nr 3, s. 1270-1294
Nationell ämneskategori
Beräkningsmatematik
Identifikatorer
URN: urn:nbn:se:umu:diva-154648DOI: 10.1137/17M1153637ISI: 000453716400010Scopus ID: 2-s2.0-85054167095OAI: oai:DiVA.org:umu-154648DiVA, id: diva2:1273439
Forskningsfinansiär
EU, Horisont 2020, 671633Tillgänglig från: 2018-12-21 Skapad: 2018-12-21 Senast uppdaterad: 2023-03-23Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas i DiVA

Övriga länkar

Förlagets fulltextScopus

Person

Karlsson, Lars

Sök vidare i DiVA

Av författaren/redaktören
Karlsson, Lars
Av organisationen
Institutionen för datavetenskap
I samma tidskrift
SIAM Journal on Matrix Analysis and Applications
Beräkningsmatematik

Sök vidare utanför DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetricpoäng

doi
urn-nbn
Totalt: 533 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf