Predicting the structure of sparse orthogonal factors
type: Item
instance of: scholarly article
title: Predicting the structure of sparse orthogonal factors
zbMATH Open document ID: 0797.65014
DOI: 10.1016/0024-3795(93)90121-4
author: Alex Pothen
published in: Linear Algebra and its Applications
publication date: 1994-03-27T00:00:00Z
review text: Given the structure of an \(m \times n\) real or complex matrix \(A\), where \(m \geq n\) and \(A\) has full column rank, the author considers the problem of correctly predicting the structure of its orthogonal factors \(Q\) and \(R\). Recently, \textit{D. R. Hare, C. R. Johnson, D. D. Olesky}, and \textit{P. van den Driessche} [SIAM J. Matrix Anal. Appl. 14, No. 3, 655-669 (1993; Zbl 0783.65038)] have described a method to predict these structures, and they have shown that corresponding to any specified nonzero element in the predicted structures of \(Q\) or \(R\), there exists a matrix \(A\) with the given structure whose factor has a nonzero element in that position. In the paper under review, this method is shown to satisfy a stronger property: there exist matrices with the structure of \(A\) whose factors have exactly the predicted structures. Efficient algorithms for computing the structures of the factors are designed, and the relationship between the structure of \(Q\) and the Householder array is also described.
reviewed by: Ferenc Móricz
Mathematics Subject Classification ID: 65F05
Mathematics Subject Classification ID: 65F30
Mathematics Subject Classification ID: 15A23
zbMATH DE Number: 540064
zbMATH Keywords: predicting the structure of sparse orthogonal factors
zbMATH Keywords: QR factorization
zbMATH Keywords: efficient algorithms
zbMATH Keywords: Householder array
describes a project that uses: symrcm
describes a project that uses: MA28
MaRDI profile type: Publication
full work available at URL: 0024-3795(93)90121-4
OpenAlex ID: W2069792133
cites work: Some Results on Sparse Matrices
cites work: Term Rank of the Direct Product of Matrices
cites work: Combinatorial matrix theory
cites work: Predicting fill for sparse orthogonal factorization
cites work: Remarks on implementation of O ( n 1/2 τ) assignment algorithms
cites work: Coverings of Bipartite Graphs
cites work: Q3266932
cites work: Two Algorithms for Bipartite Graphs
cites work: Solution of sparse linear least squares problems using Givens rotations
cites work: A Data Structure for Sparse $QR$ and $LU$ Factorizations
cites work: Symbolic Factorization for Sparse Gaussian Elimination with Partial Pivoting
cites work: Predicting Structure in Sparse Matrix Computations
cites work: Sparse Matrices in MATLAB: Design and Implementation
cites work: Sparsity Analysis of the $QR$ Factorization
cites work: Connectivity and Reducibility of Graphs
cites work: Matching theory
cites work: Computing the block triangular form of a sparse matrix
cites work: Q5683627
cites work: Algorithmic Aspects of Vertex Elimination on Directed Graphs
description: scientific article; zbMATH DE number 540064