Mathematical Sciences: Preconditioning by Fast Transforms

数学科学：通过快速变换进行预处理

• 批准号: 8703313
• 负责人: Gilbert Strang
• 金额: $ 18万
• 依托单位: Massachusetts Institute of Technology
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1987
• 资助国家: 美国
• 起止时间: 1987-06-01 至 1990-11-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=8703313&HistoricalAwards=false
• 关键词: Mathematical; Sciences; Preconditioning; Fast; Transforms

The analytical problem in this proposal is the relation between a given operator and its preconditioner. Given is a differential or integral or convolution operator with general boundary conditions. The preconditioner has particularly convenient domain and boundary conditions. After discretization it can be inverted by the Fast Fourier Transform, or in the case of the Dirichlet problem by a Fast Sine Transform. In the matrix case one applies the preconditioned conjugate gradient method and the distribution of the eigenvalues is crucial. A small number of extreme eigenvalues is acceptable if all other eigenvalues are clustered - that is what appeared in numerical experiments. The conjecture on clustering depends on establishing that the eigenvectors decay exponentially, away from the boundary. The analysis should connect problems in operator theory to problems in numerical analysis, and may give a new direction in the class of equations for which preconditioning is essential. This research falls into the general area of numerical analysis, numerical computing, computational mathematics and software design. The problem of Toeplitz operators is important in signal processing. The problem of numerical computations associated with Toeplitz matrices arises in many problems of communications engineering and its solution is of considerable importance.

该提案中的分析问题是给定算子与其预处理器之间的关系。 给定的是具有一般边界条件的微分或积分或卷积算子。 预处理器具有特别方便的域和边界条件。离散化后，可以通过快速傅里叶变换对其进行反转，或者在狄利克雷问题的情况下通过快速正弦变换进行反转。 在矩阵情况下，应用预条件共轭梯度法，特征值的分布至关重要。 如果所有其他特征值都聚集在一起，那么少量的极端特征值是可以接受的——这就是数值实验中出现的情况。 关于聚类的猜想取决于确定特征向量远离边界呈指数衰减。 该分析应将算子理论中的问题与数值分析中的问题联系起来，并可能为预处理至关重要的方程组提供新的方向。 这项研究属于数值分析、数值计算、计算数学和软件设计的一般领域。托普利茨算子问题在信号处理中很重要。 与Toeplitz矩阵相关的数值计算问题出现在通信工程的许多问题中，其解决具有相当重要的意义。