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
Recursive Blocked Algorithms for Solving Triangular Systems - Part I: One-Sided and Coupled Sylvester-Type Matrix Equations
Umeå University, Faculty of Science and Technology, Department of Computing Science. Umeå University, Faculty of Science and Technology, HPC2N (High Performance Computing Centre North).
Umeå University, Faculty of Science and Technology, Department of Computing Science. Umeå University, Faculty of Science and Technology, HPC2N (High Performance Computing Centre North).
2002 (English)In: ACM Transactions on Mathematical Software, Vol. 28, no 4, 392-415 p.Article in journal (Refereed) Published
Abstract [en]

Triangular matrix equations appear naturally in estimating the condition numbers of matrix equations and different eigenspace computations, including block-diagonalization of matrices and matrix pairs and computation of functions of matrices. To solve a triangular matrix equation is also a major step in the classical Bartels-Stewart method for solving the standard continuous-time Sylvester equation (AX-XB=C). We present novel recursive blocked algorithms for solving one-sided triangular matrix equations, including the continuous-time Sylvester and Lyapunov equations, and a generalized coupled Sylvester equation. The main parts of the computations are performed as level-3 general matrix multiply and add (GEMM) operations. In contrast to explicit standard blocking techniques, our recursive approach leads to an automatic variable blocking that has the potential of matching the memory hierarchies of today's HPC systems. Different implementation issues are discussed, including when to terminate the recursion, the design of new optimized superscalar kernels for solving leaf-node triangular matrix equations efficiently, and how parallelism is utilized in our implementations. Uniprocessor and SMP parallel performance results of our recursive blocked algorithms and corresponding routines in the state-of-the-art libraries LAPACK and SLICOT are presented. The performance improvements of our recursive algorithms are remarkable, including 10-fold speedups compared to standard algorithms.

Place, publisher, year, edition, pages
2002. Vol. 28, no 4, 392-415 p.
Identifiers
URN: urn:nbn:se:umu:diva-21950ISBN: 0098-3500 OAI: oai:DiVA.org:umu-21950DiVA: diva2:212207
Available from: 2009-04-21 Created: 2009-04-21 Last updated: 2009-07-09

Open Access in DiVA

No full text

Other links

<Go to ISI>://000179844400002

Authority records BETA

Kågström, Bo

Search in DiVA

By author/editor
Kågström, Bo
By organisation
Department of Computing ScienceHPC2N (High Performance Computing Centre North)

Search outside of DiVA

GoogleGoogle Scholar

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 16 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