LU factorization with panel rank revealing pivoting and its communication avoiding version

Amal Khabou 1 James Demmel 2 Laura Grigori 3 Ming Gu 2
3 GRAND-LARGE - Global parallel and distributed computing
LRI - Laboratoire de Recherche en Informatique, LIFL - Laboratoire d'Informatique Fondamentale de Lille, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8623
Abstract : We present the LU decomposition with panel rank revealing pivoting (LU_PRRP), an LU factorization algorithm based on strong rank revealing QR panel factorization. LU_PRRP is more stable than Gaussian elimination with partial pivoting (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 and easily solves the Wilkinson matrix and the Foster matrix. We also present CALU_PRRP, a communication avoiding version of LU_PRRP that minimizes communication. CALU_PRRP 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. CALU_PRRP is more stable than CALU, the communication avoiding version of GEPP. CALU_PRRP is also more stable in practice and is resistant to pathological cases on which GEPP and CALU fail.
Type de document :
Rapport
[Research Report] RR-7867, INRIA. 2012
Liste complète des métadonnées

Littérature citée [20 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00723564
Contributeur : Amal Khabou <>
Soumis le : vendredi 10 août 2012 - 18:08:51
Dernière modification le : jeudi 5 avril 2018 - 12:30:12
Document(s) archivé(s) le : vendredi 16 décembre 2016 - 05:37:14

Fichiers

RR-7867.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00723564, version 1
  • ARXIV : 1208.2451

Collections

Citation

Amal Khabou, James Demmel, Laura Grigori, Ming Gu. LU factorization with panel rank revealing pivoting and its communication avoiding version. [Research Report] RR-7867, INRIA. 2012. 〈hal-00723564〉

Partager

Métriques

Consultations de la notice

376

Téléchargements de fichiers

177