Next: III. SELECTED APPLICATIONS
Up: 5.3 Boundary Value Problems:
Previous: 5.3.3 Fourier Transform Method
5.3.4 Cyclic Reduction (CR)
Again, consider
Let the number of columns in the lattice be , and
define the column vectors
Then,
where
and
are tridiagonal.
Now form linear combinations
:
with
The ``reduced'' equation has the same form as
before, except that only every other vector
appears in it.
Iterate until
Now the vectors
and
are just the given
boundary values and
.
The matrix
is known since it arose from the
-fold iteration of the above combination rule.
While
is not tridiagonal any more,
it may at least be represented by a -fold product of tridiagonal
matrices:
with
Solve for the vector
by
inverting tridiagonal systems of equations.
Now go back to ever more intermediate columns:
compute
and
follow from
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.
``FACR'' method (Fourier analysis
and cyclic reduction):
In place of the column vector
use its Fourier components,
Details: see Hockney 1981, or Vesely 2001.
Next: III. SELECTED APPLICATIONS
Up: 5.3 Boundary Value Problems:
Previous: 5.3.3 Fourier Transform Method
Franz J. Vesely Oct 2005
See also: "Computational Physics - An Introduction," Kluwer-Plenum 2001