Difficulty in higher dimensions

So far we have had no trouble obtaining cheap, safe, and accurate difference methods for solving partial-differential equations (PDEs). The implicit method has met all needs. But in space dimensions higher than one, the implicit method becomes prohibitively costly. For the common example of problems in which $\partial^2 / \partial x^2$ becomes generalized to $\partial^2 / \partial x^2 \, +\, \partial^2 / \partial y^2$,we will learn the reason why. The simplest case is the heat-flow equation for which the Crank-Nicolson method gave us (37). Introducing the abbreviation $\delta_{xx} q \,=\,$q^x+1 -2q^x + q^x-1, equation (37) becomes  

$$\left( 1\ -\ \alpha \ \delta_{{xx}} \right) \ Q_{{t+1}} \eq \left( 1\ +\ \alpha \ \delta_{{xx}} \right) \ Q_t$$ (48)

The nested expression on the left represents a tridiagonal matrix. The critical stage is in solving the tridiagonal simultaneous equations for the vector of unknowns $\ Q_{{t+1}}$.Fortunately there is a special algorithm for this solution, and the cost increases only linearly with the size of the matrix. Now turn from the one-dimensional physical space of x to two-dimensional (x,y)-space. Letting $\alpha$ denote the numerical constant in (48), the equation for stepping forward in time is  

$$[ \, 1\ -\ \alpha\ ( \delta_{{xx}} \ +\ \delta_{{yy}} ) \ ] \... ... [ 1\ +\ \alpha ( \delta_{{xx}} \ +\ \delta_{{yy}} ) \ ] \ Q_t$$ (49)

The unknowns Q_t+1 are a two-dimensional function of x and y that can be denoted by a matrix. Next we will interpret the bracketed expression on the left side. It turns out to be a four-dimensional matrix!

To clarify the meaning of this matrix, a mapping from two dimensions to one will be illustrated. Take the temperature Q to be defined on a 4$\times$4 mesh. A natural way of numbering the points on the mesh is  

$$\begin{array} {rrrr} 11 & 21 & 31 & 41 \\ 12 & 22 & 32 & 42 \\ 13 & 23 & 33 & 43 \\ 14 & 24 & 34 & 44 \\ \end{array}$$ (50)

For algebraic purposes these sixteen numbers can be mapped into a vector. There are many ways to do this. A simple way would be to associate the locations in (50) with vector components by the column arrangement  

$$\begin{array} {rrrr} 1 & 2 & 3 & 4 \\ 5 & 6 & 7 & 8 \\ 9 & 10 & 11 & 12 \\ 13 & 14 & 15 & 16 \\ \end{array}$$ (51)

The second difference operator has the following star in the (x,y)-plane:  

$$\begin{tabular} {\vert c\vert c\vert c\vert} \cline{2-2} \mu... ...}{} & &\multicolumn{1}{\vert c}{} \\ \cline{2-2}\end{tabular}$$ (52)

Lay this star down in the (x,y)-plane (51) and move it around. Unfortunately, with just sixteen points, much of what you see is dominated by edges and corners. Try every position of the star that allows the center -4 to overlay one of the sixteen points. Never mind the 1's going off the sides. Start with the -4 in (52) over the 1 in the upper left corner of (51). Observe 1's on the 2 and the 5. Copy the 1's into the top row of Table 4.8 into the second and fifth columns. Then put the -4 in (52) over the 2 in (51). Observe 1's on the 1, 3, and 6. Copy the 1's into the next row of Table 4.8. Then put the -4 over the 3. Observe 1's on the 2, 4, and 7. Continue likewise. The 16$\times$16 square matrix that results is shown in Table 4.8.

Now that Table 4.8 has been constructed we can return to the interpretation of equation (49). The matrix of unknowns Q_t+1 has been mapped into a sixteen-point column vector, and the bracketed expression multiplying Q_t+1 can be mapped into a 16$\times$16 matrix. Clearly, the matrix contains zeroes everywhere that Table 4.8 contains dots. It seems fortunate that the table contains many zeroes, and we are led to hope for a rapid solution method for the simultaneous equations. The bad news is that no good method has ever been found. The best methods seem to require effort proportional to N³, where in this case N=4. Based on our experience in one dimension, those of us who worked on this problem hoped for a method proportional to N², which is the cost of an explicit method--essentially the cost of computing the right side of (41). Even all the features of implicit methods do not justify an additional cost of a factor of N. The next best thing is the splitting method.

 

-4 1 1

1 -4 1 1

1 -4 1 1

1 -4 1

1 -4 1 1

1 1 -4 1 1

1 1 -4 1 1

1 1 -4 1

1 -4 1 1

1 1 -4 1 1

1 1 -4 1 1

1 1 -4 1

1 -4 1

1 1 -4 1

1 1 -4 1

1 1 -4

EXERCISES:

1. Interpret the inflation-of-money equation when the interest rate is the imaginary number i/10.
2. Write the 45$^\circ$ diffraction equation in (x,z)-space for fixed $\omega$ in the form of (36).