Practical Variants of Krylov Subspace Methods in Finite Precision
Thesis title in Czech: | Praktické varianty metod Krylovových podprostorů v konečné přesnosti |
---|---|
Thesis title in English: | Practical Variants of Krylov Subspace Methods in Finite Precision |
Key words: | iterační metody pro řešení soustav lineárních algebraických rovnic|výkonné počítačové architektury|zpětná stabilita numerických metos |
English key words: | iterative methods for solving systems of linear algebraic equations|High-Performance computing|backward stability of numerical methods|numerical linear algebra|finite precision |
Academic year of topic announcement: | 2022/2023 |
Thesis type: | dissertation |
Thesis language: | angličtina |
Department: | Department of Numerical Mathematics (32-KNM) |
Supervisor: | Erin Claire Carson, Ph.D. |
Author: | hidden - assigned and confirmed by the Study Dept. |
Date of registration: | 12.02.2024 |
Date of assignment: | 12.02.2024 |
Confirmed by Study dept. on: | 01.03.2024 |
Guidelines |
Whereas backward stability proofs exist for classical implementations of the Generalized Minimum Residual Method (GMRES) with various orthogonalization schemes, analogous results have not been shown for popular high-performance variants, commonly used for large-scale problems on large-scale machines. For Lanczos-based methods like the conjugate gradient method, "backward-like" stability results have been shown by Anne Greenbaum, but again, no analogous result exists for high-performance variants. Further, there is no existing finite precision analysis of many techniques used in conjunction with Krylov subspace methods in practice, including deflation, augmentation, and certain types of preconditioning.
This project involves investigating the conditions under which variants of GMRES, conjugate gradient, and other Krylov subspace methods used in practice, can be said to be backward stable (or "backward-like" stable, in the case of CG). |
References |
M. Hoemmen. Communication-avoiding Krylov subspace methods. PhD thesis, UC Berkeley,
2010. E. Carson and J. Demmel. A residual replacement strategy for improving the maximum attainable accuracy of s-step Krylov subspace methods. SIAM J. Matrix Anal. Appl., 35(1):22-43, 2014. E. Carson and J. Demmel. Accuracy of the s-step Lanczos method for the symmetric eigenproblem in Finite precision. SIAM J. Matrix Anal. Appl., 36(2):793-819, 2015. J. Demmel, L. Grigori, M. Hoemmen, and J. Langou. Communication-optimal parallel and sequential QR and LU factorizations. SIAM J. Sci. Comput., 31(1):A206-A239, 2012. G. Ballard, E. Carson, J. Demmel, M. Hoemmen, N. Knight, and O. Schwartz. Communication lower bounds and optimal algorithms for numerical linear algebra. Acta Numerica, 23:1-155, 2014. P. Ghysels, T. Ashby, K. Meerbergen, and W. Vanroose. Hiding global communication latency in the GMRES algorithm on massively parallel machines. SIAM J. Sci. Comput., 35(1):C48-C71, 2013. A. Greenbaum. Behavior of slightly perturbed Lanczos and conjugate-gradient recurrences. Lin. Alg. Appl., 113:7-63, 1989. J. Liesen, Z. Strakoš: Principles and Analysis of Krylov Subspace Method, 2013. |
Preliminary scope of work |
Práce se zaměřuje na problém zpětné stability v Krylovovských iteračních metodách na moderních výkonných výpočetních architekturách. |
Preliminary scope of work in English |
The goal of the work is to study backward stability of practical variants of Krylov iterative methods on High-Performance computers. |