SpringerLink
Log in

Breaking Van Loan’s Curse: A Quest forStructure-Preserving Algorithms for Dense Structured Eigenvalue Problems

  • Chapter
Numerical Algebra, Matrix Theory, Differential-Algebraic Equations and Control Theory

  • 2589 Accesses

Abstract

In 1981 Paige and Van Loan (Linear Algebra Appl 41:11–32, 1981) posed the open question to derive an \(\mathcal{O}(n^{3})\) numerically strongly backwards stable method to compute the real Hamiltonian Schur form of a Hamiltonian matrix. This problem is known as Van Loan’s curse. This chapter summarizes Volker Mehrmann’s work on dense structured eigenvalue problems, in particular, on Hamiltonian and symplectic eigenproblems. In the course of about 35 years working on and off on these problems the curse has been lifted by him and his co-workers. In particular, his work on SR methods and on URV-based methods for dense Hamiltonian and symplectic matrices and matrix pencils is reviewed. Moreover, his work on structure-preserving methods for other structured eigenproblems is discussed.

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

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
EUR 32.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

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 84.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 109.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free ship** worldwide - see info
Hardcover Book
USD 109.99
Price excludes VAT (USA)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free ship** worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    http://en.wikipedia.org/wiki/Structure_preservation_principle

References

  1. Ammar, G., Mehrmann, V.: On Hamiltonian and symplectic Hessenberg forms. Linear Algebra Appl. 149, 55–72 (1991)

    Article  MATH  MathSciNet  Google Scholar 

  2. Banse, G.: Eigenwertverfahren für symplektische Matrizen zur Lösung zeitdiskreter optimaler Steuerungsprobleme. Z. Angew. Math. Mech. 75(Suppl. 2), 615–616 (1995)

    MathSciNet  Google Scholar 

  3. Banse, G.: Symplektische Eigenwertverfahren zur Lösung zeitdiskreter optimaler Steuerungsprobleme. PhD thesis, Fachbereich 3 – Mathematik und Informatik, Universität Bremen, Bremen (1995)

    Google Scholar 

  4. Banse, G.: Condensed forms for symplectic matrices and symplectic pencils in optimal control. Z. Angew. Math. Mech. 76(Suppl. 3), 375–376 (1996)

    MATH  Google Scholar 

  5. Banse, G., Bunse-Gerstner, A.: A condensed form for the solution of the symplectic eigenvalue problem. In: Helmke, U., Menniken, R., Sauer, J. (eds.) Systems and Networks: Mathematical Theory and Applications, pp. 613–616. Akademie Verlag, Berlin (1994)

    Google Scholar 

  6. Benner, P., Faßbender, H.: An implicitly restarted symplectic Lanczos method for the Hamiltonian eigenvalue problem. Linear Algebra Appl. 263, 75–111 (1997)

    Article  MATH  MathSciNet  Google Scholar 

  7. Benner, P., Faßbender, H.: The symplectic eigenvalue problem, the butterfly form, the SR algorithm, and the Lanczos method. Linear Algebra Appl. 275/276, 19–47 (1998)

    Google Scholar 

  8. Benner, P., Faßbender, H.: An implicitly restarted symplectic Lanczos method for the symplectic eigenvalue problem. SIAM J. Matrix Anal. Appl. 22(3), 682–713 (2000). (electronic)

    Google Scholar 

  9. Benner, P., Faßbender, H., Stoll, M.: A Hamiltonian Krylov-Schur-type method based on the symplectic Lanczos process. Linear Algebra Appl. 435(3), 578–600 (2011)

    Article  MATH  MathSciNet  Google Scholar 

  10. Benner, P., Faßbender, H., Watkins, D.S.: Two connections between the SR and HR eigenvalue algorithms. Linear Algebra Appl. 272, 17–32 (1998)

    Article  MATH  MathSciNet  Google Scholar 

  11. Benner, P., Faßbender, H., Watkins, D.S.: SR and SZ algorithms for the symplectic (butterfly) eigenproblem. Linear Algebra Appl. 287(1–3), 41–76 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  12. Benner, P., Kressner, D., Mehrmann, V.: Structure preservation: a challenge in computational control. Future Gener. Comput. Syst. 19, 1243–1252 (2003)

    Article  Google Scholar 

  13. Benner, P., Kressner, D., Mehrmann, V.: Skew-Hamiltonian and Hamiltonian eigenvalue problems: theory, algorithms and applications. In: Proceedings of the Conference on Applied Mathematics and Scientific Computing, pp. 3–39. Springer, Dordrecht (2005)

    Google Scholar 

  14. Benner, P., Mehrmann, V., Xu, H.: A new method for computing the stable invariant subspace of a real Hamiltonian matrix. J. Comput. Appl. Math. 86(1), 17–43 (1997)

    Article  MATH  MathSciNet  Google Scholar 

  15. Benner, P., Mehrmann, V., Xu, H.: A numerically stable, structure preserving method for computing the eigenvalues of real Hamiltonian or symplectic pencils. Numer. Math. 78(3), 329–358 (1998)

    Article  MATH  MathSciNet  Google Scholar 

  16. Benner, P., Mehrmann, V., Xu, H.: A note on the numerical solution of complex Hamiltonian and skew-Hamiltonian eigenvalue problems. ETNA, Electron. Trans. Numer. Anal. 8, 115–126 (1999)

    Google Scholar 

  17. Bunch, J.R.: The weak and strong stability of algorithms in numerical linear algebra. Linear Algebra Appl. 88/89, 49–66 (1987)

    Google Scholar 

  18. Bunse-Gerstner, A.: Matrix factorizations for symplectic QR-like methods. Linear Algebra Appl. 83, 49–77 (1986)

    Article  MATH  MathSciNet  Google Scholar 

  19. Bunse-Gerstner, A.: Symplectic QR-like methods. Habilitationsschrift, Universität Bielefeld, Bielefeld (1986)

    Google Scholar 

  20. Bunse-Gerstner, A., Byers, R., Mehrmann, V.: A quaternion QR algorithm. Numer. Math. 55(1), 83–95 (1989)

    Article  MATH  MathSciNet  Google Scholar 

  21. Bunse-Gerstner, A., Byers, R., Mehrmann, V.: A chart of numerical methods for structured eigenvalue problems. SIAM J. Matrix Anal. Appl. 13(2), 419–453 (1992)

    Article  MATH  MathSciNet  Google Scholar 

  22. Bunse-Gerstner, A., Mehrmann, V.: A symplectic QR like algorithm for the solution of the real algebraic Riccati equation. IEEE Trans. Automat. Control 31(12), 1104–1113 (1986)

    Article  MATH  MathSciNet  Google Scholar 

  23. Bunse-Gerstner, A., Mehrmann, V.: The HHDR algorithm and its application to optimal control problems. RAIRO Automat.-Prod. Inform. Ind. 23(4), 305–329 (1989)

    MATH  MathSciNet  Google Scholar 

  24. Bunse-Gerstner, A., Mehrmann, V., Watkins, D.S.: An SR algorithm for Hamiltonian matrices based on Gaussian elimination. In: XII Symposium on Operations Research (Passau, 1987). Volume 58 of Methods of Operations Research, pp. 339–357. Athenäum/Hain/Hanstein, Königstein (1989)

    Google Scholar 

  25. Byers, R.: Hamiltonian and symplectic algorithms for the algebraic Riccati equation. PhD thesis, Department Computer Science, Cornell University, Ithaca (1983)

    Google Scholar 

  26. Byers, R.: A Hamiltonian QR-algorithm. SIAM J. Sci. Stat. Comput. 7, 212–229 (1986)

    Article  MATH  MathSciNet  Google Scholar 

  27. Byers, R., Kressner, D.: Structured condition numbers for invariant subspaces. SIAM J. Matrix Anal. Appl. 28(2), 326–347 (2006). (electronic)

    Google Scholar 

  28. Byers, R., Mehrmann, V., Xu, H.: A structured staircase algorithm for skew-symmetric/symmetric pencils. ETNA, Electron. Trans. Numer. Anal. 26, 1–33 (2007)

    Google Scholar 

  29. Chu, D., Liu, X., Mehrmann, V.: A numerical method for computing the Hamiltonian Schur form. Numer. Math. 105(3), 375–412 (2007)

    Article  MATH  MathSciNet  Google Scholar 

  30. Della-Dora, J.: Sur quelques Algorithmes de recherche de valeurs propres. Thése, L’Université Scientifique et Medicale de Grenoble (1973)

    Google Scholar 

  31. Elsner, L.: On some algebraic problems in connection with general eigenvalue algorithms. Linear Algebra Appl. 26, 123–138 (1979)

    Article  MATH  MathSciNet  Google Scholar 

  32. Faßbender, H.: Error analysis of the symplectic Lanczos method for the symplectic eigenvalue problem. BIT 40(3), 471–496 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  33. Faßbender, H.: Symplectic Methods for the Symplectic Eigenproblem. Kluwer Academic/Plenum, New York (2000)

    MATH  Google Scholar 

  34. Faßbender, H.: The parameterized SR algorithm for symplectic (butterfly) matrices. Math. Comput. 70(236), 1515–1541 (2001)

    Article  Google Scholar 

  35. Ferng, W.R., Lin, W.-W., Wang, C.-S.: The shift-inverted J-Lanczos algorithm for the numerical solutions of large sparse algebraic Riccati equations. Comput. Math. Appl. 33(10), 23–40 (1997)

    Article  MATH  MathSciNet  Google Scholar 

  36. Flaschka, U., Mehrmann, V., Zywietz, D.: An analysis of structure preserving numerical methods for symplectic eigenvalue problems. RAIRO Automat.-Prod. Inform. Ind. 25(2), 165–189 (1991)

    MATH  MathSciNet  Google Scholar 

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

    Google Scholar 

  38. Higham, N.J., Mackey, D.S., Mackey, N., Tisseur, F.: Symmetric linearizations for matrix polynomials. SIAM J. Matrix Anal. Appl. 29(1), 143–159 (2006/2007). (electronic)

    Google Scholar 

  39. Karow, M., Kressner, D., Tisseur, F.: Structured eigenvalue condition numbers. SIAM J. Matrix Anal. Appl. 28(4), 1052–1068 (2006). (electronic)

    Google Scholar 

  40. Laub, A.J.: A Schur method for solving algebraic Riccati equations. IEEE Trans. Automat. Control AC-24, 913–921 (1979)

    Google Scholar 

  41. Lin, W.-W., Ho, T.-C.: On Schur type decompositions for Hamiltonian and symplectic pencils. Technical report, Institute of Applied Mathematics, National Tsing Hua University, Taiwan (1990)

    Google Scholar 

  42. Lin, W.-W., Mehrmann, V., Xu, H.: Canonical forms for Hamiltonian and symplectic matrices and pencils. Linear Algebra Appl. 301–303, 469–533 (1999)

    Article  MathSciNet  Google Scholar 

  43. Mackey, D.S., Mackey, N., Mehl, C., Mehrmann, V.: Vector spaces of linearizations for matrix polynomials. SIAM J. Matrix Anal. Appl. 28(4), 971–1004 (2006). (electronic)

    Google Scholar 

  44. Mackey, D.S., Mackey, N., Tisseur, F.: Structured map** problems for matrices associated with scalar products. I. Lie and Jordan algebras. SIAM J. Matrix Anal. Appl. 29(4), 1389–1410 (2007)

    Article  MathSciNet  Google Scholar 

  45. Mehrmann, V.: Der SR-Algorithmus zur Berechnung der Eigenwerte einer Matrix. Diplomarbeit, Universität Bielefeld, Bielefeld (1979)

    Google Scholar 

  46. Mehrmann, V.: A symplectic orthogonal method for single input or single output discrete time optimal quadratic control problems. SIAM J. Matrix Anal. Appl. 9(2), 221–247 (1988)

    Article  MATH  MathSciNet  Google Scholar 

  47. Mehrmann, V.: The Autonomous Linear Quadratic Control Problem, Theory and Numerical Solution. Volume 163 of Lecture Notes in Control and Information Sciences. Springer, Heidelberg (1991)

    Google Scholar 

  48. Mehrmann, V., Schröder, C., Watkins, D.S.: A new block method for computing the Hamiltonian Schur form. Linear Algebra Appl. 431(3–4), 350–368 (2009)

    Article  MATH  MathSciNet  Google Scholar 

  49. Mehrmann, V., Watkins, D.: Structure-preserving methods for computing eigenpairs of large sparse skew-Hamiltonian/Hamiltonian pencils. SIAM J. Matrix Anal. Appl. 22, 1905–1925 (2000)

    MathSciNet  Google Scholar 

  50. Paige, C.C., Van Loan, C.F.: A Schur decomposition for Hamiltonian matrices. Linear Algebra Appl. 41, 11–32 (1981)

    Article  MATH  MathSciNet  Google Scholar 

  51. Stewart, G.W.: An updating algorithm for subspace tracking. IEEE Trans. Signal Proc. 40, 1535–1541 (1992)

    Article  Google Scholar 

  52. Stewart, G.W.: Updating a rank-revealing ULV decomposition. SIAM J. Matrix Anal. Appl. 14(2), 494–499 (1993)

    Article  MATH  MathSciNet  Google Scholar 

  53. Van Loan, C.F.: A symplectic method for approximating all the eigenvalues of a Hamiltonian matrix. Linear Algebra Appl. 61, 233–251 (1984)

    Article  MATH  MathSciNet  Google Scholar 

  54. Watkins, D.S.: On Hamiltonian and symplectic Lanczos processes. Linear Algebra Appl. 385, 23–45 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  55. Watkins, D.S.: On the reduction of a Hamiltonian matrix to Hamiltonian Schur form. Electron. Trans. Numer. Anal. 23, 141–157 (2006). (electronic)

    Google Scholar 

  56. Watkins, D.S.: The Matrix Eigenvalue Problem. Society for Industrial and Applied Mathematics (SIAM), Philadelphia (2007)

    Google Scholar 

  57. Watkins, D.S., Elsner, L.: Chasing algorithms for the eigenvalue problem. SIAM J. Matrix Anal. Appl. 12, 374–384 (1991)

    Article  MATH  MathSciNet  Google Scholar 

  58. Watkins, D.S., Elsner, L.: Convergence of algorithms of decomposition type for the eigenvalue problem. Linear Algebra Appl. 143, 19–47 (1991)

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Fachbereich Mathematik/Informatik, Zentrum für Technomathematik, Universität Bremen, 28334, Bremen, Germany

    Angelika Bunse-Gerstner

  2. Institut Computational Mathematics, AG Numerik, Technische Universität Braunschweig, Pockelsstr. 14, 38106, Braunschweig, Germany

    Heike Faßbender

Authors
  1. Angelika Bunse-Gerstner
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Heike Faßbender
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Heike Faßbender .

Editor information

Editors and Affiliations

  1. Max Planck Institute for Dynamics of Complex Technical Systems, Magdeburg, Germany

    Peter Benner

  2. Carl-Friedrich-Gauß Fakultät, TU Braunschweig, Institute Computational Mathematics, Braunschweig, Germany

    Matthias Bollhöfer

  3. MATHICSE, École Polytechnique Fédérale de Lausanne (EPFL), Lausanne, Switzerland

    Daniel Kressner

  4. Institute of Mathematics, T U Berlin, Berlin, Germany

    Christian Mehl

  5. Institute of Mathematics, University of Augsburg, Augsburg, Germany

    Tatjana Stykel

Rights and permissions

Reprints and permissions

Copyright information

© 2015 Springer International Publishing Switzerland

About this chapter

Cite this chapter

Bunse-Gerstner, A., Faßbender, H. (2015). Breaking Van Loan’s Curse: A Quest forStructure-Preserving Algorithms for Dense Structured Eigenvalue Problems. In: Benner, P., Bollhöfer, M., Kressner, D., Mehl, C., Stykel, T. (eds) Numerical Algebra, Matrix Theory, Differential-Algebraic Equations and Control Theory. Springer, Cham. https://doi.org/10.1007/978-3-319-15260-8_1

Download citation

Publish with us

Policies and ethics

Search

Navigation