This is a companion PR to #321 . This will be rebased on top of that PR once merged (couldn't figure out how to stack the PRs in this case)
Background
This PR introduces lalqmr, along with an iterable implementation, which solves linear systems via QMR with a Look-ahead Lanczos process.
The motivation for using the look-ahead process is for use in non-hermitian linear systems, particularly ones which aren't well-conditioned, where the standard Lanczos process encounters either exact or numerical breakdown. The look-ahead technique circumvents the breakdown by constructing blocks in the sequence, such that the generated sequences avoid breakdown.
Implementation Details
As in #321 , we limit the memory of the allocated matrices as much as possible. There is still room for further optimizations, but their benefit is limited compared to the matrix-vector products.
Tests
This implementation is tested against some contrived matrices which guarantee block creation during QMR, as well as the standard test-suite. Additional test suggestions welcome.
Future directions
Further micro-optimization, validation on GPU
A specialized implementation for complex-symmetric (or symmetric) matrices, which reduces by a factor of ~2x the memory usage and matrix-vector products.
The residual norm is an estimate, as mentioned in the documentation. Freund recommends switching over to an explicit calculation of the residual norm once the estimate is met, which will ensure a tighter bound on the achieved tolerance.
References
Freund, R. W., & Nachtigal, N. M. (1994). An Implementation of the QMR Method Based on Coupled Two-Term Recurrences. SIAM Journal on Scientific Computing, 15(2), 313–337. https://doi.org/10.1137/0915022
Freund, R. W., Gutknecht, M. H., & Nachtigal, N. M. (1993). An Implementation of the Look-Ahead Lanczos Algorithm for Non-Hermitian Matrices. SIAM Journal on Scientific Computing, 14(1), 137–158. https://doi.org/10.1137/0914009
This is a companion PR to #321 . This will be rebased on top of that PR once merged (couldn't figure out how to stack the PRs in this case)
Background
This PR introduces
lalqmr, along with an iterable implementation, which solves linear systems via QMR with a Look-ahead Lanczos process.The motivation for using the look-ahead process is for use in non-hermitian linear systems, particularly ones which aren't well-conditioned, where the standard Lanczos process encounters either exact or numerical breakdown. The look-ahead technique circumvents the breakdown by constructing blocks in the sequence, such that the generated sequences avoid breakdown.
Implementation Details
As in #321 , we limit the memory of the allocated matrices as much as possible. There is still room for further optimizations, but their benefit is limited compared to the matrix-vector products.
Tests
This implementation is tested against some contrived matrices which guarantee block creation during QMR, as well as the standard test-suite. Additional test suggestions welcome.
Future directions
References