Separators and structure prediction in sparse orthogonal factorization
Let \(A\) be an \(m\times n\) matrix, \(m\geq n\), and let \(A=QR\), where \(Q\) is an \(m\times n\) matrix with orthogonal columns that span the range of \(A\) and \(R\) is an \(n \times n\) upper triangular matrix with positive diagonal elements. Then \(Q= H_1\cdots H_n\), where \(H_i\) is a Householder reflection with reflection vector \(h_i\). The matrix \(H\) with columns \(h_i\) is called a Householder matrix. The authors consider the \(QR\) factorization of a sparse matrix \(A\). They investigate when \(H\) is much sparser than \(A\) and related questions.
- Predicting the structure of sparse orthogonal factors
- scientific article; zbMATH DE number 554767
- Hierarchical orthogonal factorization: sparse least squares problems
- Some Results on Structure Prediction in Sparse QR Factorization
- Predicting fill for sparse orthogonal factorization
- Structure prediction and computation of sparse matrix products
- Hierarchical orthogonal factorization: sparse square matrices
- Patterns that preserve sparsity in orthogonal factorization
- Fast separable factorization and applications
- Predicting Structure in Sparse Matrix Computations
- A Data Structure for Sparse QR and LU Factorizations
- A separator theorem for graphs of bounded genus
- A Separator Theorem for Planar Graphs
- Algorithmic Aspects of Vertex Elimination on Graphs
- Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
- Combinatorial matrix theory
- Complexity Bounds for Regular Finite Difference and Finite Element Grids
- Computing a Sparse Basis for the Null Space
- Generalized Nested Dissection
- scientific article; zbMATH DE number 3816913 (Why is no real title available?)
- scientific article; zbMATH DE number 4002053 (Why is no real title available?)
- scientific article; zbMATH DE number 3748409 (Why is no real title available?)
- scientific article; zbMATH DE number 554763 (Why is no real title available?)
- scientific article; zbMATH DE number 554764 (Why is no real title available?)
- scientific article; zbMATH DE number 554767 (Why is no real title available?)
- Multifrontal Computation with the Orthogonal Factors of Sparse Matrices
- Nested Dissection for Sparse Nullspace Bases
- On Representatives of Subsets
- On the Complexity of Sparse QR and LU Factorization of Finite-Element Matrices
- Predicting fill for sparse orthogonal factorization
- Predicting the structure of sparse orthogonal factors
- Solution of sparse linear least squares problems using Givens rotations
- Some Results on Structure Prediction in Sparse QR Factorization
- Sparse Matrices in MATLAB: Design and Implementation
- Sparse Orthogonal Schemes for Structural Optimization Using the Force Method
- Sparsity Analysis of the QR Factorization
- The Null Space Problem II. Algorithms
- The Role of Elimination Trees in Sparse Factorization
- Householder reflections versus Givens rotations in sparse orthogonal decomposition
- Predicting the structure of sparse orthogonal factors
- Patterns that preserve sparsity in orthogonal factorization
- An efficient algorithm for sparse null space basis problem using ABS methods
- Orthogonal Reduction of Sparse Matrices to Upper Triangular Form Using Householder Transformations
- Low Rank Approximation of a Sparse Matrix Based on LU Factorization with Column and Row Tournament Pivoting
- Some Results on Structure Prediction in Sparse QR Factorization
- A Computational Study of Using Black-box QR Solvers for Large-scale Sparse-dense Linear Least Squares Problems
- Block computation and representation of a sparse nullspace basis of a rectangular matrix
This page was built for publication: Separators and structure prediction in sparse orthogonal factorization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1361831)
