Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
A Communication Optimization Scheme for Basis Computation of Krylov Subspace Methods on Multi-GPUs Kapitel lesen Erstes Kapitel lesen

2015 | OriginalPaper | Buchkapitel

Using Random Butterfly Transformations to Avoid Pivoting in Sparse Direct Methods

verfasst von : Marc Baboulin, Xiaoye S. Li, François-Henry Rouet

Erschienen in: High Performance Computing for Computational Science -- VECPAR 2014

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

We consider the solution of sparse linear systems using direct methods via LU factorization. Unless the matrix is positive definite, numerical pivoting is usually needed to ensure stability, which is costly to implement especially in the sparse case. The Random Butterfly Transformations (RBT) technique provides an alternative to pivoting and is easily parallelizable. The RBT transforms the original matrix into another one that can be factorized without pivoting with probability one. This approach has been successful for dense matrices; in this work, we investigate the sparse case. In particular, we address the issue of fill-in in the transformed system.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Vorheriges Kapitel Fault Tolerance in an Inner-Outer Solver: A GVR-Enabled Case Study
Nächstes Kapitel Hybrid Sparse Linear Solutions with Substituted Factorization
Literatur
1.
Anderson, E., Bai, Z., Dongarra, J.J., Greenbaum, A., McKenney, A., Du Croz, J., Hammarling, S., Demmel, J.W., Bischof, C., Sorensen, D.: LAPACK: a portable linear algebra library for high-performance computers. In: Proceedings of the 1990 ACM/IEEE Conference on Supercomputing (1990)
2.
Amestoy, P.R., Guermouche, A., L’Excellent, J.-Y., Pralet, S.: Hybrid scheduling for the parallel solution of linear systems. Parallel Comput. 32(2), 136–156 (2006)CrossRefMathSciNet
3.
Baboulin, M., Dongarra, J.J., Hermann, J., Tomov, S.: Accelerating linear system solutions using randomization techniques. ACM Trans. Math. Softw. 39(2), 1–13 (2013)CrossRef
4.
Baboulin, M., Becker, D., Dongarra, J.J.: A parallel tiled solver for dense symmetric indefinite systems on multicore architectures. In: Parallel & Distributed Processing Symposium (IPDPS) (2012)
5.
Baboulin, M., Becker, D., Bosilca, G., Danalis, A., Dongarra, J.J.: An efficient distributed randomized algorithm for solving large dense symmetric indefinite linear systems. Parallel Comput. 40(7), 213–223 (2014)CrossRefMathSciNet
6.
Becker, D., Baboulin, M., Dongarra, J.: Reducing the amount of pivoting in symmetric indefinite systems. In: Wyrzykowski, R., Dongarra, J., Karczewski, K., Waśniewski, J. (eds.) PPAM 2011. LNCS, vol. 7203, pp. 133–142. Springer, Heidelberg (2012)
7.
Blackford, L., Choi, J., Cleary, A., D’Azevedo, E., Demmel, J.W., Dhillon, I., Dongarra, J.J., Hammarling, S., Henry, G., Petitet, A., Stanley, K., Walker, D., Whaley, R.: ScaLAPACK Users’ Guide. SIAM, Philadelphia (1997) CrossRefMATH
8.
Bosilca, G., Bouteiller, A., Danalis, A., Herault, T., Lemarinier, P., Dongarra, J.J.: DAGuE: a generic distributed DAG engine for high performance computing. Parallel Comput. 38(1&2), 37–51 (2011)
9.
Demmel, J.W., Eisenstat, S.C., Gilbert, J.R., Li, X.S., Liu, J.W.H.: A supernodal approach to sparse partial pivoting. SIAM J. Matrix Anal. Appl. 20(3), 720–755 (1999)CrossRefMATHMathSciNet
10.
Duff, I.S., Erisman, I.M., Reid, J.K.: Direct Methods for Sparse Matrices. Oxford University Press, London (1986) MATH
11.
Duff, I.S., Koster, J.: The design and use of algorithms for permuting large entries to the diagonal of sparse matrices. SIAM J. Matrix Anal. Appl. 20(4), 889–901 (1999)CrossRefMATHMathSciNet
12.
George, A., Ng, E.: Symbolic factorization for sparse Gaussian elimination with partial pivoting. SIAM J. Sci. Stat. Comput. 8(6), 877–898 (1987)CrossRefMATHMathSciNet
13.
Higham, N.J.: Accuracy and Stability of Numerical Algorithms. SIAM, Philadelphia (2002) CrossRefMATH
14.
Li, X.S., Demmel, J.W.: SuperLU_DIST: a scalable distributed-memory sparse direct solver for unsymmetric linear systems. ACM Trans. Math. Softw. 29(9), 110–140 (2003)CrossRefMATHMathSciNet
15.
Parker, D.S.: Explicit formulas for the results of Gaussian elimination, Technical report CSD-950025, UCLA Computer Science Department (1995)
16.
Parker, D.S.: Random butterfly transformations with applications in computational linear algebra, Technical report CSD-950023, UCLA Computer Science Department (1995)
17.
PLASMA users’ guide, parallel linear algebra software for multicore architectures, Version 2.3 (2010). University of Tennessee
18.
Riedy, E.J.: Making static pivoting scalable and dependable, Technical report, UC Berkeley, EECS-2010-172 (2010)
19.
Schenk, O., Gärtner, K.: Solving unsymmetric sparse systems of linear equations with PARDISO. Future Gener. Comput. Syst. 20, 476–487 (2004)CrossRef
20.
Tomov, S., Dongarra, J.J., Baboulin, M.: Towards dense linear algebra for hybrid GPU accelerated manycore systems. Parallel Comput. 36(5&6), 232–240 (2010)CrossRefMATH
Metadaten
Titel
Using Random Butterfly Transformations to Avoid Pivoting in Sparse Direct Methods
verfasst von
Marc Baboulin
Xiaoye S. Li
François-Henry Rouet
Copyright-Jahr
2015
Buch
High Performance Computing for Computational Science -- VECPAR 2014

Print ISBN: 978-3-319-17352-8

Electronic ISBN: 978-3-319-17353-5

Copyright-Jahr: 2015

DOI
https://doi.org/10.1007/978-3-319-17353-5_12