×

Stability analysis of the two-level orthogonal Arnoldi procedure. (English) Zbl 1382.65102

Summary: The second-order Arnoldi (SOAR) procedure is an algorithm for computing an orthonormal basis of the second-order Krylov subspace. It has found applications in solving quadratic eigenvalue problems and model order reduction of second-order dynamical systems among others. Unfortunately, the SOAR procedure can be numerically unstable. The two-level orthogonal Arnoldi (TOAR) procedure has been proposed as an alternative to SOAR to cure the numerical instability. In this paper, we provide a rigorous stability analysis of the TOAR procedure. We prove that under mild assumptions, the TOAR procedure is backward stable in computing an orthonormal basis of the associated linear Krylov subspace. The benefit of the backward stability of TOAR is demonstrated by its high accuracy in structure-preserving model order reduction of second-order dynamical systems.

MSC:

65F15 Numerical computation of eigenvalues and eigenvectors of matrices
65F35 Numerical computation of matrix norms, conditioning, scaling
65F30 Other matrix algorithms (MSC2010)
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Z. Bai, D. Bindel, J. Clark, J. Demmel, K. S. J. Pister, and N. Zhou, {\it New numerical techniques and tools in SUGAR for 3D MEMS simulation}, in Technical Proceedings of the Fourth International Conference on Modeling and Simulation of Microsystems, Hilton Head Island, USA, Computational Publications, Cambridge, MA, 2001, pp. 31-34.
[2] Z. Bai and Y. Su, {\it Dimension reduction of large-scale second-order dynamical systems via a second-order Arnoldi method}, SIAM J. Sci. Comput., 26 (2005), pp. 1692-1709. · Zbl 1078.65058
[3] Z. Bai and Y. Su, SOAR: {\it A second-order Arnoldi method for the solution of the quadratic eigenvalue problem}, SIAM J. Matrix Anal. Appl., 26 (2005), pp. 640-659. · Zbl 1080.65024
[4] M. J. Balas, {\it Trends in large space structure control theory: Fondest hopes, wildest dreams}, IEEE Trans. Automat. Control, 27 (1982), pp. 522-535. · Zbl 0496.93007
[5] L. Bao, Y. Lin, and Y. Wei, {\it Restarted generalized Krylov subspace methods for solving large-scale polynomial eigenvalue problems}, Numer. Algorithms, 50 (2009), pp. 17-32. · Zbl 1162.65017
[6] D. S. Bindel, {\it Structured and Parameter-Dependent Eigensolvers for Simulation-Based Design of Resonant MEMS}, PhD thesis, EECS Department, University of California, Berkeley, CA, 2006.
[7] A. Björck, {\it Solving linear least squares problems by Gram-Schmidt orthogonalization}, BIT, 7 (1967), pp. 1-21. · Zbl 0183.17802
[8] A. Björck and C. C. Paige, {\it Loss and recapture of orthogonality in the modified Gram-Schmidt algorithm}, SIAM J. Matrix Anal. Appl., 13 (1992), pp. 176-190. · Zbl 0747.65026
[9] J. V. Clark, N. Zhou, D. Bindel, L. Schenato, W. Wu, J. Demmel, and K. S. J. Pister, {\it 3D MEMS simulation modeling using modified nodal analysis}, in Proceedings of the Microscale Systems: Mechanics and Measurements Symposium, SEM, Bethel, CT, 2000, pp. 68-75.
[10] R. R. Craig, {\it Structural Dynamics: An Introduction to Computer Methods}, John Wiley, New York, 1981.
[11] J. W. Daniel, W. B. Gragg, L. Kaufman, and G. W. Stewart, {\it Reorthogonalization and stable algorithms for updating the Gram-Schmidt factorization}, Math. Comput., 30 (1976), pp. 772-795. · Zbl 0345.65021
[12] L. Giraud and J. Langou, {\it When modified Gram-Schmidt generates a well-conditioned set of vectors}, IMA J. Numer. Anal., 22 (2002), pp. 521-528. · Zbl 1027.65050
[13] G. H. Golub and C. F. Van Loan, {\it Matrix Computations}, Johns Hopkins University Press, Baltimore, MD, 1996. · Zbl 0865.65009
[14] N. J. Higham, {\it Accuracy and Stability of Numerical Algorithms}, SIAM, Philadelphia, 1996. · Zbl 0847.65010
[15] Z. Jia and Y. Sun, {\it Implicitly restarted generalized second-order Arnoldi type algorithms for the quadratic eigenvalue problem}, Taiwanese J. Math., 19 (2015), pp. 1-30. Doi: 10.11650/tjm.18.2014.4577. · Zbl 1357.65043
[16] T. R. Kowalski, {\it Extracting a Few Eigenpairs of Symmetric Indefinate Matrix Pencils}, PhD thesis, Department of Mathematics, University of Kentucky, Lexington, KY, 2000.
[17] D. Kressner and J. E. Roman, {\it Memory-efficient Arnoldi algorithms for linearizations of matrix polynomials in Chebyshev basis}, Numer. Linear Algebr., 21 (2014), pp. 569-588. · Zbl 1340.65059
[18] L.-Q. Lee, L. Ge, Z. Li, C. Ng, G. Schussman, and K. Ko, {\it Achievements in ISICs/SAPP collaborations for electromagnetic modeling of accelerators}, J. Phys. Conf. Ser., 16 (2005), pp. 205-209.
[19] L.-Q. Lee, Z. Li, C. Ng, and K. Ko, {\it Omega3P: A parallel finite-element eigenmode analysis code for accelerator cavities}, Technical report SLAC-PUB-13529, Stanford Linear Accelerator Center, Menlo Park, CA, 2009.
[20] R. B. Lehoucq, D. C. Sorensen, and C. Yang, {\it ARPACK Users’ Guide: Solution of Large-Scale Eigenvalue Problems with Implicitly Restarted Arnoldi Methods}, Software Eniviron. Tools 6, SIAM, Philadelphia, 1998. · Zbl 0901.65021
[21] Y.-T. Li, Z. Bai, W.-W. Lin, and Y. Su, {\it A structured quasi-Arnoldi procedure for model order reduction of second-order systems}, Linear Algebra Appl., 436 (2012), pp. 2780-2794. · Zbl 1237.93036
[23] C. Otto, {\it Arnoldi and Jacobi-Davidson Methods for Quadratic Eigenvalue Problems}, Master’s thesis, Institut für Mathematik, Technische Universität Berlin, Berlin, 2004.
[24] B. N. Parlett, {\it The Symmetric Eigenvalue Problem}, Prentice-Hall, Englewood cliffs, NJ, 1980. · Zbl 0431.65017
[25] R. S. Puri, {\it Krylov Subspace Based Direct Projection Techniques for Low Frequency, Fully Coupled, Structural Acoustic Analysis and Optimization}, PhD thesis, Oxford Brookes University, Oxford, 2008.
[26] R. S. Puri and D. Morrey, {\it A comparison of one-and two-sided Krylov-Arnoldi projection methods for fully coupled, damped structural-acoustic analysis}, J. Comput. Acoust., 21 (2013), 1350004. · Zbl 1360.70032
[27] D. Ramaswamy and J. White, {\it Automatic generation of small-signal dynamic macromodels from 3-D simulation}, in Technical Proceedings of the Fourth International Conference on Modeling and Simulation of Microsystems, Computational Publications, Cambridge, MA, 2000, pp. 27-30.
[28] E. B. Rudnyi, {\it MOR for ANSYS}, in System-Level Modeling of MEMS, Wiley-VCH Verlag, Weinheim,Germany, 2013, pp. 425-438.
[29] B. Salimbahrami and B. Lohmann, {\it Order reduction of large scale second-order systems using Krylov subspace methods}, Linear Algebra Appl., 415 (2006), pp. 385-405. · Zbl 1103.93017
[30] R. D. Slone, {\it Fast Frequency Sweep Model Order Reduction of Polynomial Matrix Equations Resulting from Finite Element Discretizations}, PhD thesis, The Ohio State University, Columbus, OH, 2002.
[31] G. W. Stewart, {\it Matrix Algorithms, Volumn II: Eigensystems}, SIAM, Philadelphia, 2001. · Zbl 0984.65031
[32] T.-J. Su and R. R. Craig, {\it Model reduction and control of flexible structures using Krylov vectors}, J. Guidance Control Dynam., 14 (1991), pp. 260-267.
[33] Y. Su, J. Wang, X. Zeng, Z. Bai, C. Chiang, and D. Zhou, {\it SAPOR: second-order Arnoldi method for passive order reduction of RCS circuits}, in Proceedings of the 2004 IEEE/ACM International Conference on Computer-aided Design, IEEE, Piscataway, NJ, 2004, pp. 74-79.
[34] Y. Su, J. Zhang, and Z. Bai, {\it A compact Arnoldi algorithm for Polynomial Eigenvalue Problems}, http://math.cts.nthu.edu.tw/Mathematics/RANMEP
[35] R. Van Beeumen, K. Meerbergen, and W. Michiels, {\it Compact rational Krylov methods for nonlinear eigenvalue problems}, SIAM J. Matrix Anal. Appl., 36 (2015), pp. 820-838. · Zbl 1319.65042
[36] T. Wittig, I. Munteanu, R. Schuhmann, and T. Weiland, {\it Two-step Lanczos algorithm for model order reduction}, IEEE Trans. Magn., 38 (2002), pp. 673-676. · Zbl 1008.78010
[37] H. Wu and A. C. Cangellaris, {\it Krylov model order reduction of finite element approximations of electromagnetic devices with frequency-dependent material properties}, Int. J. Numer. Model. Electron. Netw. Devices Fields, 20 (2007), pp. 217-235. · Zbl 1138.78011
[38] C. Yang, {\it Solving large-scale eigenvalue problems in SciDAC applications}, J. Phys. Conf. Ser., 16 (2005), pp. 425-434.
[39] Y. Zhang and Y. Su, {\it A memory-efficient model order reduction for time-delay systems}, BIT, 53 (2013), pp. 1047-1073. · Zbl 1305.65166
[40] J. Zhu, {\it Structured Eigenvalue Problems and Quadratic Eigenvalue Problems}, PhD thesis, Department of Mathematics, University of California, Berkeley, CA, 2005.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.