<abstract xmlns="http://www.w3.org/1999/xhtml"><p>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 <italic>s</italic>-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 <italic>s</italic>-step Lanczos algorithm, introduce <italic>s</italic>-step BiCG and QMR variants, and compare the parallel performance of these new <italic>s</italic>-step versions with previous algorithms.</p></abstract>

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.

The Non–Symmetric <italic>s</italic>–Step Lanczos Algorithm: Derivation of Efficient Recurrences and Synchronization–Reducing Variants of BiCG and QMR

Chair for Information Systems Research, University of Freiburg, Platz der Alten Synagoge, 79098 Freiburg, Germany

Chair for Advanced Computing, Friedrich Schiller University Jena, Ernst-Abbe-Platz 2, 07743 Jena, Germany

International Journal of Applied Mathematics and Computer Science

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

The Non–Symmetric –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....

The Non–Symmetric s–Step Lanczos Algorithm: Derivation of Efficient Recurrences and Synchronization–Reducing Variants of BiCG and QMR

Publié en ligne: 30 déc. 2015

Pages: 769 - 785

Reçu: 15 avr. 2014

DOI: https://doi.org/10.1515/amcs-2015-0055

Mots clés
synchronization-reducing, -step Lanczos, -step BiCG, -step QMR, efficient recurrences

© 2015 Stefan Feuerriegel et al., published by De Gruyter Open

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

The Non–Symmetric s–Step Lanczos Algorithm: Derivation of Efficient Recurrences and Synchronization–Reducing Variants of BiCG and QMR

Publié en ligne: 30 déc. 2015

Pages: 769 - 785

Reçu: 15 avr. 2014

DOI: https://doi.org/10.1515/amcs-2015-0055

Mots cléssynchronization-reducing, -step Lanczos, -step BiCG, -step QMR, efficient recurrences

© 2015 Stefan Feuerriegel et al., published by De Gruyter Open

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

Mots clés
synchronization-reducing, -step Lanczos, -step BiCG, -step QMR, efficient recurrences