Separators and structure prediction in sparse orthogonal factorization

DOI10.1016/S0024-3795(97)80024-9zbMath0881.15015OpenAlexW2005687287MaRDI QIDQ1361831

Barry W. Peyton, John R. Gilbert, Esmond G. Ng

Publication date: 22 February 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)80024-9

zbMATH Keywords

sparse matrixHouseholder reflectionorthogonal factorizationHouseholder matrix\(QR\) factorization

Mathematics Subject Classification ID

Computational methods for sparse matrices (65F50) Factorization of matrices (15A23) Direct numerical methods for linear systems and matrix inversion (65F05)

Related Items

A Computational Study of Using Black-box QR Solvers for Large-scale Sparse-dense Linear Least Squares Problems, An efficient algorithm for sparse null space basis problem using ABS methods, Low Rank Approximation of a Sparse Matrix Based on LU Factorization with Column and Row Tournament Pivoting, Block computation and representation of a sparse nullspace basis of a rectangular matrix

Uses Software

• LINPACK
• symrcm

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Solution of sparse linear least squares problems using Givens rotations
• Predicting the structure of sparse orthogonal factors
• Sparsity Analysis of the $QR$ Factorization
• Nested Dissection for Sparse Nullspace Bases
• A separator theorem for graphs of bounded genus
• The Role of Elimination Trees in Sparse Factorization
• Sparse Orthogonal Schemes for Structural Optimization Using the Force Method
• Predicting fill for sparse orthogonal factorization
• Computing a Sparse Basis for the Null Space
• The Null Space Problem II. Algorithms
• A Data Structure for Sparse $QR$ and $LU$ Factorizations
• On the Complexity of Sparse $QR$ and $LU$ Factorization of Finite-Element Matrices
• A Separator Theorem for Planar Graphs
• Generalized Nested Dissection
• Sparse Matrices in MATLAB: Design and Implementation
• Algorithmic Aspects of Vertex Elimination on Graphs
• Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
• On Representatives of Subsets
• Some Results on Structure Prediction in Sparse $QR$ Factorization
• Multifrontal Computation with the Orthogonal Factors of Sparse Matrices
• Complexity Bounds for Regular Finite Difference and Finite Element Grids