Rank-profile revealing Gaussian elimination and the CUP matrix decomposition

DOI10.1016/J.JSC.2013.04.004zbMATH Open1329.65065arXiv1112.5717OpenAlexW1991713476MaRDI QIDQ2437224FDOQ2437224

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

Publication date: 3 March 2014

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

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.

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

Recommendations

• Computing the rank profile matrix
• Fast computation of the rank profile matrix and the generalized Bruhat decomposition
• Simultaneous computation of the row and column rank profiles
• Rank revealing Gaussian elimination by the maximum volume concept
• A New Algorithm for Computing the Rank of a Matrix

zbMATH Keywords

Gaussian eliminationrankechelon formrank profilereduced echelon formfast linear algebrain-place computationsLU matrix decomposition

Mathematics Subject Classification ID

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

Cites Work

• LAPACK Users' Guide
• The M4RIE library for dense linear algebra over small fields with even characteristic
• Title not available (Why is that?)
• Title not available (Why is that?)
• A new efficient algorithm for computing Gröbner bases \((F_4)\)
• Gaussian elimination is not optimal
• Modular forms, a computational approach. With an appendix by Paul E. Gunnells
• Title not available (Why is that?)
• Triangular Factorization and Inversion by Fast Matrix Multiplication
• Multiplying matrices faster than coppersmith-winograd
• On multiplication of 2 \(\times\) 2 matrices
• A set of level 3 basic linear algebra subprograms
• Title not available (Why is that?)
• ROUNDING-OFF ERRORS IN MATRIX PROCESSES
• Memory efficient scheduling of Strassen-Winograd's matrix multiplication algorithm
• Title not available (Why is that?)
• LU factoring of non-invertible matrices
• A generalization of the fast LUP matrix decomposition algorithm and applications
• Title not available (Why is that?)
• Fast algorithms for the characteristic polynomial
• Gaussian elimination: a case study in efficient genericity with MetaOCaml
• 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

Uses Software

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

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)