Symmetric indefinite triangular factorization revealing the rank profile matrix - CASYS Accéder directement au contenu
Communication Dans Un Congrès Année : 2018

Symmetric indefinite triangular factorization revealing the rank profile matrix

Résumé

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 = LDL T where P is a permutation matrix, L is lower triangular with a unit diagonal and D is symmetric block diagonal with 1×1 and 2×2 antidiagonal blocks. The novel algorithm requires O(n 2 r ω−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 Gaus-sian 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 PLDL T P T decomposition at a negligible cost.
Fichier principal
Vignette du fichier
ldlt.pdf (452.08 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01704793 , version 1 (26-02-2018)

Identifiants

Citer

Jean-Guillaume Dumas, Clément Pernet. Symmetric indefinite triangular factorization revealing the rank profile matrix. ISSAC'18, Jul 2018, New York, United States. pp.151-158, ⟨10.1145/3208976.3209019⟩. ⟨hal-01704793⟩
206 Consultations
584 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More