Sketched and Truncated Polynomial Krylov Methods: Evaluation of Matrix Functions

被引:1
作者
Palitta, Davide [1 ]
Schweitzer, Marcel [2 ]
Simoncini, Valeria [1 ,3 ]
机构
[1] Bergishce Univ Wuppertal, Sch Math & Nat Sci, Wuppertal, Germany
[2] Alma Mater Studiorum Univ Bologna, Dipartimento Matemat AM2, Bologna, Italy
[3] IMATI CNR, Pavia, Italy
关键词
Krylov subspace method; matrix function; projection method; randomization; sketching; subspace embedding; APPROXIMATION; ALGORITHMS;
D O I
10.1002/nla.2596
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
Among randomized numerical linear algebra strategies, so-called sketching procedures are emerging as effective reduction means to accelerate the computation of Krylov subspace methods for, for example, the solution of linear systems, eigenvalue computations, and the approximation of matrix functions. While there is plenty of experimental evidence showing that sketched Krylov solvers may dramatically improve performance over standard Krylov methods, especially when combined with a truncated orthogonalization step, many features of these schemes are still unexplored. We derive a new sketched Arnoldi-type relation that allows us to obtain several different new theoretical results. These lead to an improvement of our understanding of sketched Krylov methods, in particular by explaining why the frequently occurring sketched Ritz values far outside the spectral region of A$$ A $$ do not negatively influence the convergence of sketched Krylov methods for f(A)b$$ f(A)b $$. Our findings also help to identify, among several possible equivalent formulations, the most suitable sketched approximations according to their numerical stability properties. These results are also employed to analyze the error of sketched Krylov methods in the approximation of the action of matrix functions, significantly contributing to the theory available in the current literature.
引用
收藏
页数:16
相关论文
共 39 条
[1]   COMPUTING THE ACTION OF THE MATRIX EXPONENTIAL, WITH AN APPLICATION TO EXPONENTIAL INTEGRATORS [J].
Al-Mohy, Awad H. ;
Higham, Nicholas J. .
SIAM JOURNAL ON SCIENTIFIC COMPUTING, 2011, 33 (02) :488-511
[2]   A NEW SCALING AND SQUARING ALGORITHM FOR THE MATRIX EXPONENTIAL [J].
Al-Mohy, Awad H. ;
Higham, Nicholas J. .
SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS, 2009, 31 (03) :970-989
[4]   RANDOMIZED GRAM-SCHMIDT PROCESS WITH APPLICATION TO GMRES [J].
Balabanov, Oleg ;
Grigori, Laura .
SIAM JOURNAL ON SCIENTIFIC COMPUTING, 2022, 44 (03) :A1450-A1474
[5]   Randomized linear algebra for model reduction. Part I: Galerkin methods and error estimation [J].
Balabanov, Oleg ;
Nouy, Anthony .
ADVANCES IN COMPUTATIONAL MATHEMATICS, 2019, 45 (5-6) :2969-3019
[6]   LOW-RANK UPDATES OF MATRIX FUNCTIONS [J].
Beckermann, Bernhard ;
Kressner, Daniel ;
Schweitzer, Marcel .
SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS, 2018, 39 (01) :539-565
[7]   Block Gram-Schmidt algorithms and their stability properties [J].
Carson, Erin ;
Lund, Kathryn ;
Rozloznik, Miroslav ;
Thomas, Stephen .
LINEAR ALGEBRA AND ITS APPLICATIONS, 2022, 638 :150-195
[8]   SPEEDING UP KRYLOV SUBSPACE METHODS FOR COMPUTING f(A)b VIA RANDOMIZATION [J].
Cortinovis, Alice ;
Kressner, Daniel ;
Nakatsukasa, Yuji .
SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS, 2024, 45 (01) :619-633
[9]   THE NUMERICAL RANGE IS A (1+√2)-SPECTRAL SET [J].
Crouzeix, M. ;
Palencia, C. .
SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS, 2017, 38 (02) :649-655