Families of Algorithms for Reducing a Matrix to Condensed Form

In a recent paper it was shown how memory traffic can be diminished by reformulating the classic algorithm for reducing a matrix to bidiagonal form, a preprocess when computing the singular values of a dense matrix. The key is a reordering of the computation so that the most memory-intensive operati...

Full description

Saved in:
Bibliographic Details
Published in:ACM transactions on mathematical software 2012-11, Vol.39 (1), p.1-32
Main Authors: Van Zee, Field G., van de Geijn, Robert A., Quintana-Ortí, Gregorio, Elizondo, G. Joseph
Format: Article
Language:English
Subjects:
Algorithms
Computation
Computer programs
Condensing
Mathematical models
Optimization
Reduction
Showcases
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In a recent paper it was shown how memory traffic can be diminished by reformulating the classic algorithm for reducing a matrix to bidiagonal form, a preprocess when computing the singular values of a dense matrix. The key is a reordering of the computation so that the most memory-intensive operations can be “fused.” In this article, we show that other operations that reduce matrices to condensed form (reduction to upper Hessenberg form and reduction to tridiagonal form) can be similarly reorganized, yielding different sets of operations that can be fused. By developing the algorithms with a common framework and notation, we facilitate the comparing and contrasting of the different algorithms and opportunities for optimization on sequential architectures. We discuss the algorithms, develop a simple model to estimate the speedup potential from fusing, and showcase performance improvements consistent with the what the model predicts.
ISSN:0098-3500
1557-7295
DOI:10.1145/2382585.2382587