Simultaneous computation of the row and column rank profiles

DOI10.1145/2465506.2465517zbMATH Open1360.65122arXiv1301.4438OpenAlexW2127691925MaRDI QIDQ2963232FDOQ2963232

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

Publication date: 10 February 2017

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

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 imes n matrix of rank r in O(mnr^{omega-2}) field operations, with omega 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 improveLs the practical efficiency of previously known implementations.

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

Recommendations

• Computing the rank profile matrix
• Fast computation of the rank profile matrix and the generalized Bruhat decomposition
• Rank-profile revealing Gaussian elimination and the CUP matrix decomposition
• Symmetric indefinite triangular factorization revealing the rank profile matrix
• Strong rank revealing LU factorizations

zbMATH Keywords

Gaussian eliminationfinite fieldrank profileFFLAS-FFPACK

Mathematics Subject Classification ID

Complexity and performance of numerical algorithms (65Y20) Vector spaces, linear dependence, rank, lineability (15A03)

Cited In (6)

• Rank-profile revealing Gaussian elimination and the CUP matrix decomposition
• Fast computation of the rank profile matrix and the generalized Bruhat decomposition
• An improvement over the GVW algorithm for inhomogeneous polynomial systems
• Elimination-based certificates for triangular equivalence and rank profiles
• Computing the rank profile matrix
• Time and space efficient generators for quasiseparable matrices

Uses Software

• FFLAS-FFPACK

This page was built for publication: Simultaneous computation of the row and column rank profiles

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