【摘要】：代数多重网格是基于几何多重网格的一些重要原理和概念提出的一种多重网格方法，不依赖于任何实际几何网格信息。AMG包括两个过程：启动过程和求解过程。求解过程即是在代数网格层次结构之上，执行标准的多重网格循环，如V-cycle、W-cycle等。AMG采用相对简单的光滑算子，例如采用固定次数的Jacobi或Gauss-Seidel迭代，以消除高频误差。算法42描述了AMG中几个重要运算符的构造。这些稀疏矩阵乘的时间开销超过了总构造时间的80%，是AMG算法时间开销最大的组成部分。
代数多重网格（algebra multigrid， AMG）是基于几何多重网格（geometric multigrid，GMG）的一些重要原理和概念提出的一种多重网格方法，不依赖于任何实际几何网格信息。AMG包括两个过程：启动过程（setup）和求解过程（solve）。其中，启动过程基于稀疏矩阵信息，构造多重网格算法组件，包括粗网格矩阵、插值算子和限制算子等，从而形成带属性的网格层次结构。求解过程即是在代数网格层次结构之上，执行标准的多重网格循环，如V-cycle、W-cycle等。它的一个基本原理是光滑过程与粗网格校正过程的互补。对于各种多重网格算法，光滑与网格粗化是两个非常关键的组件。AMG采用相对简单的光滑算子，例如采用固定次数的Jacobi或Gauss-Seidel迭代，以消除高频误差。粗网格校正涉及三个阶段，包括通过限制算子将误差投影到较粗的网格，求解粗网格对应的方程组，然后通过插值算子将解投影回细网格。
算法4−2描述了AMG中几个重要运算符的构造。首先，通过strength函数得到第l层中矩阵Al中的强连通边，从而构造出强连接矩阵Sl（算法4−2的第3行）。然后，构造插值运算符P以将信息从第l + 1层传输到第l层（算法4−2的第4行）。最后，通过Galerkin乘积（算法4−2的第5行）构造粗网格算子，该乘积由两个稀疏矩阵组成。(www.xing528.com)
这些稀疏矩阵乘的时间开销超过了总构造时间的80%，是AMG算法时间开销最大的组成部分。而且，运算符的构造（即SpGEMM计算）是整个执行过程的重要组成部分，因此针对SpGEMM的优化尤为关键。
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
