Multi-scale linear solvers for very large systems derived from PDEs
Klaus Lackner and Ralph Menikoff
我们提出了一种新的线性求解器,适用于从离散PDE中获得的大型系统。 它是健壮的,对于我们研究的例子,计算工作与方程的数量线性扩展。 该算法基于将共轭梯度,多缩放和迭代分裂方法结合到单一方法的波长分解。 从表面上看,该算法是一个简单的预置共轭梯度,具有算法在选择预后矩阵时的所有复杂程度。 预后器是线性运算符的一个很好的近似反。 它由粗粒线运算符的反向构造,以及基于细网格上的运算符的平滑运算符。 粗粒度捕获逆运算符的长波长行为,而平滑运算符捕获短波长行为。 共轭梯度迭代解释了长波长和短波长之间的耦合。 粗粒度运算符对应于PDE的较低分辨率近似值。 虽然粗粒反向不显式地知道,但该算法只要求预前提条件器可以应用于向量。 应用于向量粗的反向可以作为另一个条件的共轭梯度求解器的求解器的求解求解器获得,该求解器将相同的算法应用于较小的问题。 因此,该方法自然是递归的。 当矩阵足够小,以便使用标准求解器有效地获得解决方案时,递归结束。 我们已经在多孔流方程上测试了我们的求解器。 在工作站上,我们解决了从10^3到10^6的网格问题,发现线性缩放保持不变。
We present a novel linear solver that works well for large systems obtained from discretizing PDEs. It is robust and, for the examples we studied, the computational effort scales linearly with the number of equations. The algorithm is based on a wavelength decomposition that combines conjugate gradient, multi-scaling and iterative splitting methods into a single approach. On the surface, the algorithm is a simple preconditioned conjugate gradient with all the sophistication of the algorithm in t...