hal-00723564, version 1
LU factorization with panel rank revealing pivoting and its communication avoiding version
N° RR-7867 (2012)
- 1 :
-
http://www.lri.fr/
CNRS : UMR8623 – Université Paris XI - Paris Sud LRI - Bâtiment 490 Université Paris-Sud 91405 Orsay Cedex France - 2 :
-
http://berkeley.edu/
UC Berkeley University of California, Berkeley Department of Mathematics Berkeley, CA 94720, USA États-Unis - 3 :
-
http://grand-large.lri.fr/index.php/Main_Page
INRIA – CNRS : UMR8623 – Université Paris XI - Paris Sud PCRI - Université de Paris-Sud, Bâtiment 650, 91405 ORSAY Cedex France
Références bibliographiques
- Type de publication : Rapports
- Domaine : Informatique/Analyse numérique
- Titre : LU factorization with panel rank revealing pivoting and its communication avoiding version
- Résumé : 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.
- Langue du document : Anglais
- Type de rapport : Rapport de recherche
- Date de publication : 25/01/2012
- Référence interne : RR-7867
Liste des fichiers attachés à ce document :
  |
|
 |
RR-7867.pdf(1.1 MB) |
|
|
TEX |
|
 |
alternative_alg.tex(9 KB) |
|
 |
RR.sty(14.9 KB) |
|
|
appendix.tex(72 KB) |
|
|
bounds.tex(9.5 KB) |
|
|
carrqrlu.bib(10.2 KB) |
|
|
carrqrlu.tex(19.2 KB) |
|
|
conclusions.tex(1.6 KB) |
|
|
introduction.tex(15.7 KB) |
|
 |
logo-inria.eps(367.9 KB) |
|
 |
logo-inria.png(275.1 KB) |
|
|
pagei.eps(5.4 MB) |
|
 |
pagei.png(26.9 KB) |
|
|
RR-7867.tex(5.8 KB) |
|
|
rrpage1.eps(2.8 MB) |
|
 |
rrpage1.png(47.6 KB) |
|
|
rrqrlu_algebra.tex(29.2 KB) |
|
|
stab_exp.tex(15.9 KB) |
|
|
figures |
|
 |
Bcalu_prrp1.png(15.2 KB) |
|
|
bcaluprrp.pdf(54.3 KB) |
|
 |
blockpairwise_luprrp.png(12.2 KB) |
|
 |
blockparallelluprrp.png(8 KB) |
|
 |
blockparallelluprrp1.png(7.5 KB) |
|
|
bluprrp1.pdf(34.4 KB) |
|
 |
BTGF.png(44.9 KB) |
|
 |
caluprrpVSgepp.png(17.1 KB) |
|
 |
caluprrpVSgepp1.png(6.8 KB) |
|
 |
Fcalu_prrp1.png(14 KB) |
|
|
fcaluprrp.pdf(23.3 KB) |
|
|
flatluprrp1.pdf(51.2 KB) |
|
 |
flatTree.png(6 KB) |
|
 |
FTRRQRvsRRQRMingn4096b32_1.png(4.2 KB) |
|
 |
FTScheme.png(7.7 KB) |
|
 |
gf4096BTb4.png(3 KB) |
|
 |
gf4096BTb4total.png(2.8 KB) |
|
 |
kahan4096_1.png(2.5 KB) |
|
|
luprrp1.pdf(25.6 KB) |
|
|
luprrp2.pdf(22.3 KB) |
|
 |
luprrp2.png(10.3 KB) |
|
 |
luprrp_1.png(9.3 KB) |
|
 |
luprrp_2.png(12.3 KB) |
|
 |
luprrpVSgepp.png(10 KB) |
|
 |
luprrpVSgepp1.png(5.5 KB) |
|
 |
patholurrqrwithouprep4096.png(2.5 KB) |
|
 |
RRQR_LU_FT_Schemeb2.png(5.9 KB) |
|
 |
RRQR_LU_FTPre_1.png(5.6 KB) |
|
 |
RRQR_LU_withoutPre1.png(4.8 KB) |
|
 |
RRQRvsRRQRMingn4096p64b32_1.png(3.9 KB) |
|
 |
RRQRvsRRQRMingnwithoutpre2048b32tau12.png(3.4 KB) |
- hal-00723564, version 1
- http://hal.inria.fr/hal-00723564
- oai:hal.inria.fr:hal-00723564
- Contributeur :
- Soumis le : Vendredi 10 Août 2012, 18:08:51
- Dernière modification le : Dimanche 12 Août 2012, 21:19:36
Documents associés
Exporter