Computing the rank profile matrix

DOI10.1145/2755996.2756682zbMATH Open1345.65019arXiv1501.05239OpenAlexW3102665839MaRDI QIDQ2819752FDOQ2819752

Authors: Jean-Guillaume Dumas, Clément Pernet, Ziad Sultan 

Publication date: 29 September 2016

Published in: Proceedings of the 2015 ACM on International Symposium on Symbolic and Algebraic Computation (Search for Journal in Brave)

Abstract: The row (resp. column) rank profile of a matrix describes the staircase shape of its row (resp. column) echelon form. In an ISSAC'13 paper, we proposed a recursive Gaussian elimination that can compute simultaneously the row and column rank profiles of a matrix as well as those of all of its leading sub-matrices, in the same time as state of the art Gaussian elimination algorithms. Here we first study the conditions making a Gaus-sian elimination algorithm reveal this information. Therefore, we propose the definition of a new matrix invariant, the rank profile matrix, summarizing all information on the row and column rank profiles of all the leading sub-matrices. We also explore the conditions for a Gaussian elimination algorithm to compute all or part of this invariant, through the corresponding PLUQ decomposition. As a consequence, we show that the classical iterative CUP decomposition algorithm can actually be adapted to compute the rank profile matrix. Used, in a Crout variant, as a base-case to our ISSAC'13 implementation, it delivers a significant improvement in efficiency. Second, the row (resp. column) echelon form of a matrix are usually computed via different dedicated triangular decompositions. We show here that, from some PLUQ decompositions, it is possible to recover the row and column echelon forms of a matrix and of any of its leading sub-matrices thanks to an elementary post-processing algorithm.

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

Recommendations

• Fast computation of the rank profile matrix and the generalized Bruhat decomposition
• Simultaneous computation of the row and column rank profiles
• Rank-profile revealing Gaussian elimination and the CUP matrix decomposition
• Symmetric indefinite triangular factorization revealing the rank profile matrix
• Rank revealing Gaussian elimination by the maximum volume concept

zbMATH Keywords

Gaussian eliminationechelon formrank profilePLUQ decomposition

Mathematics Subject Classification ID

Direct numerical methods for linear systems and matrix inversion (65F05) Symbolic computation and algebraic computation (68W30)

Cited In (7)

• Verification protocols with sub-linear communication for polynomial matrix operations
• Rank-profile revealing Gaussian elimination and the CUP matrix decomposition
• Fast computation of the rank profile matrix and the generalized Bruhat decomposition
• Simultaneous computation of the row and column rank profiles
• Computing Sparse Representations of Systems of Rational Fractions
• Computing rank-width exactly
• Time and space efficient generators for quasiseparable matrices

This page was built for publication: Computing the rank profile matrix

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2819752)