Top

Numerical Algorithms

Published in:

09-09-2019 | Original Paper

Recursive blocked algorithms for linear systems with Kronecker product structure

Authors: Minhong Chen, Daniel Kressner

Published in: Numerical Algorithms | Issue 3/2020

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Recursive blocked algorithms have proven to be highly efficient at the numerical solution of the Sylvester matrix equation and its generalizations. In this work, we show that these algorithms extend in a seamless fashion to higher-dimensional variants of generalized Sylvester matrix equations, as they arise from the discretization of PDEs with separable coefficients or the approximation of certain models in macroeconomics. By combining recursions with a mechanism for merging dimensions, an efficient algorithm is derived that outperforms existing approaches based on Sylvester solvers.

previous article Computers in mathematical research: the study of three-point root-finding methods

next article Generalized viscosity implicit scheme with Meir-Keeler contraction for asymptotically nonexpansive mapping in Banach spaces

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Bader, B.W., Kolda, T.G., et al.: Matlab tensor toolbox version 2.6. Available from http://www.sandia.gov/~tgkolda/TensorToolbox/ (2015)

Bartels, R.H., Stewart, G.W.: Algorithm 432: The solution of the matrix equation AX + XB = C. Commun. ACM 15(9), 820–826 (1972)CrossRefMATH

Binning, A.: Solving second and third-order approximations to DSGE models: a recursive Sylvester equation solution. Norges Bank Working Paper 18 (2013)

Chu, E.K.-W.: The solution of the matrix equations AXB − CXD = E and (YA − DZ,YC − BZ) = (E,F). Linear Algebra Appl. 93, 93–105 (1987)CrossRefMathSciNetMATH

Dayar, T.: Kronecker Modeling and Analysis of Multidimensional Markovian Systems. Springer, Cham (2018)CrossRefMATH

Deadman, E., Higham, N.J., Ralha, R.: Blocked Schur Algorithms for Computing the Matrix Square Root. Lecture Notes in Comput Sci, vol. 7782, pp 171–182. Springer, Berlin (2013)

Elmroth, E., Gustavson, F., Jonsson, I., Kågström, B.: Recursive blocked algorithms and hybrid data structures for dense matrix library software. SIAM Rev. 46(1), 3–45 (2004)CrossRefMathSciNetMATH

Golub, G.H., Van Loan, C.F.: Matrix Computations, 4th edn. Johns Hopkins University Press, Baltimore (2013)MATH

Granat, R., Kågström, B.: Algorithm 904: The SCASY library – parallel solvers for Sylvester-type matrix equations with applications in condition estimation, part II. ACM Trans. Math. Softw. 37(3), 1–4 (2010)MATH

10.

Granat, R., Kågström, B: Parallel solvers for Sylvester-type matrix equations with applications in condition estimation, part I Theory and algorithms. ACM Trans. Math. Softw. 37(3), 1–32 (2010)MATH

11.

Grasedyck, L., Kressner, D., Tobler, C.: A literature survey of low-rank tensor approximation techniques. GAMM-Mitt. 36(1), 53–78 (2013)CrossRefMathSciNetMATH

12.

Hackbusch, W.: Tensor Spaces and Numerical Tensor Calculus. Springer, Heidelberg (2012)CrossRefMATH

13.

Hammarling, S.: Numerical solution of the stable, nonnegative definite Lyapunov equation. IMA J. Numer. Anal. 2(3), 303–323 (1982)CrossRefMathSciNetMATH

14.

Jonsson, I., Kågström, B.: Recursive blocked algorithm for solving triangular systems. I. One-sided and coupled Sylvester-type matrix equations. ACM Trans. Math Software 28(4), 392–415 (2002)CrossRefMathSciNetMATH

15.

Jonsson, I., Kågström, B.: Recursive blocked algorithm for solving triangular systems. II. Two-sided and generalized Sylvester and Lyapunov matrix equations. ACM Trans. Math Softw. 28(4), 416–435 (2002)CrossRefMathSciNetMATH

16.

Kamenik, O.: Solving SDGE models: a new algorithm for the Sylvester equation. Comput. Econ. 25(1), 167–187 (2005)CrossRefMATH

17.

Köhler, M., Saak, J.: On BLAS level-3 implementations of common solvers for (quasi-) triangular generalized Lyapunov equations. ACM Trans. Math. Software 43(1), Art. 3, 23 (2016)CrossRefMathSciNetMATH

18.

Kolda, T.G., Bader, B.W.: Tensor decompositions and applications. SIAM Rev. 51(3), 455–500 (2009)CrossRefMathSciNetMATH

19.

Kressner, D.: Block variants of Hammarling’s method for solving Lyapunov equations. ACM Trans. Math. Software 34(1), 1–15 (2008)CrossRefMathSciNetMATH

20.

Kressner, D., Tobler, C.: Krylov subspace methods for linear systems with tensor product structure. SIAM J Matrix Anal. Appl. 31(4), 1688–1714 (2010)CrossRefMathSciNetMATH

21.

Li, B.-W., Tian, S., Sun, Y.-S., Hu, Z.-M.: Schur-decomposition for 3D matrix equations and its application in solving radiative discrete ordinates equations discretized by Chebyshev collocation spectral method. J. Comput. Phys. 229(4), 1198–1212 (2010)CrossRefMathSciNetMATH

22.

Moravitz Martin, C.D., Van Loan, C.F.: Shifted Kronecker product systems. SIAM J. Matrix Anal. Appl. 29(1), 184–198 (2006)CrossRefMathSciNetMATH

23.

Moravitz Martin, C.D., Van Loan, C.F.: Solving real linear systems with the complex Schur decomposition. SIAM J. Matrix Anal. Appl. 29(1), 177–183 (2006/07)CrossRefMathSciNetMATH

24.

Oseledets, I.V.: Tensor-train decomposition. SIAM J. Sci. Comput. 33(5), 2295–2317 (2011)CrossRefMathSciNetMATH

25.

Peise, E., Bientinesi, P.: Algorithm 979: recursive algorithms for dense linear algebra—the ReLAPACK collection. ACM Trans. Math. Software 44(2), Art. 16, 19 (2017)CrossRefMathSciNetMATH

26.

Quintana-Ortí, E.S., van de Geijn, R. A.: Formal derivation of algorithms: the triangular Sylvester equation. ACM Trans. Math. Software 29(2), 218–243 (2003)CrossRefMathSciNetMATH

27.

Sangalli, G., Tani, M.: Isogeometric preconditioners based on fast solvers for the Sylvester equation. SIAM J. Sci. Comput. 38(6), A3644–A3671 (2016)CrossRefMathSciNetMATH

28.

Simoncini, V.: Computational methods for linear matrix equations. SIAM Rev. 58(3), 377–441 (2016)CrossRefMathSciNetMATH

29.

Stewart, G.W.: Stochastic automata, tensors operation, and matrix equations. UMIACS TR-96-11, CMSC TR-3598 (1996)

30.

Stewart, W.J.: Introduction to the Numerical Solution of Markov Chains. Princeton University Press, Princeton (1994)MATH

31.

Touzene, A.: Approximated tensor sum preconditioner for stochastic automata networks. In: Proceedings 20th IEEE International Parallel Distributed Processing Symposium (2006)

32.

Van Loan, C.F.: The ubiquitous Kronecker product. J. Comput. Appl. Math. 123(1–2), 85–100 (2000)CrossRefMathSciNetMATH

Title: Recursive blocked algorithms for linear systems with Kronecker product structure
Authors: Minhong Chen
Daniel Kressner
Publication date: 09-09-2019
Publisher: Springer US
Published in: Numerical Algorithms / Issue 3/2020
Print ISSN: 1017-1398
Electronic ISSN: 1572-9265
DOI: https://doi.org/10.1007/s11075-019-00797-5

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Springer Professional "Wirtschaft+Technik"

Other articles of this Issue 3/2020

An adaptive local discontinuous Galerkin method for nonlinear two-point boundary-value problems

A convergence study for reduced rank extrapolation on nonlinear systems

Reconstruction algorithms of an inverse source problem for the Helmholtz equation

Computers in mathematical research: the study of three-point root-finding methods

A second-order artificial compression method for the evolutionary Stokes-Darcy system

Optimizations of a fast multipole symmetric Galerkin boundary element method code

Premium Partner