Wrap-around partitioning for block bidiagonal linear systems
Markus Hegland · IMA Journal of Numerical Analysis · 1998
A stable vector algorithm for the solution of block diagonal linear systems is obtained by a permutation of the unknowns called wrap-around partitioning combined with standard QR factorization. Wrap-around partitioning uses blocking and selects the unknowns in the blocks in turns. After a suitable orthogonal elimination step one ends up with a reduced system which is again block bidiagonal and so wrap-around partitioning can be applied again. Using a simple model for vectorization overhead it is shown that small block sizes give best performance. The minimal block size 2, which corresponds to cyclic reduction, is suboptimal due to memory bank conflicts.