A Parallel and Vector Variant of the Cyclic Reduction Algorithm
Roland A. Sweet · SIAM Journal on Scientific and Statistical Computing · 1988
The Buneman variant of the block cyclic reduction algorithm begins as a highly parallel algorithm, but collapses with each reduction to a very serial one. Using partial fraction expansions of rational matrix functions, it is shown how to regain the parallelism. The resulting algorithm using $n^2 $ processors runs in $O(\log ^2 n)$ time.