A pipelined Givens method for computing the QR factorization of a sparse matrix
type: Item
instance of: scholarly article
title: A pipelined Givens method for computing the QR factorization of a sparse matrix
zbMATH Open document ID: 0587.65018
DOI: 10.1016/0024-3795(86)90168-0
published in: Linear Algebra and its Applications
publication date: 1986-01-01T00:00:00Z
review text: This paper discusses an extension of the pipelined Givens method for computing the QR factorization of a real \(m\times n\) matrix to the case in which the matrix is sparse. When restricted to one process, the algorithm performs the same computation as the serial sparse Givens algorithm of \textit{A. George} and the first author [ibid. 34, 69-83 (1980; Zbl 0459.65025)]. Our implementation is compatible with the data structures used in SPARSPAK. The pipelined algorithm is well suited to parallel computers having globally shared memory and low-overhead synchronization primitives, such as the Denelcor HEP, for which computational results are presented. We point out certain synchronization problems that arise in the adaptation to the sparse setting and discuss the effect on parallel speedup of accessing a serial data file.
Mathematics Subject Classification ID: 65F05
Mathematics Subject Classification ID: 65F50
zbMATH DE Number: 3942903
zbMATH Keywords: numerical examples
zbMATH Keywords: pipelined Givens method
zbMATH Keywords: QR factorization
zbMATH Keywords: SPARSPAK
author: Michael T. Heath
author: Danny C. Sorensen
describes a project that uses: symrcm
MaRDI profile type: Publication
full work available at URL: 0024-3795(86)90168-0
OpenAlex ID: W1991565749
cites work: The natural factor formulation of the stiffness for the matrix displacement method
cites work: Implementation of some concurrent algorithms for matrix factorization
cites work: Error analysis of QR decompositions by Givens transformations
cites work: Solution of sparse linear least squares problems using Givens rotations
cites work: Solution of Large-Scale Sparse Least Squares Problems Using Auxiliary Storage
cites work: Q3664299
cites work: Q5827285
cites work: Large-scale geodetic least-squares adjustment by dissection and orthogonal decomposition
cites work: Extensions and Applications of the Householder Algorithm for Solving Linear Least Squares Problems
cites work: Solving Linear Algebraic Equations on an MIMD Computer
cites work: On Stable Parallel Linear System Solvers
cites work: Buffering for vector performance on a pipelined MIMD machine
description: scientific article; zbMATH DE number 3942903