Implicit QR algorithms for palindromic and even eigenvalue problems
Tóm tắt
In the spirit of the Hamiltonian QR algorithm and other bidirectional chasing algorithms, a structure-preserving variant of the implicit QR algorithm for palindromic eigenvalue problems is proposed. This new palindromic QR algorithm is strongly backward stable and requires less operations than the standard QZ algorithm, but is restricted to matrix classes where a preliminary reduction to structured Hessenberg form can be performed. By an extension of the implicit Q theorem, the palindromic QR algorithm is shown to be equivalent to a previously developed explicit version. Also, the classical convergence theory for the QR algorithm can be extended to prove local quadratic convergence. We briefly demonstrate how even eigenvalue problems can be addressed by similar techniques.
Tài liệu tham khảo
Bai, Z., Demmel, J.W.: On swapping diagonal blocks in real Schur form. Linear Algebra Appl. 186, 73–95 (1993)
Braman, K., Byers, R., Mathias, R.: The multishift QR algorithm. I. Maintaining well-focused shifts and level 3 performance. SIAM J. Matrix Anal. Appl. 23(4), 929–947 (2002)
Braman, K., Byers, R., Mathias, R.: The multishift QR algorithm. II. Aggressive early deflation. SIAM J. Matrix Anal. Appl. 23(4), 948–973 (2002)
Byers, R.: A hamiltonian QR algorithm. SIAM J. Sci. Statist. Comput. 7(1), 212–229 (1986)
Byers, R., Kressner, D.: Structured condition numbers for invariant subspaces. SIAM J. Matrix Anal. Appl. 28(2), 326–347 (2006)
Chu, E.K.-W., Hwang, T.-M., Lin, W.-W., Wu, C.-T.: Vibration of Fast Trains, Palindromic Eigenvalue Problems and Structure-Preserving Doubling Algorithms. Technical report, School of Mathematical Sciences, Monash University, Australia, January (2007)
Elsner, L., Sun, J.-G.: Perturbation theorems for the generalized eigenvalue problem. Linear Algebra Appl. 48, 341–357 (1982)
Golub, G.H., Van Loan, C.F.: Matrix Computations, 3rd edn. Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins University Press, Baltimore (1996)
Hilliges, A., Mehl, C., Mehrmann, V.: On the solution of palindromic eigenvalue problems. In: Proceedings of the 4th European Congress on Computational Methods in Applied Sciences and Engineering (ECCOMAS). Jyväskylä, Finland, CD-ROM (2004)
Horn, R.A., Sergeichuk, V.V.: Canonical forms for complex matrix congruence and *congruence. Linear Algebra Appl. 416(2–3), 1010–1032 (2006)
Horn, R.A., Sergeichuk, V.V.: A regularization algorithm for matrices of bilinear and sesquilinear forms. Linear Algebra Appl. 412(2–3), 380–395 (2006)
Kågström, B., Kressner, D.: Multishift variants of the QZ algorithm with aggressive early deflation. SIAM J. Matrix Anal. Appl. 29(1), 199–227 (2006–2007)
Kågström, B., Poromaa, P.: Computing eigenspaces with specified eigenvalues of a regular matrix pair (A,B) and condition estimation: theory, algorithms and software. Numer. Algorithms 12(3–4), 369–407 (1996)
Kressner, D.: Numerical methods for general and structured eigenvalue problems. Lecture Notes in Computational Science and Engineering, vol. 46. Springer, Berlin (2005)
Kressner, D., Peláez, M.J., Moro, J.: Structured Hölder condition numbers for multiple eigenvalues. Uminf report, Department of Computing Science, Umea University, Sweden, October (2006)
Mackey, D.S., Mackey, N., Mehl, C., Mehrmann, V.: Structured polynomial eigenvalue problems: good vibrations from good linearizations. SIAM J. Matrix Anal. Appl. 28(4), 1029–1051 (2006)
Mackey, D.S., Mackey, N., Mehl, C., Mehrmann, V.: Numerical methods for palindromic eigenvalue problems: computing the anti-triangular Schur form. Technical Report 409, DFG Research Center Matheon, Mathematics for key technologies in Berlin, TU Berlin, Str. des 17. Juni 136, D-10623 Berlin, Germany. http://www.matheon.de (2007, to appear in Numer. Linear Algebra Appl.)
Mehl, C.: On asymptotic convergence of nonsymmetric Jacobi algorithms. Preprint 393, Matheon - DFG Research Center Mathematics for key techonolgies, Technische Universität Berlin, Straße des 17. Juni 136, 10623 Berlin, FRG. SIAM J. Matrix Anal. Appl. 30, 291–311 (2008)
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)
Penzl, T.: Lyapack users guide. Technical report SFB393/00-33, Sonderforschungsbereich 393 Numerische Simulation auf massiv parallelen Rechnern, TU Chemnitz, 09107 Chemnitz, FRG (2000)
Rodman, L.: Bounded and stably bounded palindromic difference equations of first order. Electron. J. Linear Algebra 15, 22–49 (2006)
Rump, S.M.: Eigenvalues, pseudospectrum and structured perturbations. Linear Algebra Appl. 413(2–3), 567–593 (2006)
Schröder, C.: A canonical form for palindromic pencils and palindromic factorizations. Preprint 316, TU Berlin, Matheon, Germany (2006)
Schröder, C.: A QR-like algorithm for the palindromic eigenvalue problem. Preprint 388, TU Berlin, Matheon, Germany (2007)
Schröder, C.: URV decomposition based structured methods for palindromic and even eigenvalue problems. Preprint 375, TU Berlin, Matheon, Germany, March (2007, submitted)
Schröder, C.: Palindromic and even eigenvalue problems—analysis and numerical methods. Ph.D. thesis, Technical University Berlin, Germany (2008)
Stewart, G.W.: On the sensitivity of the eigenvalue problem Ax = λBx. SIAM J. Numer. Anal. 9, 669–686 (1972)
Stewart, G.W., Sun, J.-G.: Matrix Perturbation Theory. Computer Science and Scientific Computing. Academic, Boston (1990)
Thompson, R.C.: The characteristic polynomial of a principal subpencil of a Hermitian matrix pencil. Linear Algebra Appl. 14, 135–177 (1976)
Thompson, R.C.: Pencils of complex and real symmetric and skew matrices. Linear Algebra Appl. 147, 323–371 (1991)
Watkins, D.S.: QR-like algorithms—an overview of convergence theory and practice. In: The Mathematics of Numerical Analysis (Park City, UT, 1995). Lectures in Appl. Math, vol. 32, pp. 879–893. American Mathematical Society, Providence (1996)
Watkins, D.S.: The transmission of shifts and shift blurring in the QR algorithm. Linear Algebra Appl. 241–243, 877–896 (1996)
Watkins, D.S.: The Matrix Eigenvalue Problem: GR and Krylov Subspace Methods. SIAM, Philadelphia (2007)
Watkins, D.S., Elsner, L.: Convergence of algorithms of decomposition type for the eigenvalue problem. Linear Algebra Appl. 143, 19–47 (1991)
Watkins, D.S., Elsner, L.: Theory of decomposition and bulge-chasing algorithms for the generalized eigenvalue problem. SIAM J. Matrix Anal. Appl. 15(3), 943–967 (1994)
Wilkinson, J.H.: The Algebraic Eigenvalue Problem. Monographs on Numerical Analysis. Oxford Science, Clarendon, Oxford (1988)