Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Numerical Algorithms
Erschienen in: Numerical Algorithms 2/2020

23.07.2019 | Original Paper

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

verfasst von: Daniel Kressner, Patrick Kürschner, Stefano Massei

Erschienen in: Numerical Algorithms | Ausgabe 2/2020

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

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.
Vorheriger Artikel Optimal subsets in the stability regions of multistep methods
Nächster Artikel Fractional collocation boundary value methods for the second kind Volterra equations with weakly singular kernels

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren
Fußnoten
1
Preliminary results suggest that replacing Algorithm 1 with RADI reduces the time by 10% on average over all used sizes n.
 
Literatur
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
Metadaten
Titel
Low-rank updates and divide-and-conquer methods for quadratic matrix equations
verfasst von
Daniel Kressner
Patrick Kürschner
Stefano Massei
Publikationsdatum
23.07.2019
Verlag
Springer US
Erschienen in
Numerical Algorithms / Ausgabe 2/2020
Print ISSN: 1017-1398
Elektronische ISSN: 1572-9265
DOI
https://doi.org/10.1007/s11075-019-00776-w

Weitere Artikel der Ausgabe 2/2020

Numerical Algorithms 2/2020 Zur Ausgabe

Original Paper

Fractional collocation boundary value methods for the second kind Volterra equations with weakly singular kernels

Original Paper

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

Original Paper

Global uniqueness and solvability of tensor complementarity problems for -tensors

Original Paper

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

Original Paper

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

Original Paper

Interval methods of Adams-Bashforth type with variable step sizes