Journal article  Open Access

Low-rank updates and a divide-and-conquer method for linear matrix equations

Kressner D., Massei S., Robol L.

algorithms  FOS: Mathematics  lyapunov equation  sylvester equation  Low-rank update  low-rank update  krylov subspace methods  Mathematics - Numerical Analysis  operators  lyapunov equations  Divide-and-conquer  approximation  Computational Mathematics  superfast  divide-and-conquer  numerical-methods  eigenvalue decay  sylvester  Lyapunov equation  Sylvester equation  Hierarchical matrices  hierarchical matrices  singular-values  Numerical Analysis (math.NA)  Applied Mathematics 

Linear matrix equations, such as the Sylvester and Lyapunov equations, play an important role in various applications, including the stability analysis and dimensionality reduction of linear dynamical control systems and the solution of partial differential equations. In this work, we present and analyze a new algorithm, based on tensorized Krylov subspaces, for quickly updating the solution of such a matrix equation when its coefficients undergo low-rank changes. We demonstrate how our algorithm can be utilized to accelerate the Newton method for solving continuous-time algebraic Riccati equations. Our algorithm also forms the basis of a new divide-and-conquer approach for linear matrix equations with coefficients that feature hierarchical low-rank structure, such as hierarchically off-diagonal low-rank structures, hierarchically semiseparable, and banded matrices. Numerical experiments demonstrate the advantages of divide-and-conquer over existing approaches, in terms of computational time and memory consumption.

Source: SIAM journal on scientific computing (Print) 41 (2019). doi:10.1137/17M1161038

Publisher: Society for Industrial and Applied Mathematics,, Philadelphia, PA , Stati Uniti d'America

[1] J. Abels and P. Benner, CAREX - a collection of benchmark examples for continuous-time algebraic Riccati equations (version 2.0), SLICOT working note 1999-14, 1999. Available online from http://www.slicot.org.
[2] S. Ambikasaran and E. Darve, An O(N log N ) fast direct solver for partial hierarchically semi-separable matrices: with application to radial basis function interpolation, J. Sci. Comput., 57 (2013), pp. 477{501, doi:10.1007/s10915-013-9714-z.
[3] A. C. Antoulas, Approximation of Large-Scale Dynamical Systems, SIAM Publications, Philadelphia, PA, 2005.
[4] A. C. Antoulas, D. C. Sorensen, and Y. Zhou, On the decay rate of Hankel singular values and related issues, Systems Control Lett., 46 (2002), pp. 323{342, doi:10.1016/S0167-6911(02)00147-0.
[5] J. Baker, M. Embree, and J. Sabino, Fast singular value decay for Lyapunov solutions with nonnormal coe cients, SIAM J. Matrix Anal. Appl., 36 (2015), pp. 656{668, https://doi.org/10.1137/140993867.
[6] J. Ballani and D. Kressner, Matrices with hierarchical low-rank structures, in Exploiting hidden structure in matrix computations: algorithms and applications, vol. 2173 of Lecture Notes in Math., Springer, Cham, 2016, pp. 161{209.
[7] R. H. Bartels and G. W. Stewart, Algorithm 432: The solution of the matrix equation AX + XB = C, Communications of the ACM, 15 (1972), pp. 820{826, doi:10.1145/361573.361582.
[8] U. Baur and P. Benner, Factorized solution of Lyapunov equations based on hierarchical matrix arithmetic, Computing, 78 (2006), pp. 211{234, doi:10.1007/s00607-006-0178-y.
[9] B. Beckermann, An error analysis for rational Galerkin projection applied to the Sylvester equation, SIAM J. Numer. Anal., 49 (2011), pp. 2430{2450, https://doi.org/10.1137/110824590.
[10] B. Beckermann and A. Townsend, On the Singular Values of Matrices with Displacement Structure, SIAM J. Matrix Anal. Appl., 38 (2017), pp. 1227{1248, https://doi.org/10.1137/16M1096426.
[11] P. Benner, P. Ezzatti, D. Kressner, E. S. Quintana-Ort , and A. Remon, A mixed-precision algorithm for the solution of Lyapunov equations on hybrid CPU-GPU platforms, Parallel Comput., 37 (2011), pp. 439{ 450, https://doi.org/10.1016/j.parco.2010.12.002.
[12] P. Benner, P. Kurschner, and J. Saak, Self-generating and e cient shift parameters in ADI methods for large Lyapunov and Sylvester equations, Electron. Trans. Numer. Anal., 43 (2014/15), pp. 142{162.
[13] P. Benner and J. Saak, Numerical solution of large and sparse continuous time algebraic matrix Riccati and Lyapunov equations: a state of the art survey, GAMM-Mitt., 36 (2013), pp. 32{52, doi:10.1002/gamm.201310003.
[14] D. A. Bini, S. Massei, and L. Robol, On the decay of the o -diagonal singular values in cyclic reduction, Linear Algebra Appl., 519 (2017), pp. 27{53, doi:10.1016/j.laa.2016.12.027.
[15] S. Birk, De ated shifted block Krylov subspace methods for Hermitian positive de nite matrices, PhD thesis, Wuppertal Univ., 2015.
[16] A. Bonnafe, Estimates and asymptotic expansions for condenser p-capacities. the anisotropic case of segments, Quaestiones Mathematicae, 39 (2016), pp. 911{944, doi:10.2989/16073606.2016.1241955.
[17] S. Borm, E cient numerical methods for non-local operators, vol. 14 of EMS Tracts in Mathematics, European Mathematical Society (EMS), Zurich, 2010, doi:10.4171/091. H2-matrix compression, algorithms and analysis.
[18] D. Braess and W. Hackbusch, Approximation of 1=x by exponential sums in [1; 1), IMA J. Numer. Anal., 25 (2005), pp. 685{697, doi:10.1093/imanum/dri015.
[19] M. Crouzeix and C. Palencia, The numerical range is a (1 + p2)-spectral set, SIAM J. Matrix Anal. Appl., 38 (2017), pp. 649{655, https://doi.org/10.1137/17M1116672.
[20] M. Dahleh, M. A. Dahleh, and G. Verghese, Lectures on Dynamic Systems and Control, Department of Electrical Engineering and Computer Science, MIT, 2004.
[21] T. Damm, Direct methods and ADI-preconditioned Krylov subspace methods for generalized Lyapunov equations, Numer. Linear Algebra Appl., 15 (2008), pp. 853{871, doi:10.1002/nla.603.
[22] E. D. Denman and A. N. Beavers, Jr., The matrix sign function and computations in systems, Appl. Math. Comput., 2 (1976), pp. 63{94, doi:10.1016/0096-3003(76)90020-5.
[23] H. C. Elman, K. Meerbergen, A. Spence, and M. Wu, Lyapunov inverse iteration for identifying Hopf bifurcations in models of incompressible ow, SIAM J. Sci. Comput., 34 (2012), pp. A1584{A1606, https: //doi.org/10.1137/110827600.
[24] T. Ganelius, Rational functions, capacities and approximation, in Aspects of contemporary complex analysis (Proc. NATO Adv. Study Inst., Univ. Durham, Durham, 1979), Academic Press, London-New York, 1980, pp. 409{414.
[25] I. P. Gavrilyuk, W. Hackbusch, and B. N. Khoromskij, Hierarchical tensor-product approximation to the inverse and related operators for high-dimensional elliptic problems, Computing, 74 (2005), pp. 131{157, doi:10.1007/s00607-004-0086-y.
[26] A. A. Gonchar, The problems of E. I. Zolotarev which are connected with rational functions, Mat. Sb. (N.S.), 78 (120) (1969), pp. 640{654.
[27] L. Grasedyck, Existence of a low rank or H-matrix approximant to the solution of a Sylvester equation, Numer. Linear Algebra Appl., 11 (2004), pp. 371{389, doi:10.1002/nla.366.
[28] L. Grasedyck and W. Hackbusch, A multigrid method to solve large scale Sylvester equations, SIAM J. Matrix Anal. Appl., 29 (2007), pp. 870{894, https://doi.org/10.1137/040618102.
[29] L. Grasedyck, W. Hackbusch, and B. N. Khoromskij, Solution of large scale algebraic matrix Riccati equations by use of hierarchical matrices, Computing, 70 (2003), pp. 121{165, doi:10.1007/s00607-002- 1470-0.
[30] L. Grubisic and D. Kressner, On the eigenvalue decay of solutions to operator Lyapunov equations, Systems Control Lett., 73 (2014), pp. 42{47, doi:10.1016/j.sysconle.2014.09.006.
[31] M. H. Gutknecht, Block Krylov space methods for linear systems with multiple right-hand sides: an introduction, Anamaya Publishers, New Delhi, India, 2007, pp. 420{447.
[32] A. Haber and M. Verhaegen, Sparse solution of the Lyapunov equation for large-scale interconnected systems, Automatica J. IFAC, 73 (2016), pp. 256{268, doi:10.1016/j.automatica.2016.06.002.
[33] W. Hackbusch, Hierarchical matrices: algorithms and analysis, vol. 49 of Springer Series in Computational Mathematics, Springer, Heidelberg, 2015, doi:10.1007/978-3-662-47324-5.
[34] M. Heyouni, Extended Arnoldi methods for large Sylvester matrix equations, Technical report L.M.P.A., 2008.
[35] O. Kamen k, Solving SDGE models: A new algorithm for the Sylvester equation, Computational Economics, 25 (2005), pp. 167{187, doi:10.1007/s10614-005-6280-y.
[36] D. L. Kleinman, On an iterative technique for Riccati equation computations, IEEE Trans. Automat. Control, AC-13 (1968), pp. 114{115, doi:10.1109/TAC.1968.1098829.
[37] L. Knizhnerman and V. Simoncini, Convergence analysis of the extended Krylov subspace method for the Lyapunov equation, Numer. Math., 118 (2011), pp. 567{586, https://doi.org/10.1007/s00211-011-0366-3.
[38] J. G. Korvink and B. R. Evgenii, Oberwolfach benchmark collection, in Dimension Reduction of LargeScale Systems, P. Benner, V. Mehrmann, and D. C. Sorensen, eds., vol. 45 of Lecture Notes in Computational Science and Engineering, Springer, Heidelberg, 2005, pp. 311{316. Available from http: //portal.uni-freiburg.de/imteksimulation/downloads/benchmark.
[39] D. Kressner and C. Tobler, Krylov subspace methods for linear systems with tensor product structure, SIAM J. Matrix Anal. Appl., 31 (2010), pp. 1688{1714, doi:10.1137/090756843.
[40] V. Kucera, Algebraic riccati equation: Hermitian and de nite solutions, in The Riccati Equation, Springer, 1991, pp. 53{88.
[41] I. Kuzmanovic and N. Truhar, Sherman-Morrison-Woodbury formula for Sylvester and T -Sylvester equations with applications, Int. J. Comput. Math., 90 (2013), pp. 306{324, doi:10.1080/00207160.2012.716154.
[42] P. Lancaster and L. Rodman, The Algebraic Riccati Equation, Oxford University Press, Oxford, 1995.
[43] B. Le Bailly and J. P. Thiran, Optimal rational functions for the generalized Zolotarev problem in the complex plane, SIAM J. Numer. Anal., 38 (2000), pp. 1409{1424, doi:10.1137/S0036142999360688.
[44] J.-R. Li and J. White, Low-rank solution of Lyapunov equations, SIAM Rev., 46 (2004), pp. 693{713, doi:10.1137/S0895479801384937.
[45] S. Massei, D. Palitta, and L. Robol, Solving rank structured sylvester and lyapunov equations, arXiv preprint arXiv:1711.05493, (2017).
[46] D. Palitta and V. Simoncini, Numerical methods for large-scale Lyapunov equations with symmetric banded data, arXiv 1711.04187, (2017).
[47] S. Pauli, A numerical solver for Lyapunov equations based on the matrix sign function iteration in HSS arithmetic, Semester thesis, ETH Zurich, 2010. Available from http://anchp.ep .ch/students.
[48] T. Penzl, Eigenvalue decay bounds for solutions of Lyapunov equations: the symmetric case, Systems Control Lett., 40 (2000), pp. 139{144, doi:10.1016/S0167-6911(00)00010-4.
[49] J. K. Rice and M. Verhaegen, Distributed control: a sequentially semi-separable approach for spatially heterogeneous linear systems, IEEE Trans. Automat. Control, 54 (2009), pp. 1270{1283, doi:10.1109/TAC.2009.2019802.
[50] S. Richter, L. D. Davis, and E. G. Collins, E cient computation of the solutions to modi ed Lyapunov equations, SIAM J. Matrix Anal. Appl., 14 (1993), pp. 420{431, doi:10.1137/0614030.
[51] E. Ringh, G. Mele, J. Karlsson, and E. Jarlebring, Sylvester-based preconditioning for the waveguide eigenvalue problem, Linear Algebra and its Applications, (2017), doi:10.1016/j.laa.2017.06.027.
[52] J. Sabino, Solution of Large-Scale Lyapunov Equations via the Block Modi ed Smith Methods, PhD thesis, Department of Computational and Applied Mathematics, Rice University, Houston, TX, 2006.
[53] V. Simoncini, A new iterative method for solving large-scale Lyapunov matrix equations, SIAM J. Sci. Comput., 29 (2007), pp. 1268{1288, doi:10.1137/06066120X.
[54] V. Simoncini, Computational methods for linear matrix equations, SIAM Rev., 58 (2016), pp. 377{441, doi:10.1137/130912839.
[55] J. Xia, S. Chandrasekaran, M. Gu, and X. S. Li, Fast algorithms for hierarchically semiseparable matrices, Numer. Linear Algebra Appl., 17 (2010), pp. 953{976, doi:10.1002/nla.691.


Back to previous page
BibTeX entry
	title = {Low-rank updates and a divide-and-conquer method for linear matrix equations},
	author = {Kressner D. and Massei S. and Robol L.},
	publisher = {Society for Industrial and Applied Mathematics,, Philadelphia, PA , Stati Uniti d'America},
	doi = {10.1137/17m1161038 and 10.48550/arxiv.1712.04349},
	journal = {SIAM journal on scientific computing (Print)},
	volume = {41},
	year = {2019}