• 论文 •

### 一类Toeplitz线性代数方程组的预处理GMRES方法

1. 南京航空航天大学数学系, 飞行器数学建模与高性能计算工业和信息化部重点实验室(南京航空航天大学), 南京 211106
• 收稿日期:2019-07-17 发布日期:2021-05-13
• 通讯作者: 刘皞,hliu@nuaa.edu.cn.
• 基金资助:
国家自然科学基金（11401305，11571171）和南京航空航天大学研究生创新基地（实验室）开放基金（kfjj20180801）资助.

He Ying, Liu Hao. PRECONDITIONED GMRES METHOD FOR A CLASS OF TOEPLITZ LINEAR SYSTEMS[J]. Mathematica Numerica Sinica, 2021, 43(2): 177-191.

### PRECONDITIONED GMRES METHOD FOR A CLASS OF TOEPLITZ LINEAR SYSTEMS

He Ying, Liu Hao

1. Department of Mathematics, Nanjing University of Aeronautics and Astronautics, Key Laboratory of Mathematical Modelling and High Performance Computing of Air Vehicles(NUAA), MIIT, Nanjing 211106, China
• Received:2019-07-17 Published:2021-05-13

In this paper, we consider the solution of a class of Toeplitz linear systems derived from the fractional eigenvalue problems. We construct the Strang circulant matrix as a preconditioner to solve this Toeplitz linear systems, and analyze the properties of eigenvalues of the preconditioned coefficient matrix. We also propose the preconditioned generalized minimal residuals method (PGMRES) for solving this linear systems, and give the computational costs of this algorithm. The numerical examples show the effecticiency of our method.

MR(2010)主题分类:

()
 [1] Reutskiy S Y. A novel method for solving second order fractional eigenvalue problems[J]. Journal of Computational and Applied Mathematics, 2016, 306:133-153.[2] Herrmann R. Fractional calculus:an introduction for physicists[J]. World Scientific, 2014, 152(6):846-850.[3] Lubich. Discretized fractional calculus[J]. SIAM Journal on Mathematical Analysis, 1986, 17(3):704-716.[4] Zhao X, Sun Z Z. A box-type scheme for fractional sub-diffusion equation with Neumann boundary conditions[J]. Journal of Computational Physics, 2011, 230(15):6061-6074.[5] Ding H, Li C, Chen Y Q. High-order algorithms for Riesz derivative and their applications (II)[J]. Journal of Computational Physics, 2015, 293:218-237.[6] Zhu Y, Sun Z Z. A high-order difference scheme for the space and time fractional Bloch-Torrey equation[J]. Computational Methods in Applied Mathematics, 2017, 18(1):356-380.[7] Lei S L, Sun H W. A circulant preconditioner for fractional diffusion equations[J]. Journal of Computational Physics, 2013, 242:715-725.[8] Bai Z Z, Lu K Y, Pan J Y. Diagonal and Toeplitz splitting iteration methods for diagonal-plusToeplitz linear systems from spatial fractional diffusion equations[J]. Numerical Linear Algebra with Applications, 2017:2093.[9] Tian W, Zhou H, Deng W. A class of second order difference approximations for solving space fractional diffusion equations[J]. Mathematics of Computation, 2015, 84(294):1703-1727.[10] Sun Z Z, Wu X. A fully discrete difference scheme for a diffusion-wave system[J]. Applied Numerical Mathematics, 2006, 56(2):193-209.[11] Yang Q, Liu F, Turner I. Numerical methods for fractional partial differential equations with Riesz space fractional derivatives[J]. Applied Mathematical Modelling, 2010, 34(1):200-218.[12] Celik C, Duman M. Crank-Nicolson method for the fractional diffusion equation with the Riesz fractional derivative[J]. Journal of Computational Physics, 2012, 231(4):1743-1750.[13] Ching W K. Iterative Methods for Queuing and Manufacturing Systems[M]. Springer, 2001.[14] Levinson N. The wiener (root mean square) error criterion in filter design and prediction[J]. Journal of Mathematics and Physics, 1946, 25(2):261-278.[15] Bitmead R R, Anderson B D O. Asymptotically fast solution of Toeplitz and related systems of linear equations[J]. Linear Algebra and its Applications, 1980, 34:103-116.[16] Brent R P, Gustavson F G, Yun D. Fast solution of Toeplitz systems of equations and computation of Padé approximants[J]. Journal of Algorithms, 1980, 1(3):259-295.[17] Gustavson F G, Yun D. Fast algorithms for rational Hermite approximation and solution of Toeplitz systems[J]. IEEE Transactions on Circuits and Systems, 1979, 26(9):750-755.[18] Zohar, Shalhav. The solution of a Toeplitz set of linear equations[J]. Journal of the ACM, 1974, 21(2):272-276.[19] Ammar G S, Gragg B, Mn M. Superfast solution of real positive definite Toeplitz systems[J]. SIAM Journal on Matrix Analysis and Applications, 2006, 9(1):61-76.[20] Bunch J R. Stability of methods for solving Toeplitz systems of equations[J]. SIAM Journal on Scientific and Statistical Computing, 1985, 6(2):349-364.[21] Ng M K. Circulant and skew-circulant splitting methods for Toeplitz systems[J]. Journal of Computational and Applied Mathematics, 2003, 159(1):101-108.[22] Akhondi N, Toutounian F. Accelerated circulant and skew circulant splitting methods for Hermitian positive definite Toeplitz systems[J]. Advances in Numerical Analysis, 2012, 2012:1-17.[23] Gu C, Tian Z. On the HSS iteration methods for positive definite Toeplitz linear systems[J]. Journal of Computational and Applied Mathematics, 2009, 224(2):709-718.[24] Ng M K. Iterative Methods for Toeplitz Systems[M]. Oxford Science Publications, 2004.[25] Serra S. A practical algorithm to design fast and optimal band-Toeplitz preconditioners for Hermitian Toeplitz systems[J]. Calcolo, 1996, 33(3-4):209-221.[26] Chen J, Li T L H, Anitescu M. A parallel linear solver for multilevel Toeplitz systems with possibly several right-hand sides[J]. Parallel Computing, 2014, 40(8):408-424.[27] 徐仲, 张凯院, 陆全. Toeplitz矩阵类的快速算法[M]. 西安:西北工业大学出版社, 1999.[28] Chan R H, Ng K P. Toeplitz preconditioners for Hermitian Toeplitz systems[J]. Linear Algebra and its Applications, 1993, 190(2):181-208.[29] Chan R H. Fast band-Toeplitz preconditioners for Hermitian Toeplitz systems[J]. SIAM Journal on Scientific Computing, 2001, 15(1):164-171.[30] Tyrtyshnikov E E. Optimal and Superoptimal Circulant Preconditioners[J]. SIAM Journal on Matrix Analysis and Applications, 1992, 13(2):459-473.[31] Olkin J A. Linear and Nonlinear Deconvolution Problems[M]. PhD thesis, Rice University, Houston, 1986.[32] Chan R H, Yeung C M C. Circulant preconditioners constructed from kernels[J]. SIAM Journal on Numerical Analysis, 1992, 29(4):1093-1103.[33] Strang G. A proposal for Toeplitz matrix calculations[J]. Studies in Applied Mathematics, 1986, 74(3):171-176.[34] Chan R H, Ng M K, Jin X Q. Strang-type preconditioners for systems of LMF-based ODE codes[J]. IMA Journal of Numerical Analysis, 2001, 21(2):451-462.[35] Jin X Q. Preconditioning Techniques for Toeplitz Systems[M].高等教育出版社,2010.[36] Geller D, Kra I, Popescu S, et al. On circulant matrices[J]. Notices of the American Mathematical Society, 2004, 59(3):368-377.[37] 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.[38] Golub G H, Van Loan C F. Matrix Computations[M]. 4th Edition, The Johns Hopkins University Press, Baltimore, 2013.
 [1] 曹阳, 陈莹婷. 正则化HSS预处理鞍点矩阵的特征值估计[J]. 计算数学, 2020, 42(1): 51-62. [2] 王丽, 罗玉花, 王广彬. 求解加权线性最小二乘问题的一类预处理GAOR方法[J]. 计算数学, 2020, 42(1): 63-79. [3] 戴平凡, 李继成, 白建超. 解线性互补问题的预处理加速模Gauss-Seidel迭代方法[J]. 计算数学, 2019, 41(3): 308-319. [4] 刘忠祥, 王翠薇, 王增琦. 求解时谐涡流模型鞍点问题的分块交替分裂隐式迭代算法的改进[J]. 计算数学, 2018, 40(3): 271-286. [5] 郑华, 罗静. 一类H矩阵线性互补问题的预处理二步模基矩阵分裂迭代方法[J]. 计算数学, 2018, 40(1): 24-32. [6] 骆其伦, 黎稳. 二维Helmholtz方程的联合紧致差分离散方程组的预处理方法[J]. 计算数学, 2017, 39(4): 407-420. [7] 曹阳, 陶怀仁, 蒋美群. 鞍点问题的广义位移分裂预条件子[J]. 计算数学, 2014, 36(1): 16-26. [8] 任志茹. 三阶线性常微分方程Sinc方程组的结构预处理方法[J]. 计算数学, 2013, 35(3): 305-322. [9] 王倩, 戴华. 求解离散不适定问题的正则化GMERR方法[J]. 计算数学, 2013, 35(2): 195-204. [10] 曹阳, 谈为伟, 蒋美群. 广义鞍点问题的松弛维数分解预条件子[J]. 计算数学, 2012, 34(4): 351-360. [11] 豆铨煜, 殷俊锋. 一类求解鞍点问题的广义不精确Uzawa方法[J]. 计算数学, 2012, 34(1): 37-48. [12] 全忠,向淑晃,. 基于GMRES的多项式预处理广义极小残差法[J]. 计算数学, 2006, 28(4): 365-376. [13] 安恒斌,白中治. NGLM:一类全局收敛的Newton-GMRES方法[J]. 计算数学, 2005, 27(2): 151-174. [14] 张振跃,王靖,方敏,应文隆. 嵌套简单ILU分解代数预处理方法[J]. 计算数学, 2004, 26(2): 193-210. [15] 白中治,仇寿霞. 关于具优势对称部分的不定线性代数方程组的分裂极小残量算法[J]. 计算数学, 2002, 24(1): 113-128.