Computing the Rank Profile Matrix

Jean-Guillaume Dumas (1) , Clément Pernet (2, 3) , Ziad Sultan (2, 1)

1 CASYS - Calculs Algébriques et Systèmes Dynamiques
2 MOAIS - PrograMming and scheduling design fOr Applications in Interactive Simulation
3 ARIC - Arithmetic and Computing

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.

Domaines: Calcul formel [cs.SC]

Jean-Guillaume Dumas, Clément Pernet, Ziad Sultan. Computing the Rank Profile Matrix. ISSAC, Steve Linton, Jul 2015, Bath, United Kingdom. pp.146--153, ⟨10.1145/2755996.2756682⟩. ⟨hal-01107722v2⟩