Displacement structure approach to discrete-trigonometric-transform based preconditioners of G.Strang type and of T.Chan type
Displacement structure approach to discrete-trigonometric-transform based preconditioners of G.Strang type and of T.Chan type
复制标题
DOI：
10.1137/s0895479896312560
复制
发表时间：
1996-09
期刊：
影响因子：
1.7
通讯作者：
T. Kailath;V. Olshevsky
中科院分区：
文献类型：
--
作者：
T. Kailath;V. Olshevsky
本文利用位移结构技术设计了一类新的预条件子，用于求解大型Toeplitz线性方程组的共轭梯度法。本文给出了G. Strang型预条件子和T. Chan型预条件子的显式公式，它们属于由离散余弦或正弦变换对角化的8类矩阵中的任何一类。在标准的Wiener类假设下，对所有预条件子建立了聚类性质，保证了预条件共轭梯度法的快速收敛性. G. Strang型预条件子的公式有另一个重要的应用：它们提出了各种各样的新的O（m logm）算法，用于Toeplitz矩阵乘以向量，基于任何8个DCT和DST。近年来，Toeplitz矩阵到Vandermonde-like或Cauchy-like矩阵的变换在发展求解Toeplitz线性方程组的精确直接方法中被发现是有用的。在这里，建议进一步扩展的范围内的变换方法，探索它foriterative方法，这种技术使我们能够减少预处理共轭梯度法的每次迭代的复杂性，每次迭代4离散变换。
In this paper adisplacement structure technique is used to design a class of newpreconditioners for theconjugate gradient method applied to the solution of large Toeplitz linear equations. Explicit formulas are suggested for the G.Strang-type and for the T.Chan-type preconditioners belonging to any of 8 classes of matrices diagonalized by the correspondingdiscrete cosine or sine transforms. Under the standard Wiener class assumption theclustering property is established for all of these preconditioners, guaranteeing a rapid convergence of the preconditioned conjugate gradient method. The formulas for the G.Strang-type preconditioners have another important application: they suggest a wide variety of newO(m logm) algorithms for multiplication of a Toeplitz matrix by a vector, based on any of the 8 DCT’s and DST’s. Recentlytransformations of Toeplitz matrices to Vandermonde-like or Cauchy-like matrices have been found to be useful in developing accuratedirect methods for Toeplitz linear equations. Here it is suggested to further extend the range of the transformation approach by exploring it foriterative methods; this technique allowed us to reduce the complexity of each iteration of the preconditioned conjugate gradient method to 4 discrete transforms per iteration.