Abstract
The inexact Newton method developed earlier for computing deflating subspaces associated with separated groups of finite eigenvalues of regular linear large sparse non-Hermitian matrix pencils is specialized to solve eigenproblems arising in the hydrodynamic temporal stability analysis. To this end, for linear systems to be solved at each step of the Newton method, a new efficient MLILU2 preconditioner based on the multilevel 2nd order incomplete LU-factorization is proposed. A special variant of Krylov subspace method IDR2 with right preconditioning is developed. In comparison with GMRES it requires much smaller workspace while may converge considerably faster than BiCGStab. The effectiveness of the proposed methods is illustrated with matrix pencils of order up to 3.1 ⋅ 106 arising in the temporal linear stability analysis of a typical hydrodinamic flow.
Acknowledgements
The authors would like to thank the anonymous referee for detailed and valuable comments, which helped to considerably improve the exposition of the paper.
Funding: The work was supported by the Russian Science Foundation (project No. 17-71-20149).
References
[1] A. Arakawa and V. R. Lamb, Computational design of the basic dynamical processes of the UCLA general circulation model, Meth. Comput. Phys. 17 (1977), 173–265.10.1016/B978-0-12-460817-7.50009-4Search in Google Scholar
[2] Z. Bai, J. Demmel, J. Dongarra, A. Ruhe, and H. van der Vorst (Eds.), Templates for the Solution of Algebraic Eigenvalue Problems: a Practical Guide, SIAM, Philadelphia, 2000.10.1137/1.9780898719581Search in Google Scholar
[3] M. Benzi, G. H. Golub, and J. Liesen, Numerical solution of saddle point problems, Acta Numerica, 14 (2005), 1–137.10.1017/S0962492904000212Search in Google Scholar
[4] M. Benzi and J. Liu, Block preconditioning for saddle point systems with indefinite (1, 1) block, Int. J. Comput. Math., 84 (2007), 1117–1129.10.1080/00207160701356605Search in Google Scholar
[5] A. V. Boiko, A. V. Dovgal, G. R. Grek, and V. V. Kozlov, Physics of Transitional Shear Flows, Springer, Berlin, 2012.10.1007/978-94-007-2498-3Search in Google Scholar
[6] A. V. Boiko and Yu. M. Nechepurenko, Numerical spectral analysis of temporal stability of laminar flows in ducts of constant cross-sections, J. Comput. Math. Math. Phys., 48 (2008), 1731–1747.10.1134/S0965542508100011Search in Google Scholar
[7] M. Bollhöfer and Y. Saad, Multilevel preconditioners constructed from inverse-based ILUs, SIAM J. Sci. Comput., 27 (2006), 1627–1650.10.1137/040608374Search in Google Scholar
[8] M. Bollhöfer, Y. Saad, and O. Schenk, ILUPACK-preconditioning software package, 2010. Available online at the URL: http://ilupack.tu-bs.de.Search in Google Scholar
[9] C. Campos, J. E. Roman, E. Romero, and A. Tomas, SLEPc Users Manual, Technical Report DSIC-II/24/02, 2013.Search in Google Scholar
[10] E. Chow and Y. Saad, Experimental study of ILU preconditioners for indefinite matrices, J. Comput. Appl. Math., 86 (1997), 387–414.10.1016/S0377-0427(97)00171-4Search in Google Scholar
[11] K. V. Demyanko and Yu. M. Nechepurenko, Dependence of the linear stability of Poiseuille flows in a rectangular duct on the cross-sectional aspect ratio, Dokl. Phys., 56 (2011), 531–533.10.1134/S1028335811100077Search in Google Scholar
[12] K. V. Demyanko and Yu. M. Nechepurenko, Linear stability analysis of Poiseuille flow in a rectangular duct. Russ. J. Numer. Anal. Math. Modelling, 28 (2013), 125–148.10.1515/rnam-2013-0008Search in Google Scholar
[13] K. V. Demyanko, Yu. M. Nechepurenko, and M. Sadkane, A Newton-like method for computing deflating subspaces, J. Numer. Math., 23 (2015), 289–301.10.1515/jnma-2015-0019Search in Google Scholar
[14] P. G. Drazin, Introduction to Hydrodynamic Stability, Cambridge University Press, Cambridge, 2002.10.1017/CBO9780511809064Search in Google Scholar
[15] G. El Khoury, Yu. M. Nechepurenko, and M. Sadkane, Acceleration of inverse subpsace iteration with Newton’s method, J. Comput. Appl. Math., 259 (2014), 205–215.10.1016/j.cam.2013.06.046Search in Google Scholar
[16] M. A. Freitag and A. Spence, A tuned preconditioner for inexact inverse iteration applied to Hermitian eigenvalue problems, IMA J. Numer. Anal., 28 (2008), 522–551.10.1093/imanum/drm036Search in Google Scholar
[17] S. K. Godunov and Yu. M. Nechepurenko, Bounds for the convergence rate of Newton’s method for calculating invariant subspaces, J. Comput. Math. Math. Phys., 42 (2002), 739–746.Search in Google Scholar
[18] S. K. Godunov, Modern Aspects of Linear Algebra, Transl. of Math. Monographs Amer. Math. Soc., 1998.10.1090/mmono/175Search in Google Scholar
[19] G. H. Golub and Ch. Van Loan, Matrix Computations, second ed., The John Hopkins University Press, 1989.Search in Google Scholar
[20] M. H. Gutknecht, Variants of BiCGStab for matrices with complex spectrum, SIAM J. Sci. Comput., 14 (1993), 1020–1033.10.1137/0914062Search in Google Scholar
[21] G. Hechme, Yu. M. Nechepurenko, and M. Sadkane, Efficient methods for computing spectral projectors for linearized hydrodynamic equations, SIAM J. Sci. Comput., 31 (2008), 667–686.10.1137/050648122Search in Google Scholar
[22] V. Hernandez, J. E. Roman, A. Tomas, and V. Vidal, A survey of software for sparse eigenvalue problems, SLEPc Technical Report STR-6 (slepc 3.0.0), 2009. Available online at the URL: http://slepc.upv.es/.Search in Google Scholar
[23] I. E. Kaporin, High quality preconditionings of a general symmetric positive definite matrix based on its UTU + UTR + RTU – decomposition, Numer. Lin. Alg. Appl., 5 (1998), 483–509.10.1002/(SICI)1099-1506(199811/12)5:6<483::AID-NLA156>3.0.CO;2-7Search in Google Scholar
[24] I. E. Kaporin, Second order ILU preconditioning for nonsymmetric matrices, In: Int. Conf. on Matrix Methods and Operator Equations, June 20–25, Moscow, Russia (2005).Search in Google Scholar
[25] I. Kaporin, Multilevel ILU preconditionings for general unsymmetric matrices, In: Proc. Int. Conf. NUMGRID/VORONOI-2008, June 10–13, Moscow, Russia (2008), 150–157.Search in Google Scholar
[26] I. N. Konshin, M. A. Olshanskii, and Y. V. Vassilevski, ILU preconditioners for nonsymmetric saddle-point matrices with application to the incompressible Navier–Stokes equations, SIAM J. Sci. Comput., 37 (2015), A2171–A2197.10.1137/15M1012311Search in Google Scholar
[27] I. Konshin, M. Olshanskii, and Y. Vassilevski, LU factorizations and ILU preconditioning for stabilized discretizations of incompressible Navier–Stokes equations, Numer. Linear Algebra Appl., 24 (2017), e2085.10.1002/nla.2085Search in Google Scholar
[28] N. Li and Y. Saad, Crout versions of ILU factorization with pivoting for sparse symmetric matrices, Electron. Trans. Numer. Anal., 20 (2005), 75–85.Search in Google Scholar
[29] Yu. M. Nechepurenko, On the dimension reduction of linear differential-algebraic control systems, Dokl. Math., 86 (2012), 457–459.10.1134/S1064562412040059Search in Google Scholar
[30] M. Robbe, M. Sadkane, and A. Spence, Inexact inverse subspace iteration with preconditioning applied to non-Hermitian eigenvalue problems, SIAM J. Matrix Anal. Appl., 31 (2009), 92–113.10.1137/060673795Search in Google Scholar
[31] Y. Saad, Multilevel ILU with reorderings for diagonal dominance, SIAM J. Sci. Comput., 27 (2005), 1032–1057.10.1137/030602733Search in Google Scholar
[32] Y. Saad, M. H. Schultz, GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM J. Sci. and Stat. Comput., 7 (1986), 856–869.10.1137/0907058Search in Google Scholar
[33] P. J. Schmid and D. S. Henningson, Stability and Transition in Shear Flows, Springer, Berlin, 2000.10.1007/978-1-4613-0185-1Search in Google Scholar
[34] G. L. G. Sleijpen and H. A. van der Vorst, A Jacobi–Davidson iteration method for linear eigenvalue problems, SIAM J. Matrix Anal. Appl., 17 (1996), 401–425.10.1137/S0036144599363084Search in Google Scholar
[35] P. Sonneveld and M. B. Van Gijzen, IDR(s): A family of simple and fast algorithms for solving large nonsymmetric systems of linear equations, SIAM J. Sci. Comput., 31 (2008), 1035–1062.10.1137/070685804Search in Google Scholar
[36] M. B. Van Gijzen amd P. Sonneveld, Algorithm 913: An elegant IDR(s) variant that efficiently exploits bi-orthogonality properties. ACM Trans. Math. Software, 38 (2011), 5:1–5:19.10.1145/2049662.2049667Search in Google Scholar
[37] T. Tatsumi and T. Yoshimura, Stability of the laminar flow in a rectangular duct, J. Fluid Mech., 212 (1990), 437–449.10.1017/S002211209000204XSearch in Google Scholar
[38] V. Theofilis, P. W. Duck, and J. Owen, Viscous linear stability analysis of rectangular duct and cavity flow, J. Fluid Mech., 505 (2004), 249–286.10.1017/S002211200400850XSearch in Google Scholar
[39] M. Tismenetskyi, A new preconditioning technique for solving large sparse linear systems, Linear Algebra Appl., 154 (1991), 331–353.10.1016/0024-3795(91)90383-8Search in Google Scholar
[40] H. A. van der Vorst, Bi-CGSTAB: A fast and smoothly converging variant of Bi-CG for the solution of nonsymmetric linear systems, SIAM J. Sci. Stat. Comput., 13 (1992), 631–644.10.1137/0913035Search in Google Scholar
[41] F. Xue and H. C. Elman, Fast inexact subspace iteration for generalized eigenvalue problems with spectral transformation, Linear Algebra Appl., 435 (2011), 601–622.10.1016/j.laa.2010.06.021Search in Google Scholar
[42] L. Yu, J. P. Barbot, G. Zheng, and H. Sun, Compressive sensing with chaotic sequence, IEEE Signal Proc. Let., 17 (2010), 731–734.10.1109/LSP.2010.2052243Search in Google Scholar
© 2020 Walter de Gruyter GmbH, Berlin/Boston