Name
Abstract | ||
|---|---|---|
The row (resp. column) rank profile of a matrix describes the stair case 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 Gaussian elimination algorithm reveal this information. 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. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1145/2755996.2756682 | International Symposium on Symbolic and Algebraic Computation |
Keywords | Field | DocType |
Gaussian elimination, Rank profile, Echelon form, PLUQ decomposition | Rank (linear algebra),Row and column spaces,Discrete mathematics,Combinatorics,Elementary matrix,Augmented matrix,Pivot element,Gaussian elimination,Row echelon form,LU decomposition,Mathematics | Journal |
Volume | ISSN | Citations |
abs/1501.05239 | ACM International Symposium on Symbolic and Algebraic
Computations, pp.146--153, 2015, ISSAC 2015 | 7 |
PageRank | References | Authors |
0.52 | 9 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jean-Guillaume Dumas | 1 | 428 | 68.48 |
| Clément Pernet | 2 | 243 | 39.00 |
| Ziad Sultan | 3 | 33 | 2.80 |