APPROXIMATION OF THE LINEAR COMBINATION OF <i>φ</i>-FUNCTIONS USING THE BLOCK SHIFT-AND-INVERT KRYLOV SUBSPACE METHOD

Dongping Li; Yuhao Cong

doi:10.11948/2017085

2017 Volume 7 Issue 4

Article Contents

Article navigation > Journal of Applied Analysis & Computation > 2017 > 7(4): 1402-1416

Next Article Previous Article

Dongping Li, Yuhao Cong. APPROXIMATION OF THE LINEAR COMBINATION OF φ-FUNCTIONS USING THE BLOCK SHIFT-AND-INVERT KRYLOV SUBSPACE METHOD[J]. Journal of Applied Analysis & Computation, 2017, 7(4): 1402-1416. doi: 10.11948/2017085

Citation:

Dongping Li, Yuhao Cong. APPROXIMATION OF THE LINEAR COMBINATION OF φ-FUNCTIONS USING THE BLOCK SHIFT-AND-INVERT KRYLOV SUBSPACE METHOD[J]. Journal of Applied Analysis & Computation, 2017, 7(4): 1402-1416. doi: 10.11948/2017085

APPROXIMATION OF THE LINEAR COMBINATION OF φ-FUNCTIONS USING THE BLOCK SHIFT-AND-INVERT KRYLOV SUBSPACE METHOD

Dongping Li^3,4,
Yuhao Cong^1,2

1 Department of Mathematics, Shanghai University, Shanghai, 200444, China;
2 Department of Mathematics, Shanghai Customs College, Shanghai, 201204, China;
3 Department of Mathematics, Changchun Normal University, Changchun, 200234, China;
4 Mathematics and Science College, Shanghai Normal University, Shanghai, 130032, China

Fund Project:

Abstract

Abstract

In this paper, we develop an algorithm in which the block shiftand-invert Krylov subspace method can be employed for approximating the linear combination of the matrix exponential and related exponential-type functions. Such evaluation plays a major role in a class of numerical methods known as exponential integrators. We derive a low-dimensional matrix exponential to approximate the objective function based on the block shiftand-invert Krylov subspace methods. We obtain the error expansion of the approximation, and show that the variants of its first term can be used as reliable a posteriori error estimates and correctors. Numerical experiments illustrate that the error estimates are efficient and the proposed algorithm is worthy of further study.
- Matrix exponential /
- exponential integrators /
- block shift-and-invert Krylov subspace /
- a posteriori error estimates
MSC: 65L05;65F10;65F30

FullText(HTML)

References

[1]	A. Al-Mohy and N. J. Higham, A new scaling and modified squaring algorithm for matrix functions, SIAM J. Matrix Anal. Appl., 2009, 31(3), 970-989. Google Scholar
[2]	A. Al-Mohy and N. J. Higham, Computing the action of the matrix exponential, with an application to exponential integrators, SIAM J. Sci. Comput., 2011, 33(2), 488-511. Google Scholar
[3]	A. C. Antoulas and D. C. Sorensen, Approximation of large-scale dynamical systems:an overview, Int. J. Appl. Math. Comput. Sci, 2001, 11(5), 1093-1121. Google Scholar
[4]	A. C. Antoulas, Approximation of large-scale dynamical Systems, SIAM, Philadelphia, 2009. Google Scholar
[5]	M. Botchev, V. Grimm, and M. Hochbruck, Residual, restarting, and Richardson iteration for the matrix exponential, SIAM J. Sci. Comput., 2013, 35(3), 1376-1397. Google Scholar
[6]	M. A. Botchev, A block Krylov subspace time-exact solution method for linear ordinary differential equation systems, Numer. Linear Algebra Appl., 2013, 20(4), 557-574. Google Scholar
[7]	E. Celledoni and I. Moret, A Krylov projection method for systems of ODEs, Appl. Numer. Math., 1997, 24(2), 365-378. Google Scholar
[8]	Y. H. Cong and D. P. Li, Block Krylov subspace methods for approximating the linear combination of φ-functions arising in exponential integrators, Comput. Math. Appl., 2016, 72(4), 846-855. Google Scholar
[9]	V. Druskin, C. Lieberman and M. Zaslavsky, On adaptive choice of shifts in rational Krylov subspace reduction of evolutionary problems, SIAM J. Sci. Comput., 2010, 32(5), 2485-2496. Google Scholar
[10]	M. Eiermann and O. G. Ernst, A restarted Krylov subspace method for the evaluation of matrix function, SIAM J. Numer. Anal., 2006, 44(6), 2481-2504. Google Scholar
[11]	J. Eshof and M, Hochbruck, Preconditioning Lanczos approximations to the matrix exponential, SIAM J. Sci. Comput., 2006, 27(4), 1438-1457. Google Scholar
[12]	A. Frommer, S. Güttel and M. Schweitzer, Efficient and stable Arnoldi restarts for matrix functions based on quadrture, SIAM J. Matrix Anal. Appl., 2014, 35(2), 661-683. Google Scholar
[13]	T. Göckler and V. Grimm, Convergence Analysis of an Extended Krylov Subspace Method for the Approximation of Operator Functions in Exponential Integrators, SIAM J. Numer. Anal., 2013, 51(4), 2189-2213. Google Scholar
[14]	T. Göckler, Rational Krylov subspace methods for φ-functions in exponential integrators, PhD thesis, Karlsruhe Institute of Technology (KIT), 2014. Google Scholar
[15]	V. Grimm, Resolvent Krylov subspace approximation to operator functions, BIT Numer. Math., 2012, 52(3), 639-659. Google Scholar
[16]	S. Güttel, Rational Krylov method for operator functions, Ph.D. thesis, Fakultät füt Mathematik und Informatik der Technischen Universität Bergakademie Freiberg, 2010. Google Scholar
[17]	N. J. Higham, The Scaling and Squaring Method for the Matrix Exponential Revisited, SIAM J. Matrix Anal. Appl., 2005, 26(4), 1179-1193. Google Scholar
[18]	M. Hochbruck and C. Lubich, On Krylov subspace approximations to the matrix exponential operator, SIAM J. Numer. Anal., 1997, 34(5), 1912-1925. Google Scholar
[19]	M. Hochbruck,and A. Ostermann, Exponential Integrators, Acta Numer., 2010, 19(19), 209-286. Google Scholar
[20]	N. J. Higham, Functions of matrices:theory and computation, SIAM, Philadelphia, 2008. Google Scholar
[21]	Z. Jia and H. Lv, A posteriori error estimates of Krylov subspace approximations to matrix functions, Numer. Algor., 2015, 69(1), 1-28. Google Scholar
[22]	H. M. Kim and R. R. Craig, Jr, Structural dynamics analysis using an unsymmetric block Lanczos algorithm, Int. J. for Numer. Meth. Eng., 1988, 26(10), 2305-2318. Google Scholar
[23]	L. Knizhnerman and V. Simoncini, A new investigation of the extended Krylov subspace method for matrix function evaluations, Numer. Linear Algebra Appl., 2010, 17(4), 615-638. Google Scholar
[24]	B. V. Minchev and W. M. Wright, A review of exponential integrators for first order semi-linear problems, Tech. report 2/05, Department of Mathematics, NTNU, 2005. Google Scholar
[25]	C. Moler, C. V. Loan, Nineteen dubious ways to compute the exponential of a matrix, twenty-five years later, SIAM Review, 2003, 20(4), 3-49. Google Scholar
[26]	I. Moret and P. Novati, An interpolatory approximations of the matrix exponential based on Faber polynomials, J. Comput. Appl. Math., 2001, 131(1-2), 361-380. Google Scholar
[27]	I. Moret and P. Novati, RD-rational approximations of the matrix exponential, BIT, 2004, 44(3), 595-615. Google Scholar
[28]	I. Moret and M. Popolizio, The restarted shift-and-invert Krylov method for matrix function, Numer. Linear Algebra Appl., 2014, 21(1), 68-80. Google Scholar
[29]	J. Niesen and W. M. Wright, Algorithm 919:A Krylov subspace algorithm for evaluating the phi-functions appearing in exponential integrators, ACM Trans. Math. Software, 2012, 38(3), 1-19. Google Scholar
[30]	B. Nour-Omid, Application of the Lanczos algorithm, Comput. Phy. Comm, 1989, 53(1-3), 157-168. Google Scholar
[31]	R. B. Sidje, Expokit:A software package for computing matrix exponentials, ACM Trans. Math. Software, 1998, 24(1), 130-156. Google Scholar
[32]	B. Skaflestad and W. M. Wright, The scaling and modified squaring method for matrix functions related to the exponential, Appl. Numer. Math., 2009, 59(3), 783-799. Google Scholar
[33]	T. Schmelzer, The fast evaluation of matrix functions for exponential integrators, PhD thesis, University of Oxford, 2007. Google Scholar
[34]	Y. Saad, Analysis of some Krylov subspace approximations to the matrix exponential operator, SIAM J. Numer. Anal., 1992, 29(1), 209-228. Google Scholar
[35]	Y. Saad, Iterative Methods for sparse linear systems, 2nd edition, SIAM, Philadelphia, 2003. Google Scholar
[36]	H. Tal-ezer, On restart and error estimation for Krylov approximation of !=f(A)v, SIAM J. Sci. Comput., 2007, 29(6), 2426-2441. Google Scholar
[37]	G. Wu, H. Pang and J. Sun, Preconditioning the Restarted and Shifted Block FOM Algorithm for Matrix Exponential Computation, Mathematics, 2014, 1-24. Google Scholar
[38]	Q. Ye, Error bounds for the Lanczos methods for approximating matrix exponentials, SIAM. J. Numer Anal., 2013, 51(1), 68-87. Google Scholar