Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



The parameterized $SR$ algorithm for symplectic (butterfly) matrices

Author: H. Faßbender
Journal: Math. Comp. 70 (2001), 1515-1541
MSC (2000): Primary 65F15
Published electronically: June 27, 2000
MathSciNet review: 1836916
Full-text PDF

Abstract | References | Similar Articles | Additional Information


The $SR$ algorithm is a structure-preserving algorithm for computing the spectrum of symplectic matrices. Any symplectic matrix can be reduced to symplectic butterfly form. A symplectic matrix $B$ in butterfly form is uniquely determined by $4n-1$ parameters. Using these $4n-1$ parameters, we show how one step of the symplectic $SR$ algorithm for $B$ can be carried out in $\mathcal{O}(n)$ arithmetic operations compared to $\mathcal{O}(n^3)$ arithmetic operations when working on the actual symplectic matrix. Moreover, the symplectic structure, which will be destroyed in the numerical process due to roundoff errors when working with a symplectic (butterfly) matrix, will be forced by working just with the parameters.

References [Enhancements On Off] (What's this?)

  • 1. G. BANSE, Symplektische Eigenwertverfahren zur Lösung zeitdiskreter optimaler Steuerungsprobleme, PhD thesis, Fachbereich 3 - Mathematik und Informatik,Universität Bremen, Bremen, Germany, 1995.
  • 2. G. BANSE AND A. BUNSE-GERSTNER, A condensed form for the solution of the symplectic eigenvalue problem, in Systems and Networks: Mathematical Theory and Applications, U. Helmke, R. Menniken, and J. Sauer, eds., Akademie Verlag, 1994, pp. 613-616.
  • 3. P. BENNER AND H. FASSBENDER, The symplectic eigenvalue problem, the butterfly form, the SR algorithm, and the Lanczos method, Linear Algebra Appl., 275-276 (1998), pp. 19-47. MR 99h:65063
  • 4. P. BENNER, H. FASSBENDER, AND D. WATKINS, SR and SZ algorithms for the symplectic (butterfly) eigenproblem, Linear Algebra Appl., 287 (1999), pp. 41-76. MR 99m:65068
  • 5. M. BOHNER, Linear Hamiltonian difference systems: Disconjugacy and Jacobi-type conditions, J. Math. Anal. Appl., 199 (1996), pp. 804-826. MR 97a:39003
  • 6. J. BUNCH, The weak and strong stability of algorithms in numerical algebra, Linear Algebra Appl., 88 (1987), pp. 49-66. MR 88g:65100
  • 7. A. BUNSE-GERSTNER, Matrix factorizations for symplectic QR-like methods, Linear Algebra Appl., 83 (1986), pp. 49-77. MR 88d:15016
  • 8. A. BUNSE-GERSTNER AND V. MEHRMANN, A symplectic QR-like algorithm for the solution of the real algebraic Riccati equation, IEEE Trans. Automat. Control, AC-31 (1986), pp. 1104-1113. MR 87k:93033
  • 9. A. BUNSE-GERSTNER, V. MEHRMANN, AND D. WATKINS, An SR algorithm for Hamiltonian matrices based on Gaussian elimination, Methods of Operations Research, 58 (1989), pp. 339-356. MR 92a:65111
  • 10. J. DELLA-DORA, Numerical linear algorithms and group theory, Linear Algebra Appl., 10 (1975), pp. 267-283. MR 52:4601
  • 11. H. FASSBENDER, Symplectic Methods for Symplectic Eigenproblems, Habilitationsschrift, Universität Bremen, Fachbereich 3 - Mathematik und Informatik, 28334 Bremen, Germany, 1998.
  • 12. U. FLASCHKA, V. MEHRMANN, AND D. ZYWIETZ, An analysis of structure preserving methods for symplectic eigenvalue problems, RAIRO Automatique Productique Informatique Industrielle, 25 (1991), pp. 165-190. MR 92a:65114
  • 13. J. FRANCIS, The QR transformation, Part I and Part II, Comput. J., 4 (1961), pp. 265-271 and 332-345. MR 23:B3143; MR 25:744
  • 14. G. GOLUB AND C. VAN LOAN, Matrix Computations, Johns Hopkins University Press, Baltimore, 3rd ed., 1996. MR 97g:65006
  • 15. V. KUBLANOSKAJA, On some algorithms for the solution of the complete eigenvalue problem, U.S.S.R. Comput. Math. and Math. Phys., 3 (1961), pp. 637-657.
  • 16. P. LANCASTER AND L. RODMAN, The Algebraic Riccati Equation, Oxford University Press, Oxford, 1995. MR 97b:93003
  • 17. V. MEHRMANN, Der SR-Algorithmus zur Berechnung der Eigenwerte einer Matrix, Diplomarbeit, Universität Bielefeld, Bielefeld, FRG, 1979.
  • 18. -, The Autonomous Linear Quadratic Control Problem, Theory and Numerical Solution, no. 163 in Lecture Notes in Control and Information Sciences, Springer-Verlag, Heidelberg, 1991. MR 93d:93004
  • 19. C. PAIGE AND C. VAN LOAN, A Schur decomposition for Hamiltonian matrices, Linear Algebra Appl., 14 (1981), pp. 11-32. MR 84d:65019
  • 20. T. PAPPAS, A. LAUB, AND N. SANDELL, On the numerical solution of the discrete-time algebraic Riccati equation, IEEE Trans. Automat. Control, AC-25 (1980), pp. 631-641. MR 81h:93065a
  • 21. D. WATKINS AND L. ELSNER, Convergence of algorithms of decomposition type for the eigenvalue problem, Linear Algebra Appl., 143 (1991), pp. 19-47. MR 91m:65114

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 65F15

Retrieve articles in all journals with MSC (2000): 65F15

Additional Information

H. Faßbender
Affiliation: Zentrum Mathematik, Technische Universität München, 80290 München, Germany

Keywords: Symplectic matrix; eigenvalue problem; $SR$ algorithm
Received by editor(s): March 2, 1999
Received by editor(s) in revised form: November 17, 1999
Published electronically: June 27, 2000
Article copyright: © Copyright 2000 American Mathematical Society

American Mathematical Society