LU Factorization with Panel Rank Revealing Pivoting and its Communication Avoiding Version

Amal Khabou 1 James Demmel 2 Laura Grigori 3 Ming Gu 2
1 ParSys - LRI - Systèmes parallèles (LRI)
LRI - Laboratoire de Recherche en Informatique
3 ALPINES - Algorithms and parallel tools for integrated numerical simulations
LJLL - Laboratoire Jacques-Louis Lions, Inria Paris-Rocquencourt, Institut National des Sciences Mathématiques et de leurs Interactions
Abstract : We present block LU factorization with panel rank revealing pivoting (block LU PRRP), a decomposition algorithm based on strong rank revealing QR panel factorization. Block LU PRRP is more stable than Gaussian elimination with partial pivoting (GEPP), with a theoretical upper bound of the growth factor of (1 + τb)(n/b)−1, where b is the size of the panel used during the block factorization, τ is a parameter of the strong rank revealing QR factorization, n is the number of columns of the matrix, and for simplicity we assume that n is a multiple of b. We also assume throughout the paper that 2 ≤ b n. For example, if the size of the panel is b = 64, and τ = 2, then (1+2b)(n/b)−1 = (1.079)n−64 2n−1, where 2n−1 is the upper bound of the growth factor of GEPP. Our extensive numerical experiments show that the new factorization scheme is as numerically stable as GEPP in practice, but it is more resistant to pathological cases. The block LU PRRP factorization does only O(n2b) additional floating point operations compared to GEPP. We also present block CALU PRRP, a version of block LU PRRP that minimizes communication and is based on tournament pivoting, with the selection of the pivots at each step of the tournament being performed via strong rank revealing QR factorization. Block CALU PRRP is more stable than CALU, the communication avoiding version of GEPP, with a theoretical upper bound of the growth factor of (1 + τb) nb (H+1)−1, where H is the height of the reduction tree used during tournament pivoting. The upper bound of the growth factor of CALU is 2n(H+1)−1. Block CALU PRRP is also more stable in practice and is resistant to pathological cases on which GEPP and CALU fail.
Type de document :
Article dans une revue
SIAM Journal on Matrix Analysis and Applications, Society for Industrial and Applied Mathematics, 2013, 34 (3), 〈http://epubs.siam.org/toc/sjmael/34/3〉. 〈10.1137/120863691〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00872145
Contributeur : Laura Grigori <>
Soumis le : vendredi 11 octobre 2013 - 12:01:44
Dernière modification le : vendredi 31 août 2018 - 09:06:03

Lien texte intégral

Identifiants

Collections

Citation

Amal Khabou, James Demmel, Laura Grigori, Ming Gu. LU Factorization with Panel Rank Revealing Pivoting and its Communication Avoiding Version. SIAM Journal on Matrix Analysis and Applications, Society for Industrial and Applied Mathematics, 2013, 34 (3), 〈http://epubs.siam.org/toc/sjmael/34/3〉. 〈10.1137/120863691〉. 〈hal-00872145〉

Partager

Métriques

Consultations de la notice

441