Patterns that preserve sparsity in orthogonal factorization

DOI10.1016/S0024-3795(97)00052-9MaRDI QIDQ1375102zbMATH OpenFDO

Authors Satoru Iwata, D. D. Olesky, P. van den Driessche

Publication date 8 July 1998

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0024-3795(97)00052-9

zbMATH Keywords

binary rooted treeHall propertyHasse diagrampatternQR factorizationsparsity

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Factorization of matrices (15A23) Direct numerical methods for linear systems and matrix inversion (65F05) Computational methods for sparse matrices (65F50)

Review text

An \(m\times n\) zero-nonzero pattern \({\mathcal A}\) with the Hall property allows a full rank matrix \(A\in{\mathcal A}\) with a QR factorization. The union of patterns occurring \(Q\) over all such \(A\) is denoted by \({\mathcal Q}\). By further restricting \({\mathcal A}\) to have the strong Hall property, a Hasse diagram, that is a forest, is used to characterize patterns \({\mathcal A}\) that yield \({\mathcal Q}= {\mathcal A}\), thus preserving the sparsity of \({\mathcal A}\). For fixed \(n\), the sparsest \(n\times n\) such patterns are characterized by a binary rooted tree.

Recommendations

• Sparsity Analysis of the QR Factorization
• Some Results on Structure Prediction in Sparse QR Factorization
• Predicting fill for sparse orthogonal factorization
• Separators and structure prediction in sparse orthogonal factorization
• scientific article; zbMATH DE number 554767

Cites work

• Computing the block triangular form of a sparse matrix
• Coverings of Bipartite Graphs
• scientific article; zbMATH DE number 53952 (Why is no real title available?)
• Predicting fill for sparse orthogonal factorization
• Predicting Structure in Sparse Matrix Computations
• Predicting the structure of sparse orthogonal factors
• Some Results on Structure Prediction in Sparse QR Factorization
• Sparsity Analysis of the QR Factorization
• Strong Hall Matrices

Cited in

(2)

• Separators and structure prediction in sparse orthogonal factorization
• Sparsity Analysis of the QR Factorization

This page was built for publication: Patterns that preserve sparsity in orthogonal factorization

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