A Tricyclic Tridiagonal Equation Solver
David S. Dodson, Stewart A. Levin · SIAM Journal on Matrix Analysis and Applications · 1992
An improved method for solving tridiagonal equations on CONVEX computers is exhibited. The method employs cyclic reduction by powers of three and has several advantages over conventional power-of-two reduction. The number of divisions per element is cut in half, while the number of multiplications and additions remains almost exactly the same. Memory bank conflicts are minimized because all vector strides are powers of three, i.e., odd. The number of memory accesses is reduced by a quarter. This is especially important for the CONVEX where cyclic reduction is memory limited. Last, the algorithm supports modification in a recently published manner that maximizes the use of full vector register segments throughout the reduction [R. Reuter, Parallel Comput., 8 (1988), pp. 371–376].