Paper Info
Title
Simultaneous computation of the row and column rank profiles
Abstract
Gaussian elimination with full pivoting generates a PLUQ matrix decomposition. Depending on the strategy used in the search for pivots, the permutation matrices can reveal some information about the row or the column rank profiles of the matrix. We propose a new pivoting strategy that makes it possible to recover at the same time both row and column rank profiles of the input matrix and of any of its leading sub-matrices. We propose a rank-sensitive and quad-recursive algorithm that computes the latter PLUQ triangular decomposition of an m x n matrix of rank r in O(mnrω-2) field operations, with ω the exponent of matrix multiplication. Compared to the LEU decomposition by Malashonock, sharing a similar recursive structure, its time complexity is rank sensitive and has a lower leading constant. Over a word size finite field, this algorithm also improves the practical efficiency of previously known implementations.
Year
DOI
Venue
2013
10.1145/2465506.2465517
international symposium on symbolic and algebraic computation
Keywords
DocType
Volume
field operation,leu decomposition,permutation matrix,column rank profile,n matrix,pluq matrix decomposition,simultaneous computation,matrix multiplication,input matrix,rank r,latter pluq triangular decomposition,finite field,gaussian elimination
Conference
abs/1301.4438
ISSN
Citations 
PageRank 
ISSAC 2013, Boston, MA : \'Etats-Unis (2013)
11
0.75
References 
Authors
7
3
Name
Order
Citations
PageRank
Jean-Guillaume Dumas142868.48
Clément Pernet224339.00
Ziad Sultan3332.80