Abstract
Block Krylov subspace methods (KSMs) comprise building blocks in many state-of-the-art solvers for large-scale matrix equations as they arise, for example, from the discretization of partial differential equations. While extended and rational block Krylov subspace methods provide a major reduction in iteration counts over polynomial block KSMs, they also require reliable solvers for the coefficient matrices, and these solvers are often iterative methods themselves. It is not hard to devise scenarios in which the available memory, and consequently the dimension of the Krylov subspace, is limited. In such scenarios for linear systems and eigenvalue problems, restarting is a well-explored technique for mitigating memory constraints. In this work, such restarting techniques are applied to polynomial KSMs for matrix equations with a compression step to control the growing rank of the residual. An error analysis is also performed, leading to heuristics for dynamically adjusting the basis size in each restart cycle. A panel of numerical experiments demonstrates the effectiveness of the new method with respect to extended block KSMs.
| Original language | English |
|---|---|
| Article number | e2339 |
| Number of pages | 17 |
| Journal | Numerical Linear Algebra with Applications |
| Volume | 28 |
| Issue number | 1 |
| DOIs | |
| Publication status | Published - Jan 2021 |
Bibliographical note
Funding Information:information SNSF: Fast algorithms from low-rank updates, grant number: 200020 178806; Charles University, PRIMUS/19/SCI/11Stefano Massei and Davide Palitta are members of the Italian INdAM Research group GNCS. Kathryn Lund is supported in part by the Charles University PRIMUS grant, project no. PRIMUS/19/SCI/11, and in part by the SNSF research project Fast algorithms from low-rank updates, grant number: 200020_178806. Open access funding enabled and organized by Projekt DEAL.
Funding Information:
SNSF: Fast algorithms from low‐rank updates, grant number: 200020 178806; Charles University, PRIMUS/19/SCI/11 Funding information
Funding Information:
Stefano Massei and Davide Palitta are members of the Italian INdAM Research group GNCS. Kathryn Lund is supported in part by the Charles University PRIMUS grant, project no. PRIMUS/19/SCI/11, and in part by the SNSF research project , grant number: 200020_178806. Open access funding enabled and organized by Projekt DEAL. Fast algorithms from low‐rank updates
Publisher Copyright:
© 2020 The Authors. Numerical Linear Algebra with Applications published by John Wiley & Sons Ltd.
Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.
Funding
information SNSF: Fast algorithms from low-rank updates, grant number: 200020 178806; Charles University, PRIMUS/19/SCI/11Stefano Massei and Davide Palitta are members of the Italian INdAM Research group GNCS. Kathryn Lund is supported in part by the Charles University PRIMUS grant, project no. PRIMUS/19/SCI/11, and in part by the SNSF research project Fast algorithms from low-rank updates, grant number: 200020_178806. Open access funding enabled and organized by Projekt DEAL. SNSF: Fast algorithms from low‐rank updates, grant number: 200020 178806; Charles University, PRIMUS/19/SCI/11 Funding information Stefano Massei and Davide Palitta are members of the Italian INdAM Research group GNCS. Kathryn Lund is supported in part by the Charles University PRIMUS grant, project no. PRIMUS/19/SCI/11, and in part by the SNSF research project , grant number: 200020_178806. Open access funding enabled and organized by Projekt DEAL. Fast algorithms from low‐rank updates
Keywords
- block Krylov subspace methods
- linear matrix equations
- low-rank compression
- restarts