The parameterized 𝑆𝑅 algorithm for symplectic (butterfly) matrices

Faßbender, H.

doi:10.1090/S0025-5718-00-01265-5

The parameterized $SR$ algorithm for symplectic (butterfly) matrices
HTML articles powered by AMS MathViewer

by H. Faßbender PDF

Math. Comp. 70 (2001), 1515-1541 Request permission

Abstract:

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

G. Banse, Symplektische Eigenwertverfahren zur Lösung zeitdiskreter optimaler Steuerungsprobleme, PhD thesis, Fachbereich 3 - Mathematik und Informatik,Universität Bremen, Bremen, Germany, 1995.
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.
Peter Benner and Heike Faßbender, The symplectic eigenvalue problem, the butterfly form, the SR algorithm, and the Lanczos method, Proceedings of the Sixth Conference of the International Linear Algebra Society (Chemnitz, 1996), 1998, pp. 19–47. MR 1628381, DOI 10.1016/S0024-3795(97)10049-0
Peter Benner, Heike Faßbender, and David S. Watkins, SR and SZ algorithms for the symplectic (butterfly) eigenproblem, Linear Algebra Appl. 287 (1999), no. 1-3, 41–76. Special issue celebrating the 60th birthday of Ludwig Elsner. MR 1662860, DOI 10.1016/S0024-3795(98)10090-3
Martin Bohner, Linear Hamiltonian difference systems: disconjugacy and Jacobi-type conditions, J. Math. Anal. Appl. 199 (1996), no. 3, 804–826. MR 1386607, DOI 10.1006/jmaa.1996.0177
Charles I. Goldstein, Multigrid preconditioners applied to the iterative solution of singularly perturbed elliptic boundary value problems and scattering problems, Innovative numerical methods in engineering (Atlanta, Ga., 1986) Comput. Mech., Southampton, 1986, pp. 97–102. MR 902863
Angelika Bunse-Gerstner, Matrix factorizations for symplectic $QR$-like methods, Linear Algebra Appl. 83 (1986), 49–77. MR 862732, DOI 10.1016/0024-3795(86)90265-X
Angelika Bunse-Gerstner and Volker Mehrmann, A symplectic QR like algorithm for the solution of the real algebraic Riccati equation, IEEE Trans. Automat. Control 31 (1986), no. 12, 1104–1113. MR 864141, DOI 10.1109/TAC.1986.1104186
A. Bunse-Gerstner, V. Mehrmann, and D. Watkins, An SR algorithm for Hamiltonian matrices based on Gaussian elimination, XII Symposium on Operations Research (Passau, 1987) Methods Oper. Res., vol. 58, Athenäum/Hain/Hanstein, Königstein, 1989, pp. 339–357. MR 1072586
J. Della-Dora, Numerical linear algorithms and group theory, Linear Algebra Appl. 10 (1975), 267–283. MR 383721, DOI 10.1016/0024-3795(75)90074-9
H. Faßbender, Symplectic Methods for Symplectic Eigenproblems, Habilitationsschrift, Universität Bremen, Fachbereich 3 – Mathematik und Informatik, 28334 Bremen, Germany, 1998.
U. Flaschka, V. Mehrmann, and D. Zywietz, An analysis of structure preserving numerical methods for symplectic eigenvalue problems, RAIRO Automat.-Prod. Inform. Ind. 25 (1991), no. 2, 165–189 (English, with French summary). MR 1094350
Morgan Ward, Note on the general rational solution of the equation $ax^2-by^2=z^3$, Amer. J. Math. 61 (1939), 788–790. MR 23, DOI 10.2307/2371337
Gene H. Golub and Charles F. Van Loan, Matrix computations, 3rd ed., Johns Hopkins Studies in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, MD, 1996. MR 1417720
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.
Peter Lancaster and Leiba Rodman, Algebraic Riccati equations, Oxford Science Publications, The Clarendon Press, Oxford University Press, New York, 1995. MR 1367089
V. Mehrmann, Der SR-Algorithmus zur Berechnung der Eigenwerte einer Matrix, Diplomarbeit, Universität Bielefeld, Bielefeld, FRG, 1979.
V. L. Mehrmann, The autonomous linear quadratic control problem, Lecture Notes in Control and Information Sciences, vol. 163, Springer-Verlag, Berlin, 1991. Theory and numerical solution. MR 1133203, DOI 10.1007/BFb0039443
Chris Paige and Charles Van Loan, A Schur decomposition for Hamiltonian matrices, Linear Algebra Appl. 41 (1981), 11–32. MR 649714, DOI 10.1016/0024-3795(81)90086-0
Thrasyvoulos Pappas, Alan J. Laub, and Nils R. Sandell Jr., On the numerical solution of the discrete-time algebraic Riccati equation, IEEE Trans. Automat. Control 25 (1980), no. 4, 631–641. MR 583440, DOI 10.1109/TAC.1980.1102434
D. S. Watkins and L. Elsner, Convergence of algorithms of decomposition type for the eigenvalue problem, Linear Algebra Appl. 143 (1991), 19–47. MR 1077722, DOI 10.1016/0024-3795(91)90004-G