Document - Rational Krylov and ADI iteration for infinite size quasi-Toeplitz matrix equations

2020

Journal article Open Access

Rational Krylov and ADI iteration for infinite size quasi-Toeplitz matrix equations

Robol L.

Rational Krylov subspaces Geometry and Topology FOS: Mathematics 15B05 Stein equations Mathematics - Numerical Analysis 15A24 65F10 Algebra and Number Theory Sylvester equations Numerical Analysis Matrix equations Infinite matrices Toeplitz matrices Numerical Analysis (math.NA) Discrete Mathematics and Combinatorics

We consider a class of linear matrix equations involving semi-infinite matrices which have a quasi-Toeplitz structure. These equations arise in different settings, mostly connected with PDEs or the study of Markov chains such as random walks on bidimensional lattices. We present the theory justifying the existence of the solution in an appropriate Banach algebra which is computationally treatable, and we propose several methods for computing them. We show how to adapt the ADI iteration to this particular infinite dimensional setting, and how to construct rational Krylov methods. Convergence theory is discussed, and numerical experiments validate the proposed approaches.

Source: Linear algebra and its applications 604 (2020): 210–235. doi:10.1016/j.laa.2020.06.013

Publisher: North Holland [etc.], [New York], Stati Uniti d'America

Citations

[1] Bartels, R. H., Stewart, G. W., Sep. 1972. Solution of the Matrix Equation AX + XB = C [F4]. Commun. ACM 15 (9), 820{826.
[2] Beckermann, B., 2011. An error analysis for rational Galerkin projection applied to the Sylvester equation. SIAM Journal on Numerical Analysis 49 (6), 2430{2450.
[3] Benner, P., Kurschner, P., 2014. Computing real low-rank solutions of sylvester equations by the factored adi method. Computers & Mathematics with Applications 67 (9), 1656{1672.
[4] Benner, P., Mehrmann, V., Sima, V., Van Hu el, S., Varga, A., 1999. Slicot|a subroutine library in systems and control theory. In: Applied and computational control, signals, and circuits. Springer, pp. 499{539.
[5] Berljafa, M., Guttel, S., 2015. Generalized rational Krylov decompositions with an application to rational approximation. SIAM J. Matrix Anal. Appl. 36 (2), 894{916.
[6] Bhatia, R., Rosenthal, P., 1997. How and why to solve the operator equation AX XB = Y . Bulletin of the London Mathematical Society 29 (1), 1{21.
[7] Bini, D. A., Latouche, G., Meini, B., 2005. Numerical methods for structured Markov chains. Numerical Mathematics and Scienti c Computation. Oxford University Press, New York.
[8] Bini, D. A., Massei, S., Meini, B., Robol, L., 2018. On quadratic matrix equations with in nite size coe cients encountered in QBD stochastic processes. Numer. Linear Algebra Appl. 25 (6), e2128, 12.
[9] Bini, D. A., Massei, S., Robol, L., 2017. E cient cyclic reduction for quasibirth-death problems with rank structured blocks. Appl. Numer. Math. 116, 37{46.
[10] Bini, D. A., Massei, S., Robol, L., 2019. Quasi-Toeplitz matrix arithmetic: a MATLAB toolbox. Numerical Algorithms 81 (2), 741{769.
[11] Bini, D. A., Meini, B., Meng, J., 2019. Solving quadratic matrix equations arising in random walks in the quarter plane. In preparation.
[12] Bottcher, A., Grudsky, S. M., 2005. Spectral properties of banded Toeplitz matrices. Vol. 96. SIAM.
[13] Gaaf, S. W., Jarlebring, E., 2017. The in nite bi-lanczos method for nonlinear eigenvalue problems. SIAM Journal on Scienti c Computing 39 (5), S898{S919.
[14] Gilles, M. A., Townsend, A., 2018. Continuous analogues of krylov methods for di erential operators. arXiv preprint arXiv:1803.11049.
[15] Golub, G., Nash, S., Van Loan, C., 1979. A Hessenberg-Schur method for the problem AX + XB = C. IEEE Transactions on Automatic Control 24 (6), 909{913.
[16] Henrici, P., 1974. Applied and computational complex analysis. WileyInterscience [John Wiley & Sons], New York-London-Sydney, volume 1: Power series|integration|conformal mapping|location of zeros, Pure and Applied Mathematics.
[17] Kressner, D., Massei, S., Robol, L., 2019. Low-rank updates and a divideand-conquer method for linear matrix equations. SIAM Journal on Scienti c Computing 41 (2), A848{A876.
[18] Lancaster, P., 1970. Explicit solutions of linear matrix equations. SIAM review 12 (4), 544{566.
[19] Massei, S., Mazza, M., Robol, L., 2019. Fast solvers for 2D fractional di usion equations using rank structured matrices. to appear in SIAM Journal on Scienti c Computing.
[20] Massei, S., Palitta, D., Robol, L., 2018. Solving rank-structured Sylvester and Lyapunov equations. SIAM Journal on Matrix Analysis and Applications 39 (4), 1564{1590.
[21] Massei, S., Robol, L., 2019. Rational Krylov for Stieltjes matrix functions: convergence and pole selection. In preparation.
[22] Moret, I., Novati, P., 2019. Krylov subspace methods for functions of fractional di erential operators. Mathematics of Computation 88 (315), 293{ 312.
[23] Motyer, A. J., Taylor, P. G., 2006. Decay rates for quasi-birth-and-death processes with countably many phases and tridiagonal block generators. Advances in applied probability 38 (2), 522{544.
[24] Novati, P., 2017. Some properties of the Arnoldi-based methods for linear ill-posed problems. SIAM Journal on Numerical Analysis 55 (3), 1437{1455.
[25] Palitta, D., Simoncini, V., 2016. Matrix-equation-based strategies for convection{di usion equations. BIT Numerical Mathematics 56 (2), 751{ 776.
[26] Rosenblum, M., et al., 1956. On the operator equation BX Duke Mathematical Journal 23 (2), 263{269.

Metrics

Back to previous page

Cite as

BibTeX entry

@article{oai:it.cnr:prodotti:424808,
	title = {Rational Krylov and ADI iteration for infinite size quasi-Toeplitz matrix equations},
	author = {Robol L.},
	publisher = {North Holland [etc.], [New York], Stati Uniti d'America},
	doi = {10.1016/j.laa.2020.06.013 and 10.48550/arxiv.1907.02753},
	journal = {Linear algebra and its applications},
	volume = {604},
	pages = {210–235},
	year = {2020}
}