Arnoldi Method and Its Application in Flow Stability Problem
-
摘要: 流动稳定性问题常常归结于巨型非对称矩阵特征值问题。多数求解巨型非对称矩阵特征问题的算法均是经基本的Arnoldi算法演化而来。首先简述基本的Arnoldi算法; 其次简述基于Arnoldi算法的几类变体, 如显式重启Arnoldi算法,隐式重启Arnoldi算法与多重隐式重启Arnoldi算法; 最后基于Arnoldi算法及其变体结合谱位移技术求解计算流动稳定性问题, 并通过数值实验比较可知结合谱位移技术的多重隐式重启Arnoldi算法的求解效率最高。
-
关键词:
- Arnoldi算法 /
- 特征值 /
- Hessenberg矩阵 /
- 流动稳定性
Abstract: The problem of flow stability is often attributed to the eigenvalue problem of giant asymmetric matrix. Most algorithms for solving the eigenvalue problems of giant asymmetric matrices are evolved from the basic Arnoldi algorithm. Firstly, the basic Arnoldi algorithm was briefly described. Secondly, several variants based on Arnoldi algorithm were briefly described, such as explicitly restarted Arnoldi algorithm, implicitly restarted Arnoldi algorithm and multiple implicitly restarted Arnoldi algorithm. Finally, the Arnoldi algorithm and its variants, combined with spectral displacement technology to solve the problem of flow stability. Through numerical experiments, it is found that the multiple implicitly restarted Arnoldi algorithm combined with spectral displacement technology has the highest efficiency.-
Key words:
- Arnoldi algorithm /
- eigenvalue /
- Hessenberg matrix /
- flow stability
-
表 1 3种方法求解不可压缩二维流动比较
Table 1. Comparison of three methods for solving two-dimensional incompressible flow
methods CPU/s ITE m restarted Arnoldi * * 25 implicitly restarted Arnoldi 0.445 065 35 25 multiple implicitly restarted Arnoldi 0.218 831 1 29 表 2 3种方法分别求解来流Ma=2.5的平板边界层流动比较
Table 2. Comparison of three methods for solving the boundary layer on a flat plate at incoming Mach number Ma=2.5
methods CPU ITE m restarted Arnoldi 25.386 330 s 56 50 implicitly restarted Arnoldi 11.892 779 s 5 50 multiple implicitly restarted Arnoldi 11.434 565 s 1 52 表 3 3种方法求解不可压缩二维流动比较
Table 3. Comparison of three methods for solving two-dimensional incompressible flow
methods CPU/s ITE m E restarted Arnoldi 186.418 92 2 50 0.050 060 74-0.003 5251i implicitly restarted Arnoldi 513.948 11 1 50 0.048 060 73-0.003 466 2i multiple implicitly restarted Arnoldi 137.648 17 1 55 0.049 090 03-0.003 381 3i -
[1] Wilkinson J H. 代数特征值问题[M]. 石钟慈, 邓健新, 译. 北京: 科学出版社, 1987.Wilkinson J H. Algebraic eigenvalue problem[M]. Shi Z C, Deng J X, trans. Beijing: Science Press, 1987(in Chinese). [2] Golub G H, van Loan C F. Matrix computations[M]. 3rd ed. Baltimore: The Johns Hopkins University Press, 1996. [3] Parlett B N, Poole Jr W G. A geometric theory for the QR, LU and power iterations[J]. SIAM Journal on Numerical Analysis, 1973, 10(2): 389-412. doi: 10.1137/0710035 [4] Ford W. The algebraic eigenvalue problem[A]. Ford W. Numerical Linear Algebra with Applications[M]. San Diego, CA: Academic Press, 2015: 379-438. [5] Clint M, Jennings A. A simultaneous iteration method for the unsymmetric eigenvalue problem[J]. IMA Journal of Applied Mathematics, 1971, 8(1): 111-121. doi: 10.1093/imamat/8.1.111 [6] Clint M, Jennings A. The evaluation of eigenvalues and eigenvectors of real symmetric matrices by simultaneous iteration[J]. The Computer Journal, 1970, 13(1): 76-80. doi: 10.1093/comjnl/13.1.76 [7] Cullum J, Willoughby R A, Lake M. A lanczos algorithm for computing singular values and vectors of large matrices[J]. SIAM Journal on Scientific and Statistical Computing, 1983, 4(2): 197-215. doi: 10.1137/0904015 [8] Lanczos C. An iteration method for the solution of the eigenvalue problem of linear differential and integral operators[J]. Journal of Research of the National Bureau of Standards, 1950, 45(4): 255-282. doi: 10.6028/jres.045.026 [9] Parlett B N. The symmetric eigenvalue problem[J]. Society for Industrial and Applied Mathematics, 1980, 348: 1-13. [10] Parlett B N, Scott D S. The Lanczos algorithm with selective orthogonalization[J]. Mathematics of Computation, 1979, 33(145): 217-238. doi: 10.1090/S0025-5718-1979-0514820-3 [11] Hirao K, Nakatsuji H. A generalization of the Davidson's method to large nonsymmetric eigenvalue problems[J]. Journal of Computational Physics, 1982, 45(2): 246-254. doi: 10.1016/0021-9991(82)90119-X [12] Morgan R B, Scott D S. Generalizations of Davidson's method for computing eigenvalues of sparse symmetric matrices[J]. SIAM Journal on Scientific and Statistical Computing, 1986, 7(3): 817-825. doi: 10.1137/0907054 [13] Crouzeix M, Philippe B, Sadkane M. The Davidson method[J]. SIAM Journal on Scientific Computing, 1994, 15(1): 62-76. doi: 10.1137/0915004 [14] Arnoldi W E. The principle of minimized iterations in the solution of the matrix eigenvalue problem[J]. Quarterly of Applied Mathematics, 1951, 9(1): 17-29. doi: 10.1090/qam/42792 [15] Jia Z X. Refined iterative algorithms based on Arnoldi's process for large unsymmetric eigenproblems[J]. Linear Algebra and its Applications, 1997, 259: 1-23. doi: 10.1016/S0024-3795(96)00238-8 [16] 吕良福. 求解大型特征值问题的块Davidson方法的精化和收缩技术[D]. 南京: 南京航空航天大学, 2004.Lyu L F. Refining-strategy and deflation technique of block Davidson method for solving large sparse eigenproblems[D]. Nanjing: Nanjing University of Aeronautics and Astronautics, 2004(in Chinese). [17] 吕良福, 戴华. 求解大型特征值问题的块Davidson方法的精化技术[J]. 黑龙江大学自然科学学报, 2006, 23(1): 100-104. doi: 10.3969/j.issn.1001-7011.2006.01.023Lyu L F, Dai H. Refining-strategy of block Davidson method for solving large sparse eigenproblems[J]. Journal of natural science of Heilongjiang University, 2006, 23 (1): 100-104(in Chinese). doi: 10.3969/j.issn.1001-7011.2006.01.023 [18] Bai Z J, Day D, Demmel J, et al. A test matrix collection for non-hermitian eigenvalue problems (Release 1.0)[R]. Technical Report CS-97-355, 1997. [19] Kerner W. Large-scale complex eigenvalue problems[J]. Journal of Computational Physics, 1989, 85(1): 1-85. doi: 10.1016/0021-9991(89)90200-3 [20] Saad Y. Krylov subspace methods for solving large unsymmetric linear systems[J]. Mathematics of Computation, 1981, 37(155): 105-126 doi: 10.1090/S0025-5718-1981-0616364-6 [21] Karush W. An iterative method for finding characteristic vectors of a symmetric matrix[J]. Pacific Journal of Mathematics, 1951, 1(2): 233-248. doi: 10.2140/pjm.1951.1.233 [22] Saad Y. Variations on Arnoldi's method for computing eigenelements of large unsymmetric matrices[J]. Linear Algebra and its Applications, 1980, 34: 269-295. doi: 10.1016/0024-3795(80)90169-X [23] Saad Y. Projection methods for solving large sparse eigenvalue problems[A]. Kágström B, Ruhe A. Matrix Pencils. Proceedings of A Conference Held at Pite Havsbad[M]. Sweden: Springer, 1983, 973: 121-144. [24] Saad Y. Chebyshev acceleration techniques for solving nonsymmetric eigenvalue problems[J]. Mathematics of Computation, 1984, 42(166): 567-588. doi: 10.1090/S0025-5718-1984-0736453-8 [25] Cullum J, Donath W E. A block Lanczos algorithm for computing the Q algebraically largest eigenvalues and a corresponding eigenspace of large, sparse, real symmetric matrices[C]. IEEE Conference on Decision and Control Including the Symposium on Adaptive Processes. Phoenix, Arizona: IEEE, 1974. [26] Cullum J. The simultaneous computation of a few of the algebraically largest and smallest eigenvalues of a large, sparse, symmetric matrix[J]. Bit Numerical Mathematics, 1978, 18(3): 265-275. doi: 10.1007/BF01930896 [27] Ho D. Tchebychev acceleration technique for large scale nonsymmetric matrices[J]. Numerische Mathematik, 1989, 56(7): 721-734. doi: 10.1007/BF01405199 [28] Sadkane M. A block Arnoldi-Chebyshev method for computing the leading eigenpairs of large sparse unsymmetric matrices[J]. Numerische Mathematik, 1993, 64(1): 181-193. doi: 10.1007/BF01388686 [29] Jia Z X. The convergence of generalized lanczos methods for large unsymmetric eigenproblems[J]. SIAM Journal on Matrix Analysis and Applications, 1995, 16(3): 843-862. doi: 10.1137/S0895479893246753 [30] Jia Z X. A refined iterative algorithms based on the block Arnoldi process for large unsymmetric eigenproblems[J]. Linear Algebra & Its Applications, 1998, 270: 171-189. [31] Jia Z X. Polynomial characterizations of the approximate eigenvectors by the refined Arnoldi method and an implicitly restarted refined Arnoldi algorithm[J]. Linear Algebra and its Applications, 1999, 287(1/3): 191-214. [32] 曹陶桃. 求解大型非对称矩阵特征问题的精化Arnoldi-Chebyshev方法[D]. 南京: 南京航空航天大学, 2006.Cao T T. Refined Arnoldi-Chebyshev method for large unsymmetric eigenproblems[D]. Nanjing: Nanjing University of Aeronautics and Astronautics, 2006(in Chinese). [33] Sorensen D C. Implicit application of polynomial filters in a K-step Arnoldi method[J]. SIAM Journal on Matrix Analysis and Applications, 1992, 13(1): 357-385. doi: 10.1137/0613025 [34] Fazeli S A S, Emad N, Liu Z F. A key to choose subspace size in implicitly restarted Arnoldi method[J]. Numerical Algorithms, 2015, 70(2): 407-426. doi: 10.1007/s11075-014-9954-5 [35] Lehoucq R B, Sorensen D C. Deflation techniques for an implicitly restarted Arnoldi iteration[J]. SIAM Journal on Matrix Analysis and Applications, 1996, 17(4): 789-821. doi: 10.1137/S0895479895281484 [36] Emad N, Petiton S G, Edjlali G. Multiple explicitly restarted Arnoldi method for solving large eigenproblems[J]. SIAM Journal on Scientific Computing, 2005, 27(1): 253-277. doi: 10.1137/S1064827500366082 [37] Fender A, Emad N, Petiton S, et al. Leveraging accelerators in the multiple implicitly restarted Arnoldi method with nested subspaces[C]. IEEE International Conference on Emerging Technologies and Innovative Business Practices for the Transformation of Societies. Balaclava, Mauritius: IEEE, 2016. [38] Liu Z F, Emad N, Amor S B, et al. PageRank computation using a multiple implicitly restarted Arnoldi method for modeling epidemic spread[J]. International Journal of Parallel Programming, 2015, 43(6): 1028-1053. doi: 10.1007/s10766-014-0344-3 [39] Golub G H, Greif C. An Arnoldi-type algorithm for computing page rank[J]. BIT Numerical Mathematics, 2006, 46(4): 759-771. doi: 10.1007/s10543-006-0091-y [40] Theofilis V. Advances in global linear instability analysis of nonparallel and three-dimensional flows[J]. Progress in Aerospace Sciences, 2003, 39(4): 249-315. doi: 10.1016/S0376-0421(02)00030-1 [41] Theofilis V. Global linear instability[J]. Annual Review of Fluid Mechanics, 2011, 43(1): 319-352. doi: 10.1146/annurev-fluid-122109-160705 [42] Pedro P G. Advances in global instability computations: from incompressible to hypersonic flow[D]. Madrid: Universidad Politécnica de Madrid, 2014. [43] 赵磊. 高超声速后掠钝板边界层横流定常涡失稳的研究[D]. 天津: 天津大学, 2016.Zhao L. Study on instability of stationary crossfrow vortices in hypersonic Swept blunt plate boundary layer[D]. Tianjin: Tianjin University, 2016(in Chinese). [44] 郗有成. 基于全局稳定性分析的高速边界层感受性与稳定性研究[D]. 北京: 清华大学, 2021.Chi Y C. Study on sensitivity and stability of high-speed boundary layer based on global stability analysis[D]. Beijing: Tsinghua University, 2021(in Chinese). [45] Loiseau J C, Bucci M A, Cherubini S, et al. Time-stepping and Krylov methods for large-scale instability problems[J]. Arxiv, 2018, 50: 53-73. [46] Ruhe A. Rational Krylov algorithms for nonsymmetric eigenvalue problems. Ⅱ. matrix pairs[J]. Linear Algebra and its Applications, 1994, 197-198: 283-295. doi: 10.1016/0024-3795(94)90492-8 [47] Morgan R B, Zeng M. Harmonic projection methods for large non-symmetric eigenvalue problems[J]. Numerical Linear Algebra with Applications, 1998, 5(1): 33-55. doi: 10.1002/(SICI)1099-1506(199801/02)5:1<33::AID-NLA125>3.0.CO;2-1 [48] Schmid P J, Henningson D S. Stability and transition in shear flows[M]. World Publishing Corporation, 2014. [49] Dubois J, Calvin C, Petiton S G. Accelerating the explicitly restarted Arnoldi method with GPUs using an autotuned matrix vector product[J]. SIAM Journal on Scientific Computing, 2011, 33(5): 3010-3019. doi: 10.1137/10079906X [50] Braman K, Byers A, Mathias R. The multishift QR algorithm. Part Ⅰ: maintaining well-focused shifts and level 3 performance[J]. SIAM Journal on Matrix Analysis and Applications, 2002, 23(4): 929-947. doi: 10.1137/S0895479801384573 [51] Stathopoulos A, Saad Y, Wu K S. Dynamic thick restarting of the Davidson, and the implicitly restarted Arnoldi methods[J]. SIAM Journal on Scientific Computing, 1998, 19(1): 227-245. doi: 10.1137/S1064827596304162 [52] Malik M R. Numerical methods for hypersonic boundary layer stability[J]. Journal of Computational Physics, 1990, 86(2): 376-413. doi: 10.1016/0021-9991(90)90106-B [53] Lehoucq R B, Sorensen D C, Yang C. ARPACK users' guide: solution of large scale eigenvalue problems with implicitly restarted Arnoldi methods[J]. DBLP, 1998, 28: 67-77. [54] 曹志浩. 矩阵特征值问题[M]. 上海: 上海科学技术出版社, 1980.Cao Z H. Matrix eigenvalue problem[M]. Shanghai: Science and Technology Press, 1980(in Chinese). [55] Tezuka A, Suzuki K. Three-dimensional global linear stability analysis of flow around a spheroid[J]. AIAA Journal, 2006, 44(8): 1697-1708. doi: 10.2514/1.16632 [56] 陈曦. 高超声速边界层转捩问题研究[D]. 北京: 北京大学, 2018.Chen X. Research on hypersonic boundary layer transition[D]. Beijing: Peking University, 2018(in Chinese). [57] 陈曦, 陈坚强, 董思卫, 等. 高超声速6°迎角圆锥边界层背风流向涡稳定性分析[J]. 空气动力学学报, 2020, 38(2): 299-307. https://www.cnki.com.cn/Article/CJFDTOTAL-KQDX202002013.htmChen X, Chen J Q, Dong S W, et al. Stability analyses of leeward streamwise vortices for a hypersonic yawed cone at 6 degree angle of attack[J]. Journal of aerodynamics, 2020, 38 (2): 299-307(in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-KQDX202002013.htm [58] Schmid P J, Henningson D S. Stability and transition in shear flows[M]. New York: Springer Verlag, 2014. [59] Malik M R. Numerical methods for hypersonic boundary layer stability[J]. Journal of Computational Physics, 1990, 86(2): 376-413. doi: 10.1016/0021-9991(90)90106-B