The Non–Symmetric s–Step Lanczos Algorithm: Derivation of Efficient Recurrences and Synchronization–Reducing Variants of BiCG and QMR
The Lanczos algorithm is among the most frequently used iterative techniques for computing a few dominant eigenvalues of a large sparse non-symmetric matrix. At the same time, it serves as a building block within biconjugate gradient (BiCG) and quasi-minimal residual (QMR) methods for solving large...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Sciendo
2015-12-01
|
| Series: | International Journal of Applied Mathematics and Computer Science |
| Subjects: | |
| Online Access: | https://doi.org/10.1515/amcs-2015-0055 |
| _version_ | 1818909235286638592 |
|---|---|
| author | Feuerriegel Stefan Bücker H. Martin |
| author_facet | Feuerriegel Stefan Bücker H. Martin |
| author_sort | Feuerriegel Stefan |
| collection | DOAJ |
| description | The Lanczos algorithm is among the most frequently used iterative techniques for computing a few dominant eigenvalues of a large sparse non-symmetric matrix. At the same time, it serves as a building block within biconjugate gradient (BiCG) and quasi-minimal residual (QMR) methods for solving large sparse non-symmetric systems of linear equations. It is well known that, when implemented on distributed-memory computers with a huge number of processes, the synchronization time spent on computing dot products increasingly limits the parallel scalability. Therefore, we propose synchronization-reducing variants of the Lanczos, as well as BiCG and QMR methods, in an attempt to mitigate these negative performance effects. These so-called s-step algorithms are based on grouping dot products for joint execution and replacing time-consuming matrix operations by efficient vector recurrences. The purpose of this paper is to provide a rigorous derivation of the recurrences for the s-step Lanczos algorithm, introduce s-step BiCG and QMR variants, and compare the parallel performance of these new s-step versions with previous algorithms. |
| first_indexed | 2024-12-19T22:23:41Z |
| format | Article |
| id | doaj.art-4bb2af957f604e3fba66473f017aa78e |
| institution | Directory Open Access Journal |
| issn | 2083-8492 |
| language | English |
| last_indexed | 2024-12-19T22:23:41Z |
| publishDate | 2015-12-01 |
| publisher | Sciendo |
| record_format | Article |
| series | International Journal of Applied Mathematics and Computer Science |
| spelling | doaj.art-4bb2af957f604e3fba66473f017aa78e2022-12-21T20:03:33ZengSciendoInternational Journal of Applied Mathematics and Computer Science2083-84922015-12-0125476978510.1515/amcs-2015-0055amcs-2015-0055The Non–Symmetric s–Step Lanczos Algorithm: Derivation of Efficient Recurrences and Synchronization–Reducing Variants of BiCG and QMRFeuerriegel Stefan0Bücker H. Martin1Chair for Information Systems Research, University of Freiburg, Platz der Alten Synagoge, 79098 Freiburg, GermanyChair for Advanced Computing, Friedrich Schiller University Jena, Ernst-Abbe-Platz 2, 07743 Jena, GermanyThe Lanczos algorithm is among the most frequently used iterative techniques for computing a few dominant eigenvalues of a large sparse non-symmetric matrix. At the same time, it serves as a building block within biconjugate gradient (BiCG) and quasi-minimal residual (QMR) methods for solving large sparse non-symmetric systems of linear equations. It is well known that, when implemented on distributed-memory computers with a huge number of processes, the synchronization time spent on computing dot products increasingly limits the parallel scalability. Therefore, we propose synchronization-reducing variants of the Lanczos, as well as BiCG and QMR methods, in an attempt to mitigate these negative performance effects. These so-called s-step algorithms are based on grouping dot products for joint execution and replacing time-consuming matrix operations by efficient vector recurrences. The purpose of this paper is to provide a rigorous derivation of the recurrences for the s-step Lanczos algorithm, introduce s-step BiCG and QMR variants, and compare the parallel performance of these new s-step versions with previous algorithms.https://doi.org/10.1515/amcs-2015-0055synchronization-reducings-step lanczoss-step bicgs-step qmrefficient recurrences |
| spellingShingle | Feuerriegel Stefan Bücker H. Martin The Non–Symmetric s–Step Lanczos Algorithm: Derivation of Efficient Recurrences and Synchronization–Reducing Variants of BiCG and QMR International Journal of Applied Mathematics and Computer Science synchronization-reducing s-step lanczos s-step bicg s-step qmr efficient recurrences |
| title | The Non–Symmetric s–Step Lanczos Algorithm: Derivation of Efficient Recurrences and Synchronization–Reducing Variants of BiCG and QMR |
| title_full | The Non–Symmetric s–Step Lanczos Algorithm: Derivation of Efficient Recurrences and Synchronization–Reducing Variants of BiCG and QMR |
| title_fullStr | The Non–Symmetric s–Step Lanczos Algorithm: Derivation of Efficient Recurrences and Synchronization–Reducing Variants of BiCG and QMR |
| title_full_unstemmed | The Non–Symmetric s–Step Lanczos Algorithm: Derivation of Efficient Recurrences and Synchronization–Reducing Variants of BiCG and QMR |
| title_short | The Non–Symmetric s–Step Lanczos Algorithm: Derivation of Efficient Recurrences and Synchronization–Reducing Variants of BiCG and QMR |
| title_sort | non symmetric s step lanczos algorithm derivation of efficient recurrences and synchronization reducing variants of bicg and qmr |
| topic | synchronization-reducing s-step lanczos s-step bicg s-step qmr efficient recurrences |
| url | https://doi.org/10.1515/amcs-2015-0055 |
| work_keys_str_mv | AT feuerriegelstefan thenonsymmetricssteplanczosalgorithmderivationofefficientrecurrencesandsynchronizationreducingvariantsofbicgandqmr AT buckerhmartin thenonsymmetricssteplanczosalgorithmderivationofefficientrecurrencesandsynchronizationreducingvariantsofbicgandqmr AT feuerriegelstefan nonsymmetricssteplanczosalgorithmderivationofefficientrecurrencesandsynchronizationreducingvariantsofbicgandqmr AT buckerhmartin nonsymmetricssteplanczosalgorithmderivationofefficientrecurrencesandsynchronizationreducingvariantsofbicgandqmr |