This has serious consequences. Later passes spread these
values out even further. After three passes, the matrix contains
a large diagonal and a noisy background. At first glance, this
might seem like a good result; the artifacts have dissipated
rather than remaining as discrete events. The problem is that
the number of operations needed to attenuate the artifacts
becomes large very rapidly, so large that the
cost of such an operation is prohibitive (order *n ^{2}* rotations
instead of order

Figure 3

The problem in Figure comes from the random variation of the coefficient values. When we compute the angle for Givens rotation, we get slightly different answers at each point because of the varying coefficients. The angles that we compute are correct in that they do the best possible job of attacking the off-diagonal elements. However, the creation of artifacts is also controlled by the rotation angles. Different angles mean that artifacts are created in different places. Thus the 1% (4% on the main diagonal) variation in coefficients introduces artifacts over ranges of positions rather than at discrete locations. Again, this is a bad idea because it means we have to do prohibitively many operations to arrive at a tridiagonal form.

One alternative is to use a constant (mean) value of rotation angle to perform the Givens rotations. This constant angle would keep artifacts confined to a few locations, and mean that attenuating the artifacts with successive passes would be much faster. In Figure , I did this, using a rotation angle computed from the mean values of the diagonal coefficients. You can see that, as I predicted, the artifacts remain along the diagonals, similar to Figure , rather than spreading over the entire matrix. This is good. On the down side, however, successive passes of rotation do not reduce the matrix to tridiagonal form. Compare the lower right panel of Figure to that of Figure , and you will see that the artifacts have not been attenuated very well. More passes do not solve the problem.

The reason this happens is because we used an average rotation angle. This angle does a relatively poor job of annihilating the off-diagonal elements, so no matter how many times we do it, these elements do not go away completely.

Figure 4

All hope is not lost. Certainly in Figure we have improved the diagonal dominance of the matrix, at little cost. We could use such an operator now in the Jacobi iterative scheme or conjugate gradients and expect convergence to be much faster. In the case of Jacobi, the 45 degree algorithm should be stable where it was not before. So even if we have not been able to reduce to tridiagonal form in the lateral velocity case, this method should still be a useful preconditioner for other methods.

12/18/1997