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
Parallel Eigenvalue Reordering in Real Schur Forms
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap. Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Högpresterande beräkningscentrum norr (HPC2N).
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap. Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Högpresterande beräkningscentrum norr (HPC2N). (UMIT)
ETH, Zürich.
2009 (Engelska)Ingår i: Concurrency and Computation, ISSN 1532-0626, E-ISSN 1532-0634, Vol. 21, nr 9, s. 1225-1250Artikel i tidskrift (Refereegranskat) Published
Abstract [en]

A parallel algorithm for reordering the eigenvalues in the real Schur form of a matrix is presented and discussed. Our novel approach adopts computational windows and delays multiple outside-window updates until each window has been completely reordered locally. By using multiple concurrent windows the parallel algorithm has a high level of concurrency, and most work is level 3 BLAS operations. The presented algorithm is also extended to the generalized real Schur form. Experimental results for ScaLAPACK-style Fortran 77 implementations on a Linux cluster confirm the efficiency and scalability of our algorithms in terms of more than 16 times of parallel speedup using 64 processors for large-scale problems. Even on a single processor our implementation is demonstrated to perform significantly better compared with the state-of-the-art serial implementation.

Ort, förlag, år, upplaga, sidor
2009. Vol. 21, nr 9, s. 1225-1250
Nyckelord [en]
parallel algorithms;eigenvalue problems;invariant subspaces, direct reordering, Sylvester matrix equations, condition number estimates
Nationell ämneskategori
Datavetenskap (datalogi) Programvaruteknik
Identifikatorer
URN: urn:nbn:se:umu:diva-24699DOI: 10.1002/cpe.1386OAI: oai:DiVA.org:umu-24699DiVA, id: diva2:227207
Tillgänglig från: 2009-07-10 Skapad: 2009-07-10 Senast uppdaterad: 2018-06-08Bibliografiskt granskad
Ingår i avhandling
1. Algorithms and Library Software for Periodic and Parallel Eigenvalue Reordering and Sylvester-Type Matrix Equations with Condition Estimation
Öppna denna publikation i ny flik eller fönster >>Algorithms and Library Software for Periodic and Parallel Eigenvalue Reordering and Sylvester-Type Matrix Equations with Condition Estimation
2007 (Engelska)Doktorsavhandling, sammanläggning (Övrigt vetenskapligt)
Abstract [en]

This Thesis contains contributions in two different but closely related subfields of Scientific and Parallel Computing which arise in the context of various eigenvalue problems: periodic and parallel eigenvalue reordering and parallel algorithms for Sylvestertype matrix equations with applications in condition estimation.

Many real world phenomena behave periodically, e.g., helicopter rotors, revolving satellites and dynamic systems corresponding to natural processes, like the water flow in a system of connected lakes, and can be described in terms of periodic eigenvalue problems. Typically, eigenvalues and invariant subspaces (or, specifically, eigenvectors) to certain periodic matrix products are of interest and have direct physical interpretations. The eigenvalues of a matrix product can be computed without forming the product explicitly via variants of the periodic Schur decomposition. In the first part of the Thesis, we propose direct methods for eigenvalue reordering in the periodic standard and generalized real Schur forms which extend earlier work on the standard and generalized eigenvalue problems. The core step of the methods consists of solving periodic Sylvester-type equations to high accuracy. Periodic eigenvalue reordering is vital in the computation of periodic eigenspaces corresponding to specified spectra. The proposed direct reordering methods rely on orthogonal transformations and can be generalized to more general periodic matrix products where the factors have varying dimensions and ±1 exponents of arbitrary order.

In the second part, we consider Sylvester-type matrix equations, like the continuoustime Sylvester equation AX −XB =C, where A of size m×m, B of size n×n, and C of size m×n are general matrices with real entries, which have applications in many areas. Examples include eigenvalue problems and condition estimation, and several problems in control system design and analysis. The parallel algorithms presented are based on the well-known Bartels–Stewart’s method and extend earlier work on triangular Sylvester-type matrix equations resulting in a novel software library SCASY. The parallel library provides robust and scalable software for solving 44 sign and transpose variants of eight common Sylvester-type matrix equations. SCASY also includes a parallel condition estimator associated with each matrix equation.

In the last part of the Thesis, we propose parallel variants of the direct eigenvalue reordering method for the standard and generalized real Schur forms. Together with the existing and future parallel implementations of the non-symmetric QR/QZ algorithms and the parallel Sylvester solvers presented in the Thesis, the developed software can be used for parallel computation of invariant and deflating subspaces corresponding to specified spectra and associated reciprocal condition number estimates.

Ort, förlag, år, upplaga, sidor
Umeå: Datavetenskap, 2007. s. 44
Serie
Report / UMINF, ISSN 0348-0542 ; 07.21
Nyckelord
periodic eigenvalue problems, product eigenvalue problems, periodic Schur form, periodic eigenvalue reordering, periodic eigenspaces, parallel algorithms, Sylvester-type matrix equations, parallel eigenvalue reordering, condition estimation
Nationell ämneskategori
Datavetenskap (datalogi)
Identifikatorer
urn:nbn:se:umu:diva-1415 (URN)978-91-7264-410-6 (ISBN)
Externt samarbete:
Disputation
2007-11-23, MA121, MIT-huset, Umeå Universitet, UMEÅ, 10:00 (Engelska)
Opponent
Handledare
Tillgänglig från: 2007-11-01 Skapad: 2007-11-01 Senast uppdaterad: 2018-06-09Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas i DiVA

Övriga länkar

Förlagets fulltext

Personposter BETA

Granat, RobertKågström, Bo

Sök vidare i DiVA

Av författaren/redaktören
Granat, RobertKågström, Bo
Av organisationen
Institutionen för datavetenskapHögpresterande beräkningscentrum norr (HPC2N)
I samma tidskrift
Concurrency and Computation
Datavetenskap (datalogi)Programvaruteknik

Sök vidare utanför DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetricpoäng

doi
urn-nbn
Totalt: 361 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