Symmetric indefinite triangular factorization revealing the rank profile matrix

DOI10.1145/3208976.3209019MaRDI QIDQ5120190zbMATH OpenOpenAlexWikidataFDO

Authors Jean-Guillaume Dumas, Clément Pernet

Publication date 9 September 2020

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

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

zbMATH Keywords

\(\mathbf{LDL}^T\)finite fieldrank profile matrixsymmetric Gaussian elimination

Mathematics Subject Classification ID

Numerical linear algebra (65F99) Symbolic computation and algebraic computation (68W30)

Abstract: We present a novel recursive algorithm for reducing a symmetric matrix to a triangular factorization which reveals the rank profile matrix. That is, the algorithm computes a factorization $mathbf{P}^{T}mathbfAmathbfP=mathbfLmathbfDmathbf{L}^T$ where $mathbfP$ is a permutation matrix, $mathbfL$ is lower triangular with a unit diagonal and $mathbfD$ is symmetric block diagonal with $1imes1$ and $2imes2$ antidiagonal blocks. The novel algorithm requires $O(n^2{r}^{omega-2})$ arithmetic operations. Furthermore, experimental results demonstrate that our algorithm can even be slightly more than twice as fast as the state of the art unsymmetric Gaussian elimination in most cases, that is it achieves approximately the same computational speed. By adapting the pivoting strategy developed in the unsymmetric case, we show how to recover the rank profile matrix from the permutation matrix and the support of the block-diagonal matrix. There is an obstruction in characteristic $2$ for revealing the rank profile matrix which requires to relax the shape of the block diagonal by allowing the 2-dimensional blocks to have a non-zero bottom-right coefficient. This relaxed decomposition can then be transformed into a standard $mathbfPmathbfLmathbfDmathbf{L}^{T}mathbf{P}^T$ decomposition at a negligible cost.

Recommendations

• Rank-revealing decomposition of symmetric indefinite matrices via block anti-triangular factorization
• Computing symmetric rank-revealing decompositions via triangular factorization
• Symmetric rank revealing factorizations
• Communication-avoiding symmetric-indefinite factorization
• Add-sub pivoting triangular factorization for symmetric matrix

Cited in

(6)

• Some fast algorithms multiplying a matrix by its adjoint
• Symmetric rank revealing factorizations
• Rank-revealing decomposition of symmetric indefinite matrices via block anti-triangular factorization
• Computing the rank profile matrix
• Simultaneous computation of the row and column rank profiles
• Fast in-place accumulation

This page was built for publication: Symmetric indefinite triangular factorization revealing the rank profile matrix

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