A parameterized ordering for cache-, register- and pipeline-efficient Givens QR decomposition

DOI10.1023/A:1018970413988MaRDI QIDQ1284142zbMATH OpenOpenAlexFDO

Authors James J. jun. Carrig, Gerard G. L. Meyer

Publication date 30 March 1999

Published in Advances in Computational Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1023/a:1018970413988

zbMATH Keywords

Givens algorithmgraphorderingQR decompositionsuperscalar processor

Mathematics Subject Classification ID

Direct numerical methods for linear systems and matrix inversion (65F05) Orthogonalization in numerical linear algebra (65F25) Numerical algorithms for specific classes of architectures (65Y10)

Review text

A number of methods are known in the literature to calculate the QR decomposition of a matrix. The authors start with the basic Givens algorithm and construct a dependency graph such that any valid ordering through that graph yields an algorithm which is numerically identical to the original. Then they develop parametrized orderings through the graph, motivated by a simple model of a superscalar processor with a cache, registers, and a pipeline. The final algorithm simultaneously minimizes the number of loads and stores, while not stalling the floating point pipeline.

Recommendations

• On the relation between pseudo-Hermiticity and dissipation
• Efficient householder QR factorization for superscalar processors
• scientific article; zbMATH DE number 833735
• Row-ordering schemes for sparse Givens transformations. I. Bipartite graph model
• Row-ordering schemes for sparse Givens transformations. III. Analyses for a model problem

Cited in

(4)

• On the relation between pseudo-Hermiticity and dissipation
• Efficient householder QR factorization for superscalar processors
• Parallel QR factorization for hybrid message passing/shared memory operation
• Row-ordering schemes for sparse Givens transformations. I. Bipartite graph model

This page was built for publication: A parameterized ordering for cache-, register- and pipeline-efficient Givens QR decomposition

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1284142)