Application of matrix bandwidth reduction technique in implicit discontinuous Galerkin
-
摘要:
为了数值求解二维Euler方程,以间断有限元方法作为空间离散、向后差分公式(BDF)作为时间离散。针对采用牛顿法求解源于隐式时间积分的非线性方程组,构造了相应的Jacobi矩阵,其具有阶数高、稀疏性强、数值非对称的特点。在每个时间步内,选择带预处理的广义极小残量(GMRES)方法求解线性方程组,预处理矩阵由不完全LU分解(ILU)方法构造。将矩阵带宽缩减技术应用于上述求解过程,无需额外的存储空间,就缩小了预处理矩阵与系数矩阵的差距,从而加快了GMRES方法的收敛、增大了可用的时间步长。通过求解典型的空气动力学问题,检验了该应用的有效性。
-
关键词:
- 间断有限元 /
- 隐式方法 /
- 线性方程组 /
- 广义极小残量(GMRES)方法 /
- 矩阵带宽缩减
Abstract:To numerically solve the two-dimensional Euler equations, discontinuous Galerkin method and backward difference formula (BDF) are used as spatial and temporal discretization, respectively. The Newton-Raphson method is taken to solve the nonlinear equations arising from the implicit time integration. The Jacobia matrix is constructed. Owing to the high-order, sparsity and non-symmetry of the matrix, the preconditioned generalized minimal residual (GMRES) method is chosen in every time step for solving the linear equations. The preconditioner is constructed using incomplete lower-upper (ILU) decomposition method. The bandwidth reduction technique is applied to the solution of the linear equations. Without extra storage cost, the application narrows the difference between the preconditioner and the coefficient matrix, thus accelerating the convergence of GMRES method and increasing the available time step size for temporal integration. Typical aerodynamic problems are solved to test the effectiveness of the application.
-
表 1 GMRES的迭代步数(圆柱绕流)
Table 1. Iteration steps of GMRES(flow around a cylinder)
CFL 带宽未经缩减 带宽经过缩减 5 6 4 10 11 5 20 15 6 表 2 预处理矩阵与系数矩阵之差的Frobenius范数(圆柱绕流)
Table 2. Frobenius norm for difference between preconditioner and coefficient matrix (flow around a cylinder)
CFL 带宽未经缩减 带宽经过缩减 5 40 34 10 205 85 20 40 157 203 表 3 GMRES的迭代步数(NACA0012翼型绕流)
Table 3. Iteration steps of GMRES(flow around NACA0012 airfoil)
CFL 带宽未经缩减 带宽经过缩减 5 5 4 10 14 5 20 未收敛 6 表 4 预处理矩阵与系数矩阵之差的Frobenius范数(NACA0012翼型绕流)
Table 4. Frobenius norm for difference between preconditioner and coefficient matrix(flow around NACA0012)
CFL 带宽未经缩减 带宽经过缩减 5 42 33 10 280 86 20 334 511 205 表 5 GMRES的迭代步数(RAE2822翼型绕流)
Table 5. Iteration steps of GMRES (flow around RAE2822 airfoil)
CFL 带宽未经缩减 带宽经过缩减 10 7 5 20 10 5 40 33 6 表 6 预处理矩阵与系数矩阵之差的Frobenius范数(RAE2822翼型绕流)
Table 6. Frobenius norm for difference between preconditioner and coefficient matrix (flow around RAE2822 airfoil)
CFL 带宽未经缩减 带宽经过缩减 10 70 63 20 231 155 40 349 645 369 -
[1] 吕宏强, 张涛, 孙强, 等.间断伽辽金法在可压缩流数值模拟中的应用研究综述[J].空气动力学学报, 2016, 35(4):455-471.LYU H Q, ZHANG T, SUN Q, et al.Applications of discontinuous Galerkin method in numerical simulations of compressible flows:A review[J].Acta Aerodynamica Sinica, 2016, 35(4):455-471(in Chinese). [2] COCKBURN B, SHU C W.The Runge-Kutta discontinuous Galerkin method for conservation laws V:Multidimensional systems[J].Journal of Computational Physics, 1997, 141(2):199-224. [3] COCKBURN B, SHU C W.Runge-Kutta discontinuous Galerkin methods for convection-dominated problems[J].Journal of Scientific Computing, 2001, 16(3):173-261. doi: 10.1023/A:1012873910884 [4] FU G S, SHU C W.A new trouble-cell indicator for discontinuous Galerkin methods for hyperbolic conservation laws[J].Journal of Computational Physics, 2017, 347:305-327. doi: 10.1016/j.jcp.2017.06.046 [5] 颜庆津.数值分析[M].4版.北京:北京航空航天大学出版社, 2012:202-203.YAN Q J.Numerical analysis[M].4th ed.Beijing:Beihang University Press, 2012:202-203(in Chinese). [6] KANEVSKY A, CARPENTER M H, GOTTLIEB D, et al.Application of implicit-explicit high order Runge-Kutta methods to discontinuous-Galerkin schemes[J].Journal of Computational Physics, 2007, 225(2):1753-1781. doi: 10.1016/j.jcp.2007.02.021 [7] 郝海兵, 张强, 杨永, 等.基于LU-SGS迭代的DGM隐式方法研究[J].西北工业大学学报, 2014, 32(3):346-350. doi: 10.3969/j.issn.1000-2758.2014.03.003HAO H B, ZHANG Q, YANG Y, et al.An implicit scheme of discontinuous Galerkin method(DGM) based on LU-SGS iterative method[J].Journal of Northwestern Polytechnical University, 2014, 32(3):346-350(in Chinese). doi: 10.3969/j.issn.1000-2758.2014.03.003 [8] BASSI F, BOTTI L, COLOMBO A, et al.Linearly implicit Rosenbrock-type Runge-Kutta schemes applied to the discontinuous Galerkin solution of compressible and incompressible unsteady flows[J].Computers & Fluids, 2015, 118:305-320. http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=7d2a59ec65434f651ce241c13fc795a2 [9] SAAD Y, SCHULTZ M H.GMRES:A generalized minimal residual algorithm for solving nonsymmetric linear systems[J].SIAM Journal on Scientific and Statistical Computing, 1986, 7(3):856-869. doi: 10.1137/0907058 [10] 马昌凤, 柯艺芬, 唐嘉, 等.数值线性代数与算法(MATLAB版)[M].北京:国防工业出版社, 2017:152-176.MA C F, KE Y F, TANG J, et al.Numerical linear algebra and algorithms(MATLAB edition)[M].Beijing:National Defense Industry Press, 2017:162-176(in Chinese). [11] 华伯浩.大型有限元程序系统的网格结点编码优化算法[J].应用数学和力学, 1981, 2(2):207-218. http://www.cnki.com.cn/Article/CJFDTotal-YYSX198102005.htmHUA B H.The network node relabeling optimum algorithms for large finite element program system[J].Applied Mathematics and Mechanics, 1981, 2(2):207-218(in Chinese). http://www.cnki.com.cn/Article/CJFDTotal-YYSX198102005.htm [12] 王家林.有限元模型中自由度层次的带宽优化算法[J].西南交通大学学报, 2009, 44(2):186-189. doi: 10.3969/j.issn.0258-2724.2009.02.008WANG J L.Bandwidth optimization algorithm of finite element models at level of degree of freedom[J].Journal of Southwest Jiaotong University, 2009, 44(2):186-189(in Chinese). doi: 10.3969/j.issn.0258-2724.2009.02.008 [13] LIU W H, SHERMAN A H.Comparative analysis of the Cuthill-Mckee and the reverse Cuthill-Mckee ordering algorithms for sparse matrices[J].SIAM Journal on Numerical Analysis, 1976, 13(2):198-213. doi: 10.1137/0713020 [14] HESTHAVEN J S, WARBURTON T.Nodal discontinuous Galerkin methods:Algorithm, analysis, and applications[M].New York:Springer Science and Business Media, 2008:297-299. [15] QIU J X, KHOO B C, SHU C W.A numerical study for the performance of the Runge-Kutta discontinuous Galerkin method based on different numerical fluxes[J].Journal of Computational Physics, 2006, 212:540-565. doi: 10.1016/j.jcp.2005.07.011 [16] DOLEJSI V, FEISTAUER M.Discontinuous Galerkin method:Analysis and applications to compressible flow[M].Berlin:Springer International Publishing, 2015:423-424, 434-438. [17] BASSI F, REBAY S.High-order accurate discontinuous finite element solution of the 2D Euler equations[J].Journal of Computational Physics, 1997, 138(2):251-285. doi: 10.1006/jcph.1997.5454 [18] KRIVODONOVA L, BERGER M.High-order accurate implementation of solid wall boundary conditions in curved geometries[J].Journal of Computational Physics, 2006, 211(2):492-512. doi: 10.1016/j.jcp.2005.05.029 [19] 王勖成.有限单元法[M].北京:清华大学出版社, 2003:131-132.WANG X C.Finite element method[M].Beijing:Tsinghua University Press, 2003:131-132(in Chinese). [20] DOLEJSI V, FEISTAUER M.A semi-implicit discontinuous Galerkin finite element method for the numerical solution of inviscid compressible flow[J].Journal of Computational Physics, 2004, 198(2):727-746. doi: 10.1016/j.jcp.2004.01.023 [21] 方田.Krylov子空间法及预处理技术在CFD中的应用[D].武汉: 武汉理工大学, 2013: 45-52.FANG T.Krylov sub-space iterative method with preconditioning and its application in numerical simulation for CFD[D].Wuhan: Wuhan University of Technology, 2013: 45-52(in Chinese). [22] BURGESS N K, MARVRIPLIS D J.Robust computation of turbulent flow using discontinuous Galerkin method:AIAA-2012-0457[R].Reston:AIAA, 2012:25-27.