Mathematics of Computation

Author(s): H. Faßbender.
Journal: Math. Comp. 70 (2001), 1515-1541.
MSC (2000): Primary 65F15
Posted: June 27, 2000
Retrieve article in: PDF DVI PostScript
This article is available free of charge

The

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

in butterfly form is uniquely determined by

parameters. Using these

parameters, we show how one step of the symplectic

algorithm for

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.

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

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6842(e) ISSN 0025-5718(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2008, American Mathematical Society Privacy Statement		Search the AMS