Change search
ReferencesLink to record
Permanent link

Direct link
Recursive Blocked Algorithms for Solving Triangular Systems—Part II: Two-Sided and Generalized Sylvester and Lyapunov Matrix Equations
Umeå University, Faculty of Science and Technology, Computing Science.
2002 In: ACM Transactions on Mathematical Software, ISSN 0098-3500, Vol. 28, no 4, 416-435 p.Article in journal (Refereed) Published
Place, publisher, year, edition, pages
2002. Vol. 28, no 4, 416-435 p.
URN: urn:nbn:se:umu:diva-3062OAI: diva2:141508
Available from: 2003-11-26 Created: 2003-11-26Bibliographically approved
In thesis
1. Recursive Blocked Algorithms, Data Structures, and High-Performance Software for Solving Linear Systems and Matrix Equations
Open this publication in new window or tab >>Recursive Blocked Algorithms, Data Structures, and High-Performance Software for Solving Linear Systems and Matrix Equations
2003 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

This thesis deals with the development of efficient and reliable algorithms and library software for factorizing matrices and solving matrix equations on high-performance computer systems. The architectures of today's computers consist of multiple processors, each with multiple functional units. The memory systems are hierarchical with several levels, each having different speed and size. The practical peak performance of a system is reached only by considering all of these characteristics. One portable method for achieving good system utilization is to express a linear algebra problem in terms of level 3 BLAS (Basic Linear Algebra Subprogram) transformations. The most important operation is GEMM (GEneral Matrix Multiply), which typically defines the practical peak performance of a computer system. There are efficient GEMM implementations available for almost any platform, thus an algorithm using this operation is highly portable.

The dissertation focuses on how recursion can be applied to solve linear algebra problems. Recursive linear algebra algorithms have the potential to automatically match the size of subproblems to the different memory hierarchies, leading to much better utilization of the memory system. Furthermore, recursive algorithms expose level 3 BLAS operations, and reveal task parallelism. The first paper handles the Cholesky factorization for matrices stored in packed format. Our algorithm uses a recursive packed matrix data layout that enables the use of high-performance matrix--matrix multiplication, in contrast to the standard packed format. The resulting library routine requires half the memory of full storage, yet the performance is better than for full storage routines.

Paper two and tree introduce recursive blocked algorithms for solving triangular Sylvester-type matrix equations. For these problems, recursion together with superscalar kernels produce new algorithms that give 10-fold speedups compared to existing routines in the SLICOT and LAPACK libraries. We show that our recursive algorithms also have a significant impact on the execution time of solving unreduced problems and when used in condition estimation. By recursively splitting several problem dimensions simultaneously, parallel algorithms for shared memory systems are obtained. The fourth paper introduces a library---RECSY---consisting of a set of routines implemented in Fortran 90 using the ideas presented in paper two and three. Using performance monitoring tools, the last paper evaluates the possible gain in using different matrix blocking layouts and the impact of superscalar kernels in the RECSY library.

20 p.
Report / UMINF, ISSN 0348-0542 ; 03.17
Datorberäkningar och högpresterande datorer, Recursive algorithm, recursive blocked format, Cholesky factorization, Sylvester-type equations, automatic blocking, superscalar, GEMM-based, RECSY library, Datorberäkningar och högpresterande datorer
National Category
Computer Engineering
Research subject
Computing Science
urn:nbn:se:umu:diva-160 (URN)91-7305-568-9 (ISBN)
Public defence
2003-12-17, MA121, MIT-huset, Umeå Universitet, Umeå, 13:15
Available from: 2003-11-26 Created: 2003-11-26Bibliographically approved

Open Access in DiVA

No full text

Other links
By organisation
Computing Science

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

Total: 18 hits
ReferencesLink to record
Permanent link

Direct link