96
5. Solution of Linear Equation Systems
5.2.4 Cyclic Reduction
There are cases even more special that allow still greater cost reduction than
that offered by TDMA. An interesting example is provided by systems in
which the matrix is not only tridiagonal but all of the elements on each
diagonal are identical. The cyclic reduction method can be used to solve
such systems with a cost per variable that actually decreases as the system
becomes larger. Let us see how that is possible.
Suppose that, in the system (5.9), the coefficients A h , A b and Ab are
independent of the index i; we may then drop the index. Then, for even
values of i, we multiply row i - 1 by Aw/Ap and subtract it from row i.
Then we multiply row i + 1 by AE/Ap and subtract it from row i. This
eliminates the elements to the immediate left and right of the main diagonal
in the even numbered rows but replaces the zero element two columns to the
left of the main diagonal by -Ah/AP and the zero element two columns to
the right of the main diagonal by -Ai/Ap; the diagonal element becomes
Ap - 2AwAE/AP. Because the elements in every even row are the same, the
calculation of the new elements needs to be done only once; this is where the
savings come from.
At the completion of these operations the even numbered equations contain only even indexed variables and constitute a set of n/2 equations for
these variables; considered as a separate system, these equations are tridiagonal and the elements on each diagonal of the reduced matrix are again
equal. In other words, the reduced set of equations has the same form as the
original one but is half the size. It can be further reduced in the same way. If
the number of equations in the original set is a power of two (or certain other
convenient numbers), the method can be continued until only one equation
remains; the latter is solved directly. The remaining variables can then be
found by a variant of back substitution.
One can show that the cost of this method is proportional to log, n, so that
the cost per variable decreases with the number of variables. Although the
method may seem rather specialized, there are CFD applications in which it
plays a role. These are flows in very regular geometries such as the rectangular
boxes which are used, for example, in direct or large eddy simulations of
turbulence and in some meteorological applications.
In these applications, cyclic reduction and related methods provide the
basis for methods of solving elliptic equations such as Laplace and Poisson
equations directly, that is, non-iteratively. Since the solutions are also exact
in the sense that they contain no iteration error, this method is invaluable
whenever it can be used.
Cyclic reduction is closely related to the fast Fourier transform which is
also used to solve elliptic equations in simple geometries. Fourier methods
may also be used for evaluating derivatives, as was shown in Sect. 3.10.
5. Solution of Linear Equation Systems
5.2.4 Cyclic Reduction
There are cases even more special that allow still greater cost reduction than
that offered by TDMA. An interesting example is provided by systems in
which the matrix is not only tridiagonal but all of the elements on each
diagonal are identical. The cyclic reduction method can be used to solve
such systems with a cost per variable that actually decreases as the system
becomes larger. Let us see how that is possible.
Suppose that, in the system (5.9), the coefficients A h , A b and Ab are
independent of the index i; we may then drop the index. Then, for even
values of i, we multiply row i - 1 by Aw/Ap and subtract it from row i.
Then we multiply row i + 1 by AE/Ap and subtract it from row i. This
eliminates the elements to the immediate left and right of the main diagonal
in the even numbered rows but replaces the zero element two columns to the
left of the main diagonal by -Ah/AP and the zero element two columns to
the right of the main diagonal by -Ai/Ap; the diagonal element becomes
Ap - 2AwAE/AP. Because the elements in every even row are the same, the
calculation of the new elements needs to be done only once; this is where the
savings come from.
At the completion of these operations the even numbered equations contain only even indexed variables and constitute a set of n/2 equations for
these variables; considered as a separate system, these equations are tridiagonal and the elements on each diagonal of the reduced matrix are again
equal. In other words, the reduced set of equations has the same form as the
original one but is half the size. It can be further reduced in the same way. If
the number of equations in the original set is a power of two (or certain other
convenient numbers), the method can be continued until only one equation
remains; the latter is solved directly. The remaining variables can then be
found by a variant of back substitution.
One can show that the cost of this method is proportional to log, n, so that
the cost per variable decreases with the number of variables. Although the
method may seem rather specialized, there are CFD applications in which it
plays a role. These are flows in very regular geometries such as the rectangular
boxes which are used, for example, in direct or large eddy simulations of
turbulence and in some meteorological applications.
In these applications, cyclic reduction and related methods provide the
basis for methods of solving elliptic equations such as Laplace and Poisson
equations directly, that is, non-iteratively. Since the solutions are also exact
in the sense that they contain no iteration error, this method is invaluable
whenever it can be used.
Cyclic reduction is closely related to the fast Fourier transform which is
also used to solve elliptic equations in simple geometries. Fourier methods
may also be used for evaluating derivatives, as was shown in Sect. 3.10.