Solving Block Linear Systems with Low-Rank 
Off-Diagonal Blocks Is Easily Parallelizable

Vladimir Menkov
Department of Computer Science
Indiana University at Bllomington

Abstract

An easily and efficiently parallelizable direct method is given for solving a
block linear system $Bx=y$, where $B=D+Q$ is the sum of a non-singular block
diagonal matrix $D$ and a matrix $Q$ with low-rank blocks.  This implicitly
defines a new preconditioning method with an operation count close to the cost
of calculating a matrix-vector product $Qw$ for some $w$, plus at most twice
the cost of calculating $D^{-1}w$ for some $w$.  When implemented on a
parallel machine the processor utilization can be as good as that of those
operations.  Order estimates are given for the general case, and an
implementation is compared to block SSOR preconditioning.