Paper Info
Title
Symmetric Indefinite Triangular Factorization Revealing The Rank Profile Matrix
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 P-T AP = LDLT where P is a permutation matrix, L is lower triangular with a unit diagonal and D is symmetric block diagonal with 1x1 and 2x2 antidiagonal blocks. This algorithm requires O(n(2)r(omega-2)) arithmetic operations, with n the dimension of the matrix, r its rank and. an admissible exponent for matrix multiplication. Furthermore, experimental results demonstrate that our algorithm has very good performance: its computational speed matches that of its numerical counterpart and is twice as fast as the unsymmetric exact Gaussian factorization. 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. We also note that 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 PLDLT PT decomposition at a negligible cost.
Year
DOI
Venue
2018
10.1145/3208976.3209019
ISSAC'18: PROCEEDINGS OF THE 2018 ACM INTERNATIONAL SYMPOSIUM ON SYMBOLIC AND ALGEBRAIC COMPUTATION
DocType
Volume
Citations 
Conference
abs/1802.10453
0
PageRank 
References 
Authors
0.34
9
2
Name
Order
Citations
PageRank
Jean-Guillaume Dumas142868.48
Clément Pernet224339.00