Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

A Riemannian Method on Quotient Manifolds for Solving Generalized Lyapunov Equations

  • Published:
Journal of Scientific Computing Aims and scope Submit manuscript

Abstract

In this paper, we consider finding a low-rank approximation to the solution of a large-scale generalized Lyapunov matrix equation in the form of \(A X M + M X A = C\), where A and M are symmetric positive definite matrices. An algorithm called an Increasing Rank Riemannian Method for Generalized Lyapunov Equation (IRRLyap) is proposed by merging the increasing rank technique and Riemannian optimization techniques on the quotient manifold \({\mathbb {R}}_*^{n \times p} / {\mathcal {O}}_p\). To efficiently solve the optimization problem on \({\mathbb {R}}_*^{n \times p} / {\mathcal {O}}_p\), a line-search-based Riemannian inexact Newton’s method is developed with its global convergence and local superlinear convergence rate guaranteed. Moreover, we derive a preconditioner which takes \(M \ne I\) into consideration. Numerical experiments show that the proposed Riemannian inexact Newton’s method and the preconditioner have superior performance, and that IRRLyap is preferable compared to the tested state-of-the-art methods when the lowest rank solution is desired.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Algorithm 1
Algorithm 2
Algorithm 3
Algorithm 4
Fig. 1
Fig. 2

Similar content being viewed by others

Data availability

The datasets generated during and analyzed during the current study are available from the corresponding author on reasonable request.

Notes

  1. The term “equivalent” means if \(X\in {\mathcal {S}}_+(p,n)\) is a stationary point of h then \(\pi (Y)\in {\mathbb {R}}^{n\times p}/{\mathcal {O}}_p\) satisfying \(X=YY^T\) is also a stationary point of f; conversely, if \(\pi (Y)\) is a stationary point of f, then \(X=YY^T\) is a stationary point of h.

  2. A sequence \(\{x_k\}\subset {\mathcal {M}}\) converging to \(x^*\in {\mathcal {M}}\) is superlinear if \( \frac{\textrm{dist}(x^*,x_{k+1})}{\textrm{dist}(x^*,x_k)} \rightarrow 0(k \rightarrow \infty ). \)

  3. A sequence \(\{x_k\}\subset {\mathcal {M}}\) converging to \(x^*\in {\mathcal {M}}\) has Q-order of \(1+\min (1,t)\) if \(\limsup _{k \rightarrow \infty } \frac{\textrm{dist}(x^*,x_{k+1})}{\textrm{dist}(x^*,x_k)^{1+\min (1,t)}} <\infty . \)

  4. The function \(\mathrm {orthonormal(A)}\) returns a orthonormal basis of the column space of A, and is implemented by returning the Q-factor of the thin QR-decomposition of A, for example. In this case, G is given by the inverse of the R-factor.

  5. The data are available at https://www.cise.ufl.edu/research/sparse/matrices/list_by_id.html with different dimensions.

References

  1. Absil, P.-A., Baker, C.G., Gallivan, K.A.: Trust-region methods on Riemannian manifolds. Found. Comput. Math. 7, 303–330 (2007)

    MathSciNet  MATH  Google Scholar 

  2. Absil, P.A., Mahony, R., Sepulchre, R.: Optimization Algorithms on Matrix Manifolds. Princeton University Press, Princeton (2008)

    MATH  Google Scholar 

  3. Antoulas, A.C.: Approximation of large-scale dynamical systems. In: Advances in Design and Control (2005)

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

    MATH  Google Scholar 

  5. Baur, U.: Low rank solution of data-sparse Sylvester equations. Numer. Linear Algebra Appl. 15, 837–851 (2008)

    MathSciNet  MATH  Google Scholar 

  6. Baur, U., Benner, P.: Factorized solution of Lyapunov equations based on hierarchical matrix arithmetic. Computing 78(3), 211–234 (2006)

    MathSciNet  MATH  Google Scholar 

  7. Benner, P., Heiland, J., Werner, S.W.R.: A low-rank solution method for Riccati equations with indefinite quadratic terms. Numer. Algorithms 92, 1083–1103 (2021)

    MathSciNet  MATH  Google Scholar 

  8. Benner, P., Köhler, M., Saak, J.: M-M.E.S.S.-2.1—the matrix equations sparse solvers library (2022). https://www.mpi-magdeburg.mpg.de/projects/mess

  9. Benner, P., Kürschner, P.: Computing real low-rank solutions of Sylvester equations by the factored ADI method. Comput. Math. Appl. 67(9), 1656–1672 (2014)

    MathSciNet  MATH  Google Scholar 

  10. Benner, P., Li, R.-C., Truhar, N.: On the ADI method for Sylvester equations. J. Comput. Appl. Math. 233(4), 1035–1045 (2009)

    MathSciNet  MATH  Google Scholar 

  11. Benner, P., Palitta, D., Saak, J.: On an integrated Krylov-ADI solver for large-scale Lyapunov equations. Numer. Algorithms 92(1), 35–63 (2022)

    MathSciNet  MATH  Google Scholar 

  12. Benner, P., Saak, J.: A semi-discretized heat transfer model for optimal cooling of steel profiles. In: Benner, P., Mehrmann, V., Sorensen, D.C. (eds.) Dimension Reduction of Large-Scale Systems, pp. 353–356. Springer, Berlin (2005)

    MATH  Google Scholar 

  13. Benzi, M., Golub, G.H., Liesen, J.: Numerical solution of saddle point problems. Acta Numer. 14, 1–137 (2005)

    MathSciNet  MATH  Google Scholar 

  14. Boothby, W.M.: An introduction to differentiable manifolds and Riemannian geometry. In: Pure and Applied Mathematics, vol. 63. Elsevier (1975)

  15. Boumal, N.: An Introduction to Optimization on Smooth Manifolds. Cambridge University Press, Cambridge (2023)

    MATH  Google Scholar 

  16. Boumal, N., Absil, P.-A.: Low-rank matrix completion via preconditioned optimization on the Grassmann manifold. Linear Algebra Appl. 475, 200–239 (2015)

    MathSciNet  MATH  Google Scholar 

  17. Burer, S., Monteiro, R.D.C.: A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization. Math. Program. 95(2), 329–357 (2003)

    MathSciNet  MATH  Google Scholar 

  18. Byrd, R.H., Nocedal, J.: A tool for the analysis of quasi-Newton methods with application to unconstrained minimization. SIAM J. Numer. Anal. 26, 727–739 (1989)

    MathSciNet  MATH  Google Scholar 

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

    MathSciNet  MATH  Google Scholar 

  20. Bortoloti, M.A.A., Fernandes, T.A., Ferreira, O.P.: An efficient damped Newton-type algorithm with globalization strategy on Riemannian manifolds. J. Comput. Appl. Math. 403(3), 113853 (2022)

    MathSciNet  MATH  Google Scholar 

  21. Bortoloti, M.A.A., Fernandes, T.A., Ferreira, O.P., Yuan, J.: Damped Newton’s method on Riemannian manifolds. J. Global Optim. 77(3), 643–660 (2018)

    MathSciNet  MATH  Google Scholar 

  22. Dembo, R.S., Eisenstat, S.C., Steihaug, T.: Inexact Newton methods. SIAM J. Numer. Anal. 19(2), 400–408 (1982)

    MathSciNet  MATH  Google Scholar 

  23. Dembo, R.S., Steihaug, T.: Truncated-Newton algorithms for large-scale unconstrained optimization. Math. Program. 26(2), 190–212 (1983)

    MathSciNet  MATH  Google Scholar 

  24. Dennis, J.E., Schnabel, B.: Numerical methods for unconstrained optimization and nonlinear equations. In Prentice Hall Series in Computational Mathematics (1983)

  25. Druskin, V., Simoncini, V.: Adaptive rational Krylov subspaces for large-scale dynamical systems. Syst. Control Lett. 60, 546–560 (2011)

    MathSciNet  MATH  Google Scholar 

  26. Golub, G.H., Van Loan, C.F.: Matrix Computations, 3rd edn. Johns Hopkins University Press, Baltimore (1996)

    MATH  Google Scholar 

  27. Golub, G.H., Nash, S., Van Loan, C.: A Hessenberg-Schur method for the problem AX + XB= C. IEEE Trans. Autom. Control 24(6), 909–913 (1979)

    MathSciNet  MATH  Google Scholar 

  28. Gosea, I.V., Gugercin, S., Beattie, C.: Data-driven balancing of linear dynamical systems. SIAM J. Sci. Comput. 44(1), A554–A582 (2022)

    MathSciNet  MATH  Google Scholar 

  29. Goyal, B., Dogra, A., Agrawal, S., Sohi, B.S., Sharma, A.: Image denoising review: from classical to state-of-the-art approaches. Inf. Fus. 55, 220–244 (2020)

    MATH  Google Scholar 

  30. Grasedyck, L.: Existence of a low rank or H-matrix approximant to the solution of a Sylvester equation. Numer. Linear Algebra Appl. 11, 371–389 (2004)

    MathSciNet  MATH  Google Scholar 

  31. Gugercin, S., Sorensen, D.C., Antoulas, A.C.: A modified low-rank Smith method for large-scale Lyapunov equations. Numerical Algorithms 32(1), 27–55 (2003)

    MathSciNet  MATH  Google Scholar 

  32. Hamadi, M., Jbilou, K., Ratnani, A.: A model reduction method in large scale dynamical systems using an extended-rational block Arnoldi method. J. Appl. Math. Comput. 68, 271–293 (2021)

    MathSciNet  MATH  Google Scholar 

  33. Hammarling, S.: Numerical solution of the stable, non-negative definite Lyapunov equation. SIMA J. Numer. Anal. 2(3), 303–323 (1982). (07)

    MATH  Google Scholar 

  34. Helmke, U., Shayman, M.A.: Critical points of matrix least squares distance functions. Linear Algebra Appl. 215, 1–19 (1995)

    MathSciNet  MATH  Google Scholar 

  35. Hestenes, M.R., Stiefel, E.: Methods of conjugate gradients for solving linear systems. J. Res. Natl. Bur. Stand. 49, 409–435 (1952)

    MathSciNet  MATH  Google Scholar 

  36. Huang, W., Absil, P.-A., Gallivan, K.A.: A Riemannian BFGS method without differentiated retraction for nonconvex optimization problems. SIAM J. Optim. 28(1), 470–495 (2018)

    MathSciNet  MATH  Google Scholar 

  37. Huang, W., Absil, P.A., Gallivan, K.A., Hand, P.: ROPTLIB: an object-oriented C++ library for optimization on Riemannian manifolds. ACM Trans. Math. Softw. 44(4), 1–21 (2018)

    MathSciNet  MATH  Google Scholar 

  38. Huang, W., Absil, P.-A., Gallivan, K.A.: A Riemannian symmetric rank-one trust-region method. Math. Program. 150, 179–216 (2015)

    MathSciNet  MATH  Google Scholar 

  39. Huang, W., Gallivan, K.A.: A limited-memory Riemannian symmetric rank-one trust-region method with a restart strategy. J. Sci. Comput. 93(1), 1 (2022)

    MathSciNet  MATH  Google Scholar 

  40. Huang, W., Gallivan, K.A., Absil, P.-A.: A Broyden class of quasi-Newton methods for Riemannian optimization. SIAM J. Optim. 25, 1660–1685 (2015)

    MathSciNet  MATH  Google Scholar 

  41. Iannazzo, B., Porcelli, M.: The Riemannian Barzilai–Borwein method with nonmonotone line search and the matrix geometric mean computation. IMA J. Numer. Anal. 38, 495–517 (2018)

    MathSciNet  MATH  Google Scholar 

  42. Jódar, L.: Lyapunov matrix equation in system stability and control (Zoran Gajic and Muhammad Tahir Javed Qureshi). SIAM Rev. 38(4), 691–691 (1996)

    MATH  Google Scholar 

  43. Keshavan, R.H., Montanari, A., Sewoong, O.: Matrix completion from noisy entries. J. Mach. Learn. Res. 11, 2057–2078 (2010)

    MathSciNet  MATH  Google Scholar 

  44. Kirsten, G., Simoncini, V.: Order reduction methods for solving large-scale differential matrix Riccati equations. SIAM J. Sci. Comput. 42(4), A2182–A2205 (2020)

    MathSciNet  MATH  Google Scholar 

  45. Li, J.-R., White, J.: Low-rank solution of Lyapunov equations. SIAM Rev. 46(4), 693–713 (2004)

    MathSciNet  MATH  Google Scholar 

  46. Li, X., Ling, S., Strohmer, T., Wei, K.: Rapid, robust, and reliable blind deconvolution via nonconvex optimization. Appl. Comput. Harmon. Anal. 47(3), 893–934 (2019)

    MathSciNet  MATH  Google Scholar 

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

    MathSciNet  MATH  Google Scholar 

  48. Massart, E., Absil, P.-A.: Quotient geometry with simple geodesics for the manifold of fixed-rank positive-semidefinite matrices. SIAM J. Matrix Anal. Appl. 41(1), 171–198 (2020)

    MathSciNet  MATH  Google Scholar 

  49. Mishra, B., Vandereycken, B.: A Riemannian approach to low-rank algebraic Riccati equations (2014)

  50. Moore, B.A.: Principal component analysis in linear systems: controllability, observability, and model reduction. IEEE Trans. Autom. Control 26, 17–32 (1981)

    MathSciNet  MATH  Google Scholar 

  51. Nocedal, J., Wright, S.J.: Numerical Optimization. Springer Series in Operations Research, 2nd edn. Springer, Berlin (2006)

    MATH  Google Scholar 

  52. Palitta, D., Simoncini, V.: Matrix-equation-based strategies for convection-diffusion equations. BIT Numer. Math. 56(2), 751–776 (2016)

    MathSciNet  MATH  Google Scholar 

  53. Penzl, T.: Numerical solution of generalized Lyapunov equations. Adv. Comput. Math. 8(1), 33–48 (1998)

    MathSciNet  MATH  Google Scholar 

  54. Penzl, T.: Eigenvalue decay bounds for solutions of Lyapunov equations: the symmetric case. Syst. Control Lett. 40(2), 139–144 (2000)

    MathSciNet  MATH  Google Scholar 

  55. Ring, W., Wirth, B.: Optimization methods on Riemannian manifolds and their application to shape space. SIAM J. Optim. 22(2), 596–627 (2012)

    MathSciNet  MATH  Google Scholar 

  56. Saak, J., Benner, P.: Efficient numerical solution of the LQR? Problem for the heat equation. In: Proceedings in Applied Mathematics and Mechanics, vol. 4, no. 1 (2004)

  57. Sato, H.: A Dai–Yuan-type Riemannian conjugate gradient method with the weak Wolfe conditions. Comput. Optim. Appl. 64(1), 101–118 (2016)

    MathSciNet  MATH  Google Scholar 

  58. Sato, H., Iwai, T.: A new, globally convergent Riemannian conjugate gradient method. Optimization 64(4), 1011–1031 (2015)

    MathSciNet  MATH  Google Scholar 

  59. Schilders, W.H., Van der Vorst, H.A., Rommes, J. (eds.): Model Order Reduction: Theory, Research Aspects and Applications, vol. 13. Springer, Berlin (2008)

    MATH  Google Scholar 

  60. Simoncini, V.: A new iterative method for solving large-scale Lyapunov matrix equations. SIAM J. Sci. Comput. 29(3), 1268–1288 (2007)

    MathSciNet  MATH  Google Scholar 

  61. Vandereycken, B.: Low-rank matrix completion by Riemannian optimization. SIAM J. Optim. 23(2), 1214–1236 (2013)

    MathSciNet  MATH  Google Scholar 

  62. Vandereycken, B., Vandewalle, S.: A Riemannian optimization approach for computing low-rank solutions of Lyapunov equations. SIAM J. Matrix Anal. Appl. 31(5), 2553–2579 (2010)

    MathSciNet  MATH  Google Scholar 

  63. Wang, Y., Zhao, Z., Bai, Z.: Riemannian Newton-CG methods for constructing a positive doubly stochastic matrix from spectral data. Inverse Prob. 36(11), 115006 (2020)

    MathSciNet  MATH  Google Scholar 

  64. Zhao, Z., Bai, Z., Jin, X.: A Riemannian inexact Newton-CG method for constructing a nonnegative matrix with prescribed realizable spectrum. Numer. Math. 140, 827–855 (2018)

    MathSciNet  MATH  Google Scholar 

  65. Zheng, S., Huang, W., Vandereycken, B., Zhang, X.: Riemannian optimization using three different metrics for Hermitian PSD fixed-rank constraints: an extended version (2023)

  66. Zhu, X.: A Riemannian conjugate gradient method for optimization on the Stiefel manifold. Comput. Optim. Appl. 67, 73–110 (2017)

    MathSciNet  MATH  Google Scholar 

Download references

Funding

This work was partially supported by the National Natural Science Foundation of China (No. 12371311), the Natural Science Foundation of Fujian Province (No. 2023J06004), the Fundamental Research Funds for the Central Universities (No. 20720240151), and Xiaomi Young Talents Program.

Author information

Authors and Affiliations

  1. School of Mathematical Sciences, Xiamen University, Xiamen, China

    Zhenwei Huang & Wen Huang

Authors
  1. Zhenwei Huang
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Wen Huang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Wen Huang.

Ethics declarations

Conflict of interest

On behalf of all authors, the corresponding author states that there is no conflict of interest.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Huang, Z., Huang, W. A Riemannian Method on Quotient Manifolds for Solving Generalized Lyapunov Equations. J Sci Comput 102, 74 (2025). https://doi.org/10.1007/s10915-025-02807-2

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s10915-025-02807-2

Keywords