6.8 Block Cyclic Reduction

Block cyclic reduction is another fast ( O( N ² log ₂ N)) method for the model problem but is slightly more generally applicable than the FFT-based solution. The fastest algorithms for the model problem on vector computers are often a hybrid of block cyclic reduction and FFT.

First we describe a simple but numerically unstable version version of the algorithm; then we say a little about how to stabilize it. Write the model problem as

where we assume that N, the dimension of A = T _N + 2 I _N, is odd. Note also that x _i and b _i are N-vectors.

We use block Gaussian elimination to combine three consecutive sets of equations,

thus eliminating x _{j ?1} and x _j+1:

Doing this for every set of three consecutive equations yields two sets of equations: one for the x _j with j even,

where B = A ² ? 2 I, and one set of equations for the x _j with j odd, which we can solve after solving equation (6.50) for the odd x _j.

Note that equation (6.50) has the same form as the original problem, so we may repeat this process recursively. For example, at the next step we get

and

We repeat this until only one equation is left, which we solve another way.

We formalize this...