umu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Algorithms and Library Software for Periodic and Parallel Eigenvalue Reordering and Sylvester-Type Matrix Equations with Condition Estimation
Umeå University, Faculty of Science and Technology, Department of Computing Science.
2007 (English)Doctoral thesis, comprehensive summary (Other academic)
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.

Place, publisher, year, edition, pages
Umeå: Datavetenskap , 2007. , 44 p.
Series
Report / UMINF, ISSN 0348-0542 ; 07.21
Keyword [en]
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
National Category
Computer Science
Identifiers
URN: urn:nbn:se:umu:diva-1415ISBN: 978-91-7264-410-6 (print)OAI: oai:DiVA.org:umu-1415DiVA: diva2:140959
Public defence
2007-11-23, MA121, MIT-huset, Umeå Universitet, UMEÅ, 10:00 (English)
Opponent
Supervisors
Available from: 2007-11-01 Created: 2007-11-01 Last updated: 2016-08-30Bibliographically approved
List of papers
1. Direct Eigenvalue Reordering in a Product of Matrices in Periodic Schur Form
Open this publication in new window or tab >>Direct Eigenvalue Reordering in a Product of Matrices in Periodic Schur Form
2006 (English)In: SIAM Journal on Matrix Analysis and Applications, ISSN 0895-4798, Vol. 28, no 1, 285-300 p.Article in journal (Refereed) Published
Abstract [en]

A direct method for eigenvalue reordering in a product of a K-periodic matrix sequence in periodic or extended periodic real Schur form is presented and analyzed. Each reordering of two adjacent sequences of diagonal blocks is performed tentatively to guarantee backward stability and involves solving a K-periodic Sylvester equation (PSE) and constructing a K-periodic sequence of orthogonal transformation matrices. An error analysis of the direct reordering method is presented, and results from computational experiments confirm the stability and accuracy of the method for well-conditioned as well as ill-conditioned problems. These include matrix sequences with fixed and time-varying dimensions, and sequences of small and large periodicity.

Keyword
product of $K$-periodic matrix sequence, extended periodic real Schur form, eigenvalue reordering, $K$-periodic Sylvester equation, periodic eigenvalue problem
Identifiers
urn:nbn:se:umu:diva-15888 (URN)dx.doi.org/10.1137/05062490X (DOI)
Available from: 2007-08-03 Created: 2007-08-03 Last updated: 2009-09-17Bibliographically approved
2. Computing Periodic Deflating Subspaces Associated with a Specified Set of Eigenvalues
Open this publication in new window or tab >>Computing Periodic Deflating Subspaces Associated with a Specified Set of Eigenvalues
2007 (English)In: BIT Numerical Mathematics, ISSN 0006-3835, Vol. 47, no 4, 763-791 p.Article in journal (Refereed) Published
Abstract [en]

We present a direct method for reordering eigenvalues in the generalized periodic real Schur form of a regular K-cyclic matrix pair sequence (A (k) ,E (k) ). Following and generalizing existing approaches, reordering consists of consecutively computing the solution to an associated Sylvester-like equation and constructing K pairs of orthogonal matrices. These pairs define an orthogonal K-cyclic equivalence transformation that swaps adjacent diagonal blocks in the Schur form. An error analysis of this swapping procedure is presented, which extends existing results for reordering eigenvalues in the generalized real Schur form of a regular pair (A,E). Our direct reordering method is used to compute periodic deflating subspace pairs corresponding to a specified set of eigenvalues. This computational task arises in various applications related to discrete-time periodic descriptor systems. Computational experiments confirm the stability and reliability of the presented eigenvalue reordering method.

Keyword
generalized product of a K-cyclic matrix pair sequence, generalized periodic real Schur form, eigenvalue reordering, periodic generalized coupled Sylvester equation, K-cyclic equivalence transformation, generalized periodic eigenvalue problem
Identifiers
urn:nbn:se:umu:diva-21939 (URN)10.1007/s10543-007-0143-y (DOI)0006-3835 (ISBN)
Note
Granat, R. Kagstroem, B. Kressner, D.Available from: 2009-04-21 Created: 2009-04-21 Last updated: 2009-09-17
3. Parallel Solvers for Sylvester-type Matrix Equations with Applications in Condition Estimation, Part I: Theory and Algorithms
Open this publication in new window or tab >>Parallel Solvers for Sylvester-type Matrix Equations with Applications in Condition Estimation, Part I: Theory and Algorithms
2010 (English)In: ACM Transactions on Mathematical Software, ISSN 0098-3500, Vol. 37, no 3, 32:1-32:32 p.Article in journal (Refereed) Published
Abstract [en]

Parallel ScaLAPACK-style algorithms for solving eight common standard and generalized Sylvester-type matrix equations and various sign and transposed variants are presented. All algorithms are blocked variants based on the Bartels--Stewart method and involve four major steps: reduction to triangular form, updating the right-hand side with respect to the reduction, computing the solution to the reduced triangular problem, and transforming the solution back to the original coordinate system. Novel parallel algorithms for solving reduced triangular matrix equations based on wavefront-like traversal of the right-hand side matrices are presented together with a generic scalability analysis. These algorithms are used in condition estimation and new robust parallel sep − 1-estimators are developed. Experimental results from three parallel platforms, including results from a mixed OpenMP/MPI platform, are presented and analyzed using several performance and accuracy metrics. The analysis includes results regarding general and triangular parallel solvers as well as parallel condition estimators.

Place, publisher, year, edition, pages
New York: ACM Press, 2010
National Category
Mathematics
Identifiers
urn:nbn:se:umu:diva-2708 (URN)10.1145/1824801.1824810 (DOI)000282761200009 ()
Note

Artikelnummer/article number: 32

Available from: 2007-11-01 Created: 2007-11-01 Last updated: 2013-03-15Bibliographically approved
4. Algorithm 904: the SCASY library - parallel solvers for Sylvester-type matrix equations with applications in condition estimation, part II
Open this publication in new window or tab >>Algorithm 904: the SCASY library - parallel solvers for Sylvester-type matrix equations with applications in condition estimation, part II
2010 (English)In: ACM Transactions on Mathematical Software, ISSN 0098-3500, E-ISSN 1557-7295, Vol. 37, no 3, 33Article in journal (Refereed) Published
Abstract [en]

We continue our presentation of parallel ScaLAPACK-style algorithms for solving Sylvester-type matrix equations. In Part II, we present SCASY (SCAlable SYlvester solvers), a state-of-the-art HPC software library for solving 44 sign and transpose variants of eight common standard and generalized Sylvester-type matrix equations.

Place, publisher, year, edition, pages
New York: Association for Computing Machinery (ACM), 2010
Keyword
Algorithms, Performance, Reliability, Parallel computing, parallel algorithms, Eigenvalue problems, condition estimation, Sylvester matrix equations
National Category
Computer and Information Science
Identifiers
urn:nbn:se:umu:diva-51035 (URN)10.1145/1824801.1824811 (DOI)000282761200010 ()
External cooperation:
Funder
Swedish Research Council, 70625701
Available from: 2012-01-09 Created: 2012-01-09 Last updated: 2017-12-08Bibliographically approved
5. Parallel Eigenvalue Reordering in Real Schur Forms
Open this publication in new window or tab >>Parallel Eigenvalue Reordering in Real Schur Forms
2009 (English)In: Concurrency and Computation, ISSN 1532-0626, E-ISSN 1532-0634, Vol. 21, no 9, 1225-1250 p.Article in journal (Refereed) 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.

Keyword
parallel algorithms;eigenvalue problems;invariant subspaces, direct reordering, Sylvester matrix equations, condition number estimates
National Category
Computer Science Software Engineering
Identifiers
urn:nbn:se:umu:diva-24699 (URN)10.1002/cpe.1386 (DOI)
Available from: 2009-07-10 Created: 2009-07-10 Last updated: 2012-04-11Bibliographically approved

Open Access in DiVA

fulltext(2442 kB)1371 downloads
File information
File name FULLTEXT01.pdfFile size 2442 kBChecksum SHA-1
c45636c8dc34c85c8dd4350ce4199b6bbc79fee035f8dd7a859382e0858979ab9ed86509
Type fulltextMimetype application/pdf

Authority records BETA

Granat, Robert

Search in DiVA

By author/editor
Granat, Robert
By organisation
Department of Computing Science
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 1371 downloads
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

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 765 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf