Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Numerical Algorithms
Published in: Numerical Algorithms 2/2020

23-07-2019 | Original Paper

Low-rank updates and divide-and-conquer methods for quadratic matrix equations

Authors: Daniel Kressner, Patrick Kürschner, Stefano Massei

Published in: Numerical Algorithms | Issue 2/2020

Log in

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

search-config
loading …

Abstract

In this work, we consider two types of large-scale quadratic matrix equations: continuous-time algebraic Riccati equations, which play a central role in optimal and robust control, and unilateral quadratic matrix equations, which arise from stochastic processes on 2D lattices and vibrating systems. We propose a simple and fast way to update the solution to such matrix equations under low-rank modifications of the coefficients. Based on this procedure, we develop a divide-and-conquer method for quadratic matrix equations with coefficients that feature a specific type of hierarchical low-rank structure, which includes banded matrices. This generalizes earlier work on linear matrix equations. Numerical experiments indicate the advantages of our newly proposed method versus iterative schemes combined with hierarchical low-rank arithmetic.
previous article Optimal subsets in the stability regions of multistep methods
next article Fractional collocation boundary value methods for the second kind Volterra equations with weakly singular kernels

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
Footnotes
1
Preliminary results suggest that replacing Algorithm 1 with RADI reduces the time by 10% on average over all used sizes n.
 
Literature
1.
Abels, J., Benner, P.: CAREX - a collection of benchmark examples for continuous-time algebraic Riccati equations (Version 2.0). SLICOT working note 1999–14 (1999)
2.
Ambikasaran, S., Darve, E.: An \(\mathcal {O}(n\log N)\) fast direct solver for partial hierarchically semi-separable matrices: with application to radial basis function interpolation. J. Sci. Comput. 57(3), 477–501 (2013)MathSciNetMATH
3.
Baur, U., Benner, P.: Factorized solution of Lyapunov equations based on hierarchical matrix arithmetic. Computing 78(3), 211–234 (2006)MathSciNetMATH
4.
Beckermann, B., Reichel, L.: Error estimates and evaluation of matrix functions via the Faber transform. SIAM J. Numer. Anal. 47(5), 3849–3883 (2009)MathSciNetMATH
5.
Beckermann, B., Townsend, A.: On the singular values of matrices with displacement structure. SIAM J. Matrix Anal. Appl. 38(4), 1227–1248 (2017)MathSciNetMATH
6.
Benner, P., Bollhöfer, M., Kressner, D., Mehl, C., Stykel, T.: Numerical algebra, matrix theory, differential-algebraic equations and control theory. Springer International Publishing (2015)
7.
Benner, P., Bujanović, Z., Kürschner, P., Saak, J.: A numerical comparison of solvers for large-scale, continuous-time algebraic Riccati equations. Technical Report 1811.00850 arXiv (2018)
8.
Benner, P., Bujanović, Z., Kürschner, P., Saak, J.: RADI: A low-rank ADI-type algorithm for large scale algebraic Riccati equations. Numer. Math. 138 (2), 301–330 (2018)MathSciNetMATH
9.
Benner, P., Byers, R., Mehrmann, V., Xu, H.: Robust numerical methods for robust control Technical Report 06-2004. Institut für Mathematik, TU Berlin (2004)
10.
Benner, P., Li, J., Penzl, T.: Numerical solution of large-scale Lyapunov equations, Riccati equations, and linear-quadratic optimal control problems. Numer. Linear Algebra Appl. 15(9), 755–777 (2008)MathSciNetMATH
11.
Benner, P., Saak, J.: Numerical solution of large and sparse continuous time algebraic matrix Riccati and Lyapunov equations: a state of the art survey. GAMM-Mitt. 36(1), 32–52 (2013)MathSciNetMATH
12.
Berljafa, M., Elsworth, S., Güttel, S.: A Rational Krylov Toolbox for MATLAB MIMS EPrint 2014.56, Manchester Institute for Mathematical Sciences, The University of Manchester, UK (2014)
13.
Bini, D.A., Favati, P., Meini, B.: A compressed cyclic reduction for QBD processes with low-rank upper and lower transitions. In: Matrix-analytic methods in stochastic models, volume 27 of Springer Proc. Math. Stat., pp. 25–40. Springer, New York (2013)
14.
Bini, D.A., Iannazzo, B., Meini, B.: Numerical Solution of Algebraic Riccati Equations, Volume 9 of Fundamentals of Algorithms. SIAM Publications, Philadelphia (2012)MATH
15.
Bini, D.A., Latouche, G., Meini, B.: Numerical methods for structured Markov chains. Numerical Mathematics and Scientific Computation. Oxford University Press, New York (2005). Oxford Science PublicationsMATH
16.
Bini, D.A., Massei, S., Robol, L.: Efficient cyclic reduction for quasi-birth-death problems with rank structured blocks. Appl. Numer Math. 116, 37–46 (2017)MathSciNetMATH
17.
Bini, D.A., Massei, S., Robol, L.: On the decay of the off-diagonal singular values in cyclic reduction. Linear Algebra Appl. 519, 27–53 (2017)MathSciNetMATH
18.
Bini, D.A., Meini, B.: The cyclic reduction algorithm: from Poisson equation to stochastic processes and beyond. In memoriam of Gene H. Golub. Numer. Algorithms 51(1), 23–60 (2009)MathSciNetMATH
19.
Chu, E. K. -W., Fan, H. -Y., Lin, W. -W.: A structure-preserving doubling algorithm for continuous-time algebraic Riccati equations. Linear Algebra Appl. 396, 55–80 (2005)MathSciNetMATH
20.
Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to algorithms, 3rd edn. MIT Press, Cambridge (2009)MATH
21.
Datta, B.N.: Numerical linear algebra and applications, 2nd edn. Society for Industrial and Applied Mathematics (SIAM), Philadelphia (2010)MATH
22.
Druskin, V., Simoncini, V.: Adaptive rational Krylov subspaces for large-scale dynamical systems. Syst. Cont. Lett. 60(8), 546–560 (2011)MathSciNetMATH
23.
Grasedyck, L., Hackbusch, W., Khoromskij, B.N.: Solution of large scale algebraic matrix Riccati equations by use of hierarchical matrices. Computing 70(2), 121–165 (2003)MathSciNetMATH
24.
Guo, C., Higham, N.J., Tisseur, F.: Detecting and solving hyperbolic quadratic eigenvalue problems. SIAM J. Matrix Anal. Appl. 30(4), 1593–1613 (2008/09)
25.
Guo, X., Lin, W., Xu, S.: A structure-preserving doubling algorithm for nonsymmetric algebraic Riccati equation. Numer Math. 103(3), 393–412 (2006)MathSciNetMATH
26.
Güttel, S.: Rational Krylov methods for operator functions. PhD thesis, TU Freiberg (2010)
27.
Hackbusch, W.: Hierarchical matrices: algorithms and analysis, Volume 49 of Springer Series in Computational Mathematics. Springer, Berlin (2015)
28.
Heyouni, M.: Extended Arnoldi methods for large low-rank Sylvester matrix equations. Appl. Numer. Math. 60(11), 1171–1182 (2010)MathSciNetMATH
29.
Higham, N.J., Kim, H.: Numerical analysis of a quadratic matrix equation. IMA J. Numer Anal. 20(4), 499–519 (2000)MathSciNetMATH
30.
Kressner, D., Massei, S., Robol, L.: Low-rank updates and a divide-and-conquer method for linear matrix equations. SIAM J. Sci. Comput. 41(2), A848–A876 (2019)MathSciNetMATH
31.
Feng, E.B., Rudnyi L., Koziol, D., Korvink, J.G.: Parametric model reduction for fast simulation of cyclic voltammograms. Sens. Lett. 4(2), 165–173 (2006)
32.
Lancaster, P.: Lambda-matrices and vibrating systems. Dover Publications, Inc., Mineola (2002). Reprint of the 1966 original [Pergamon Press, New York; MR0210345 (35 #1238)]MATH
33.
Lancaster, P., Rodman, L.: The Algebraic Riccati Equation. Oxford University Press, Oxford (1995)MATH
34.
Lang, N., Mena, H., Saak, J.: On the benefits of the LDLT factorization for large-scale differential matrix equation solvers. Linear Algebra Appl. 480, 44–71 (2015)MathSciNetMATH
35.
Latouche, G., Ramaswami, V.: Introduction to matrix analytic methods in stochastic modeling. ASA-SIAM Series on Statistics and Applied Probability. Society for Industrial and Applied Mathematics (SIAM), Philadelphia (1999). American Statistical Association, Alexandria, VAMATH
36.
Locatelli, A.: Optimal control: an introduction. Basel, Switzerland (2001)MATH
37.
38.
Mehrmann, V., Tan, E.: Defect correction methods for the solution of algebraic Riccati equations. IEEE Trans Automat. Control 33(7), 695–698 (1988)MathSciNetMATH
39.
Melman, A.: Generalization and variations of Pellet’s theorem for matrix polynomials. Linear Algebra Appl. 439(5), 1550–1567 (2013)MathSciNetMATH
40.
Miyazawa, M.: Tail decay rates in double QBD processes and related reflected random walks. Math. Oper. Res. 34(3), 547–575 (2009)MathSciNetMATH
41.
Ruhe, A.: The rational Krylov algorithm for nonsymmetric eigenvalue problems. III: Complex shifts for real matrices. BIT Numer. Math. 34(1), 165–176 (1994)MathSciNetMATH
42.
Ruhe, A.: Rational Krylov: A practical algorithm for large sparse nonsymmetric matrix pencils. SIAM J. Sci. Comput. 19(5), 1535–1551 (1998)MathSciNetMATH
43.
Russell, D.L.: Mathematics of Finite-Dimensional Control Systems, volume 43 of Lect. Notes Pure Appl Math. Marcel Dekker Inc., New York (1979)
44.
Seneta, E.: Non-negative matrices and Markov chains. Springer Series in Statistics. Springer, New York (2006). Revised reprint of the second (1981) edition [Springer-Verlag, New York; MR0719544]MATH
45.
Sima, V.: Algorithms for linear-quadratic optimization, volume 200 of Pure and Applied Mathematics. Marcel Dekker, Inc., New York (1996)
46.
Simoncini, V.: A new iterative method for solving large-scale Lyapunov matrix equations. SIAM J. Sci. Comput. 29(3), 1268–1288 (2007)MathSciNetMATH
47.
Simoncini, V.: Analysis of the rational Krylov subspace projection method for large-scale algebraic Riccati equations. SIAM J. Matrix Anal. Appl. 37(4), 1655–1674 (2016)MathSciNetMATH
48.
Simoncini, V., Szyld, D.B., Monsalve, M.: On two numerical methods for the solution of large-scale algebraic Riccati equations. IMA J. Numer. Anal. 34(3), 904–920 (2013)MathSciNetMATH
49.
Starke, G.: Near-circularity for the rational Zolotarev problem in the complex plane. J. Approx. Theory 70(1), 115–130 (1992)MathSciNetMATH
50.
The MORwiki Community. Scanning electrochemical microscopy MORwiki – Model Order Reduction Wiki (2018)
51.
Tisseur, F.: Backward error and condition of polynomial eigenvalue problems. Linear Algebra Appl. 309(1-3), 339–361 (2000)MathSciNetMATH
52.
Willems, J.C.: Least squares stationary optimal control and the algebraic Riccati Equation. IEEE Trans. Autom. Control 16, 621–634 (1971)MathSciNet
Metadata
Title
Low-rank updates and divide-and-conquer methods for quadratic matrix equations
Authors
Daniel Kressner
Patrick Kürschner
Stefano Massei
Publication date
23-07-2019
Publisher
Springer US
Published in
Numerical Algorithms / Issue 2/2020
Print ISSN: 1017-1398
Electronic ISSN: 1572-9265
DOI
https://doi.org/10.1007/s11075-019-00776-w

Other articles of this Issue 2/2020

Numerical Algorithms 2/2020 Go to the issue

Original Paper

A new modified three-step iteration method for G-nonexpansive mappings in Banach spaces with a graph

Original Paper

The global convergence of the BFGS method under a modified Yuan-Wei-Lu line search technique

Original Paper

A gradient-type algorithm with backward inertial steps associated to a nonconvex minimization problem

Original Paper

Preconditioned quasi-compact boundary value methods for space-fractional diffusion equations

Original Paper

Chebyshev-Legendre spectral method and inverse problem analysis for the space fractional Benjamin-Bona-Mahony equation

Original Paper

Three-step alternating iterations for index 1 and non-singular matrices

Premium Partner

    Image Credits