Paper Info
Title
Component-Averaged Row Projections: A Robust, Block-Parallel Scheme for Sparse Linear Systems
Abstract
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.
Year
DOI
Venue
2005
10.1137/040609458
SIAM J. Scientific Computing
Keywords
Field
DocType
convergence property,block-parallel scheme,row projections,block-parallel,convergence proof,large sparse linear system,partial differential equations,component-averaging,linear equations,convex feasibility problem,component-averaged row projections,kaczmarz row projection,superspace,linear system,parallel processing,sparse linear systems,domain decom- position,linear speedup ratio,pdes shows,certain component-averaging operation,component-averaged row projection,certain superspace,partial differential equation,domain decomposition,data transfer
Linear system,Iterative method,Row equivalence,Algorithm,Kaczmarz method,Numerical analysis,Numerical linear algebra,Mathematics,Domain decomposition methods,Speedup
Journal
Volume
Issue
ISSN
27
3
1064-8275
Citations 
PageRank 
References 
32
2.60
11
Authors
2
Name
Order
Citations
PageRank
Dan Gordon121021.44
Rachel Gordon218317.97