Preliminary Remarks on Multigrid Methods for Circulant Matrices


获取原文并翻译 | 示例


In this note we propose a multigrid approach to the solution of (multilevel) banded circulant linear system. In particular, we discuss how to define a "coarse-grid projector" such that the projected matrix at lower dimension preserves the circulant structure. This approach naturally leads to an optimal algorithm having linear cost as the size N of the system and so improving the the classical one based on Fast Fourier Transforms (FFTs) that costs O(N log N) arithmetic operations (ops). It's worth mentioning that these banded circulants are used as preconditioners for elliptic and parabolic PDEs (with Dirichlet or periodic boundary conditions) and for some 2D image restoration problems where the point spread function (PSF) is numerically banded. Therefore the use of the proposed multigrid technique reduces the overall cost from O(k(ε,n)N log N) to O(k(ε,n)N), where k(ε, n) is the number of Preconditioned Conjugate Gradient (PCG) iterations to reach the solution within a given accuracy of ε. The full analysis of convergence and the related numerical experiments are reported in a forthcoming paper.
机译:在本说明中,我们提出了一种多网格方法来求解(多级)带状循环线性系统。特别是,我们讨论了如何定义“粗网格投影仪”,以使较低尺寸的投影矩阵保留循环结构。这种方法自然会导致一种最优算法,其线性代价为系统的大小N,因此基于快速傅立叶变换(FFT)改进了经典算法,而这种算法花费了O(N log N)个算术运算(ops)。值得一提的是,这些带状环行体用作椭圆形和抛物线形PDE(具有Dirichlet或周期性边界条件)和点扩展函数(PSF)在数字上带状的一些2D图像恢复问题的预处理器。因此,使用建议的多重网格技术可将总成本从O(k(ε,n)N log N)降低到O(k(ε,n)N),其中k(ε,n)是预处理共轭数梯度(PCG)迭代以在给定的ε精度内达到解。即将发表的论文中对收敛性进行了全面分析,并进行了相关的数值实验。



  • 外文文献
  • 中文文献
  • 专利
  • 写作辅导
  • 期刊发表


京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号