Cyclic Reduction - History and Applications
Walter Gander, Gene Howard Golub · 1997
We discuss the method of Cyclic Reduction for solving special systems of linear equations that arise when discretizing partial differential equations. In connection with parallel computations the method has become very important. 1 Introduction Cyclic Reduction has proved to be an algorithm which is very powerful for solving structured matrix problems. In particular for matrices which are (block) Toeplitz and (block) tri-diagonal, the method is especially useful. The basic idea is to eliminate half the unknowns, regroup the equations and again eliminate half the unknowns. The process is continued ad nauseum. This simple idea is useful in solving the finite difference approximation to Poisson's equation in a rectangle and for solving certain recurrences. The algorithm easily parallelizes and can be used on a large variety of architectures [7]. New uses of Cyclic Reduction continue to be developed -- see, for instance, the recent publication by Amodio and Paprzycki [1]. In this paper, w...