Distributed Southwell: An Iterative Method with Low
Communication Costs
Authors
Event Type
Paper
Communication Avoidance
Graph Algorithms
Linear Algebra
TimeThursday, November 16th11am -
11:30am
Location405-406-407
DescriptionWe present a new algorithm, the Distributed Southwell
method, as a competitor to Block Jacobi for
preconditioning and multigrid smoothing. It is based on
the Southwell iterative method, which is sequential,
where only the equation with the largest residual is
relaxed per iteration. The Parallel Southwell method
extends this idea by relaxing equation i if it has the
largest residual among all the equations coupled to
variable i. Since communication is required for
processes to exchange residuals, this method in
distributed memory can be expensive. Distributed
Southwell uses a novel scheme to reduce this
communication of residuals while avoiding deadlock.
Using test problems from the SuiteSparse Matrix
Collection, we show that Distributed Southwell requires
less communication to reach the same accuracy when
compared to Parallel Southwell. Additionally, we show
that the convergence of Distributed Southwell does not
degrade like that of Block Jacobi when the number of
processes is increased.
Download PDF:
here
