Rank-profile revealing Gaussian elimination and the CUP matrix decomposition

DOI10.1016/j.jsc.2013.04.004zbMath1329.65065arXiv1112.5717OpenAlexW1991713476MaRDI QIDQ2437224

Arne Storjohann, Clément Pernet, Claude-Pierre Jeannerod

Publication date: 3 March 2014

Published in: Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1112.5717

zbMATH Keywords

Gaussian eliminationrankrank profileechelon formreduced echelon formfast linear algebrain-place computationsLU matrix decomposition

Mathematics Subject Classification ID

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

Related Items

Solving equations and optimization problems with uncertainty ⋮ Fast computation of the rank profile matrix and the generalized Bruhat decomposition ⋮ Time and space efficient generators for quasiseparable matrices ⋮ Refined F5 Algorithms for Ideals of Minors of Square Matrices ⋮ Exact computations with quasiseparable matrices ⋮ Computational Number Theory, Past, Present, and Future ⋮ High-order lifting for polynomial Sylvester matrices ⋮ Verification protocols with sub-linear communication for polynomial matrix operations ⋮ Elimination-based certificates for triangular equivalence and rank profiles ⋮ Fast matrix decomposition in \(\mathbb F_2\) ⋮ Improving the Complexity of Block Low-Rank Factorizations with Fast Matrix Arithmetic ⋮ Almost all subgeneric third-order Chow decompositions are identifiable ⋮ Gauss-Jordan elimination method for computing all types of generalized inverses related to the {1}-inverse

Uses Software

• FFLAS-FFPACK
• LAPACK
• M4RI
• BLAS
• M4RIE
• Python

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fast algorithms for the characteristic polynomial
• A new efficient algorithm for computing Gröbner bases \((F_4)\)
• Gaussian elimination: a case study in efficient genericity with MetaOCaml
• Gaussian elimination is not optimal
• On multiplication of 2 \(\times\) 2 matrices
• Unitäre Transformationen großer Matrizen
• Memory efficient scheduling of Strassen-Winograd's matrix multiplication algorithm
• LAPACK Users' Guide
• A generalization of the fast LUP matrix decomposition algorithm and applications
• A set of level 3 basic linear algebra subprograms
• Triangular Factorization and Inversion by Fast Matrix Multiplication
• LU factoring of non-invertible matrices
• The M4RIE library for dense linear algebra over small fields with even characteristic
• Multiplying matrices faster than coppersmith-winograd
• ROUNDING-OFF ERRORS IN MATRIX PROCESSES