Component-averaged row projections: A robust, block-parallel scheme for sparse linear systems
Component-averaged row projections: A robust, block-parallel scheme for sparse linear systems
复制标题
DOI：
10.1137/040609458
复制
发表时间：
2005-01-01
影响因子：
3.1
通讯作者：
Gordon, R
中科院分区：
文献类型：
--
作者：
Gordon, D;Gordon, R
提出了一种并行求解大型稀疏线性方程组的新方法。它通过将方程分成块并以块并行迭代模式操作来进行;即，所有的块被并行处理，并且部分结果被“合并”以形成下一个块。新方案在块内执行Kaczmarz行投影，并通过某些分量平均操作合并结果，因此它被称为分量平均行投影，或CARP。系统矩阵可以是一般的、非对称的和病态的，并且划分成块是不受限制的。对于偏微分方程（PDE），如果块是基于域的，则仅对域之间边界处的变量进行平均，从而最小化处理器之间的数据传输。CARP非常健壮;它的应用程序的线性系统的测试情况下，从偏微分方程表明，它收敛于困难的情况下，国家的最先进的方法失败。它也是非常高效的内存，并表现出几乎线性的加速比，在某些情况下效率大于1。给出了收敛性的形式证明：证明了在一定的超空间中，分量平均运算等价于行投影，因此CARP算法的收敛性与Kaczmarz算法的收敛性是一致的。CARP及其收敛性证明也适用于一致凸可行性问题。
A new method for the parallel solution of large sparse linear systems is introduced. It proceeds by dividing the equations into blocks and operating in block-parallel iterative mode; i.e., all the blocks are processed in parallel, and the partial results are "merged" to form the next iterate. The new scheme performs Kaczmarz row projections within the blocks and merges the results by certain component-averaging operations-hence it is called component-averaged row projections, or CARP. The system matrix can be general, nonsymmetric, and ill-conditioned, and the division into blocks is unrestricted. For partial differential equations (PDEs), if the blocks are domain-based, then only variables at the boundaries between domains are averaged, thereby minimizing data transfer between processors. CARP is very robust; its application to test cases of linear systems derived from PDEs shows that it converges in difficult cases where state-of-the-art methods fail. It is also very memory efficient and exhibits an almost linear speedup ratio, with efficiency greater than unity in some cases. A formal proof of convergence is presented: It is shown that the component- averaging operations are equivalent to row projections in a certain superspace, so the convergence properties of CARP are identical to those of Kaczmarz's algorithm in the superspace. CARP and its convergence proof also apply to the consistent convex feasibility problem.