Predicting the structure of sparse orthogonal factors
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.
- A Data Structure for Sparse QR and LU Factorizations
- Algorithmic Aspects of Vertex Elimination on Directed Graphs
- Combinatorial matrix theory
- Computing the block triangular form of a sparse matrix
- Connectivity and Reducibility of Graphs
- Coverings of Bipartite Graphs
- scientific article; zbMATH DE number 3149610 (Why is no real title available?)
- scientific article; zbMATH DE number 3420184 (Why is no real title available?)
- Matching theory
- Predicting fill for sparse orthogonal factorization
- Predicting Structure in Sparse Matrix Computations
- Predicting the structure of sparse orthogonal factors
- Remarks on implementation of O ( n 1/2 τ) assignment algorithms
- Solution of sparse linear least squares problems using Givens rotations
- Some Results on Sparse Matrices
- Sparse Matrices in MATLAB: Design and Implementation
- Sparsity Analysis of the QR Factorization
- Symbolic Factorization for Sparse Gaussian Elimination with Partial Pivoting
- Term Rank of the Direct Product of Matrices
- Two Algorithms for Bipartite Graphs
- Predicting the structure of sparse orthogonal factors
- Separators and structure prediction in sparse orthogonal factorization
- Patterns that preserve sparsity in orthogonal factorization
- On the diameter of tree associahedra
- A General Orthogonalization Technique with Applications to Time Series Analysis and Signal Processing
- Predicting fill for sparse orthogonal factorization
- Some Results on Structure Prediction in Sparse QR Factorization
- Approximation algorithms in combinatorial scientific computing
- A survey of direct methods for sparse linear systems
- Sparse linear least-squares problems
This page was built for publication: Predicting the structure of sparse orthogonal factors
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1318224)
