Hermitian Toeplitz线性方程组的新预处理方法

数学理论与应用 ›› 2018, Vol. 38 ›› Issue (3-4): 50-58.

Hermitian Toeplitz线性方程组的新预处理方法

刘仲云¹ ，徐伟进¹ ，陈思恒¹ ，张育林²

1.长沙理工大学数学与统计学院
2.Minho大学数学中心葡萄牙

出版日期:2018-12-30 发布日期:2020-09-21
基金资助:
国家自然科学基金资助项目(11371075)

A New Preconditioning Technique for Hermitian Toeplitz Systems

Online:2018-12-30 Published:2020-09-21

摘要/Abstract

摘要： 本文研究解 HermitianToeplitz线性方程组 Ax=b 的预处理共轭梯度法.基于Hermitian Toeplitz矩阵可通过酉相似转化为一个实 Toeplitz矩阵与一个 Hankel矩阵的和(UAU* =T+H)的结论,我们首先将 Ax=b 转化为实线性方程组(T+H)[x1,x2]=[b1,b2].然后,我们提出一个新预处理子来求解这两个方程组.特别地,我们采用 DCT 和 DST 求解,只涉及到实运算.我们分析预处理矩阵的谱性质,并讨论每步迭代的计算复杂度.数值实验表明该预处理子是有效的.

关键词: HermitianToeplitz矩阵, 预处理共轭梯度方法, DST, DCT

Abstract: In this paper we give a preconditioned conjugate gradient method(PCG)to solve the Hermitian To-eplitz system Ax=b.Based on the fact that an Hermitian Toeplitz matrix Acan be reduced into a real Toeplitzmatrix plus a Hankel matrix(i.e.,UAU*=T+H)by a unitary similarity transformation(this unitary matrix is U=(I-iJ)/ √2),we first reduce the system Ax=b to a real linear systems(T+H)[x1,x2]=[b1,b2]. Then we propose a new preconditioner for solving those two systems.In particular,our solver only involveseal arithmetics when the discrete sine transform(DST)and discrete cosine transform(DCT)are used.The spectral properties of the preconditioned matrix are analyzed,and the computational complexity is discussed. Numerical experiments show that our preconditioner performs well for solving the Hermitian Toeplitz systems.

Key words: Hermitian Toeplitz matrix , PCG, DST, DCT

刘仲云, 徐伟进, 陈思恒, 张育林, . Hermitian Toeplitz线性方程组的新预处理方法[J]. 数学理论与应用, 2018, 38(3-4): 50-58.

Liu Zhongyun, Xu Weijin, Chen Siheng, Zhang Yulin. A New Preconditioning Technique for Hermitian Toeplitz Systems[J]. Mathematical Theory and Applications, 2018, 38(3-4): 50-58.

[1]	刘仲云, 陈思恒, 徐伟进, 张育林. Hermitian Toeplitz矩阵向量乘积的快速算法[J]. 数学理论与应用, 2017, 37(3-4): 38-42.
[2]	刘仲云, 吴念慈 , 秦小蓉 , 张育林. 实对称正定Toeplitz矩阵的带位移的Sine预处理子[J]. 数学理论与应用, 2017, 37(1): 1-6.