5.3.4 Cyclic Reduction (CR)

Again, consider

$$u_{k+1,l}-2u_{k,l}+ u_{k-1,l} +u_{k,l+1}-2u_{k,l}+u_{k,l-1} = - \rho_{k,l} (\Delta l)^{2}$$

Let the number of columns in the lattice be $M=2^{p}$, and define the column vectors

$$\mbox{$\bf u$}_{k} \equiv \{ u_{k,l} \, ; \; l=0, \dots N-1 \}^{T} \,;\;\;\;k=0,\dots,M-1$$

Then,

$$\mbox{$\bf u$}_{k-1} + \mbox{${\bf T}$} \cdot \mbox{$\bf u$}_{k} + \mbox{$\bf u$}_{k+1} = - \mbox{$\bf\rho$}_{k} (\Delta l)^{2}$$

where

$$\mbox{${\bf T}$} \equiv \left( \begin{array}{ccccc} -2 & 1 & 0 & \dots & \\ 1 &-2 & 1 & ... ...& 0 & \dots & \\ 0 &2 & 0 & & \\ &\ddots &\ddots &\ddots & \end{array}\right)$$

$$= \hspace{4.5em} \mbox{${\bf B}$} \hspace{5em} - \hspace{4em} 2 \,\mbox{${\bf I}$}$$

$\mbox{${\bf B}$}$ and $\mbox{${\bf T}$}$ are tridiagonal.
Now form linear combinations $[k-1]-\mbox{${\bf T}$} \cdot [k] + [k+1]$:

$$\mbox{$\bf u$}_{k-2} + \mbox{${\bf T}$}^{(1)} \cdot \mbox{$\... ...$\bf u$}_{k+2} = - \mbox{$\bf\rho$}_{k}^{(1)} (\Delta l)^{2}$$

with

$$\mbox{${\bf T}$}^{(1)} \equiv 2 \mbox{${\bf I}$} - \mbox{${\bf T}$}^{2}$$

$$\mbox{$\bf\rho$}_{k}^{(1)} \equiv \mbox{$\bf\rho$}_{k-1} - \mbox{${\bf T}$} \cdot \mbox{$\bf\rho$}_{k} +\mbox{$\bf\rho$}_{k+1}$$

The ``reduced'' equation has the same form as before, except that only every other vector $\mbox{$\bf u$}_{k}$ appears in it.
$\Longrightarrow$Iterate until

$$\mbox{$\bf u$}_{0} + \mbox{${\bf T}$}^{(p)} \cdot \mbox{$\bf... ...$\bf u$}_{M} = - \mbox{$\bf\rho$}_{M/2}^{(p)} (\Delta l)^{2}$$

Now the vectors $\mbox{$\bf u$}_{0}$ and $\mbox{$\bf u$}_{M}$ are just the given boundary values $u_{0,l}$ and $u_{M,l}\,$ $(l=0,1, \dots N-1)$. The matrix $\mbox{${\bf T}$}^{(p)}$ is known since it arose from the $p\,$-fold iteration of the above combination rule. While $\mbox{${\bf T}$}^{(p)}$ is not tridiagonal any more, it may at least be represented by a $2^{p}$-fold product of tridiagonal matrices:

$$\mbox{${\bf T}$}^{(p)}=-\prod_{l=1}^{2^{p}} \left[ \mbox{${\bf T}$}-\beta_{l}\mbox{${\bf I}$} \right]$$

with

$$\beta_{l}= 2 \cos\left[ \frac{2(l-1)\pi}{2^{p+1}}\right]$$

$\Longrightarrow$Solve for the vector $\mbox{$\bf u$}_{M/2}$ by inverting $2^{p}$ tridiagonal systems of equations.

Now go back to ever more intermediate columns: compute $\mbox{$\bf u$}_{M/4}$ and $\mbox{$\bf u$}_{3M/4}$ follow from

$$\mbox{$\bf u$}_{0} + \mbox{${\bf T}$}^{(p-1)} \cdot \mbox{$\bf u$}_{M/4} + \mbox{$\bf u$}_{M/2} = - \mbox{$\bf\rho$}_{M/4}^{(p-1)} (\Delta l)^{2}$$

$$\mbox{$\bf u$}_{M/2} + \mbox{${\bf T}$}^{(p-1)} \cdot \mbox{$\bf u$}_{3M/4} + \mbox{$\bf u$}_{M} = - \mbox{$\bf\rho$}_{3M/4}^{p-1} (\Delta l)^{2}$$

and so on.

Lit. HOCKNEY: Combination of the CR technique and the Fourier transform method is superior to most other techniques for solving the potential equation. $\Longrightarrow$``FACR'' method (Fourier analysis and cyclic reduction): In place of the column vector $\mbox{$\bf u$}_{k} \equiv \{ u_{k,l};\,l=0, \dots N-1\}^{T}$ use its $N$ Fourier components,

$$U_{k}(n) \equiv \sum_{l=0}^{N-1} u_{k,l} e^{2\pi i \, nl/N} \, ; \;\;(n=0, \dots N-1) \nonumber$$

Details: see Hockney 1981, or Vesely 2001.