.png){kind=icon}
.png){kind=icon}
Return
Component-averaged row projections: A robust, block-parallel scheme for sparse linear systems
.png){kind=icon}
OA
AI
DOI：10.1137/040609458.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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.
Keywords:
block-parallel
component-averaging
convex feasibility problem
domain decomposition
linear equations
parallel processing
partial differential equations
row projections
sparse linear systems
superspace
Journal
IF:
2.6
Papers:
5.1K
Citations:
1.8W
Organization
No organization information available