Rank-profile revealing Gaussian elimination and the CUP matrix decomposition
From MaRDI portal
Publication:2437224
Abstract: Transforming a matrix over a field to echelon form, or decomposing the matrix as a product of structured matrices that reveal the rank profile, is a fundamental building block of computational exact linear algebra. This paper surveys the well known variations of such decompositions and transformations that have been proposed in the literature. We present an algorithm to compute the CUP decomposition of a matrix, adapted from the LSP algorithm of Ibarra, Moran and Hui (1982), and show reductions from the other most common Gaussian elimination based matrix transformations and decompositions to the CUP decomposition. We discuss the advantages of the CUP algorithm over other existing algorithms by studying time and space complexities: the asymptotic time complexity is rank sensitive, and comparing the constants of the leading terms, the algorithms for computing matrix invariants based on the CUP decomposition are always at least as good except in one case. We also show that the CUP algorithm, as well as the computation of other invariants such as transformation to reduced column echelon form using the CUP algorithm, all work in place, allowing for example to compute the inverse of a matrix on the same storage as the input matrix.
Recommendations
Cites work
- scientific article; zbMATH DE number 3511563 (Why is no real title available?)
- scientific article; zbMATH DE number 1305088 (Why is no real title available?)
- scientific article; zbMATH DE number 976329 (Why is no real title available?)
- scientific article; zbMATH DE number 1936673 (Why is no real title available?)
- scientific article; zbMATH DE number 2151219 (Why is no real title available?)
- scientific article; zbMATH DE number 961607 (Why is no real title available?)
- A generalization of the fast LUP matrix decomposition algorithm and applications
- A new efficient algorithm for computing Gröbner bases (F₄)
- A set of level 3 basic linear algebra subprograms
- Fast algorithms for the characteristic polynomial
- Gaussian elimination is not optimal
- Gaussian elimination: a case study in efficient genericity with MetaOCaml
- LAPACK Users' Guide
- LU factoring of non-invertible matrices
- Memory efficient scheduling of Strassen-Winograd's matrix multiplication algorithm
- Modular forms, a computational approach. With an appendix by Paul E. Gunnells
- Multiplying matrices faster than coppersmith-winograd
- On multiplication of 2 2 matrices
- ROUNDING-OFF ERRORS IN MATRIX PROCESSES
- The M4RIE library for dense linear algebra over small fields with even characteristic
- Triangular Factorization and Inversion by Fast Matrix Multiplication
- Unitäre Transformationen großer Matrizen
Cited in
(15)- Verification protocols with sub-linear communication for polynomial matrix operations
- Exact computations with quasiseparable matrices
- Solving equations and optimization problems with uncertainty
- High-order lifting for polynomial Sylvester matrices
- Computational Number Theory, Past, Present, and Future
- Gauss-Jordan elimination method for computing all types of generalized inverses related to the {1}-inverse
- Fast computation of the rank profile matrix and the generalized Bruhat decomposition
- Improving the Complexity of Block Low-Rank Factorizations with Fast Matrix Arithmetic
- Refined F5 Algorithms for Ideals of Minors of Square Matrices
- Simultaneous computation of the row and column rank profiles
- Fast matrix decomposition in \(\mathbb F_2\)
- Elimination-based certificates for triangular equivalence and rank profiles
- Computing the rank profile matrix
- Time and space efficient generators for quasiseparable matrices
- Almost all subgeneric third-order Chow decompositions are identifiable
This page was built for publication: Rank-profile revealing Gaussian elimination and the CUP matrix decomposition
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2437224)
