Base-\(p\)-cyclic reduction for tridiagonal systems of equations (Q1181506)

Cycling reduction or recursive doubling are known as well-vectorizable algorithms for solving systems of linear equations with weakly diagonally dominant tridiagonal matrices. However, on banked-memory machines, where the number of memory banks is a power of 2, it is necessary to develop some techniques in order to avoid memory bank conflicts and to speed up the algorithm. The author studies versions of the cyclic reduction algorithm, where the size of the system is reduced by eliminating \(p-1\) out of \(p\) equations for some odd \(p\), and/or the elements of the reduced matrix are moved to free contiguous locations in each reduction step. The performances of both approaches (and their combination) on CRAY X-MP and NEC SX-2 machines are presented.