Rank revealing Gaussian elimination by the maximum volume concept
From MaRDI portal
Publication:1987003
Abstract: A Gaussian elimination algorithm is presented that reveals the numerical rank of a matrix by yielding small entries in the Schur complement. The algorithm uses the maximum volume concept to find a square nonsingular submatrix of maximum dimension. The bounds on the revealed singular values are similar to the best known bounds for rank revealing LU factorization, but in contrast to existing methods the algorithm does not make use of the normal matrix. An implementation for dense matrices is described whose computational cost is roughly twice the cost of an LU factorization with complete pivoting. Because of its flexibility in choosing pivot elements, the algorithm is amenable to implementation with blocked memory access and for sparse matrices.
The authors present an algorithm for revealing the numerical rank of matrices by using the Gaussian elimination method. The bounds on the singular values is consistent with previous results available in the literature, but the algorithm presented here does not make use of the normal matrix. It can be implemented with blocked memory access to achieve high floating point performance on dense matrices.
Recommendations
- Low‐rank revealing QR factorizations
- Efficient Algorithms for Computing a Strong Rank-Revealing QR Factorization
- Computing rank-revealing QR factorizations of dense matrices
- A block algorithm for computing rank-revealing QR factorizations
- On the existence and computation of rank-revealing LU factorizations
Cites work
- A volume associated with \(m{\times}n\) matrices
- Efficient Algorithms for Computing a Strong Rank-Revealing QR Factorization
- How to find a good submatrix
- scientific article; zbMATH DE number 5060482 (Why is no real title available?)
- scientific article; zbMATH DE number 961607 (Why is no real title available?)
- Manifestations of the Schur complement
- On the existence and computation of rank-revealing LU factorizations
- Row Modifications of a Sparse Cholesky Factorization
- Semi-optimal bases for linear dependencies
- The least squares problem and pseudo-inverses
- The maximal-volume concept in approximation by low-rank matrices
- Updated triangular factors of the basis to maintain sparsity in the product form simplex method
Cited in
(13)- Gaussian elimination and the ranks of the components in the Cartesian decomposition of a matrix
- On the existence and computation of rank-revealing LU factorizations
- Rank-profile revealing Gaussian elimination and the CUP matrix decomposition
- Computing the rank profile matrix
- Maximum Volume Inscribed Ellipsoid: A New Simplex-Structured Matrix Factorization Framework via Facet Enumeration and Convex Optimization
- A Rank-Revealing Method with Updating, Downdating, and Applications
- Polynomial time \(\rho\)-locally maximum volume search
- Revisiting degeneracy, strict feasibility, stability, in linear programming
- Maximal volume matrix cross approximation for image compression and least squares solution
- Interior point methods in the year 2025
- Estimating a matrix's singular values with interpolative decompositions
- Certifying solutions of degenerate semidefinite programs
- Entry growth in Gaussian elimination
This page was built for publication: Rank revealing Gaussian elimination by the maximum volume concept
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1987003)
