56
3. Finite Difference Methods
algebraic equations, which must be solved numerically. This system is sparse,
meaning that each equation contains only a few unknowns. The system can
be written in matrix notation as follows:
A 4 = Q ,
(3.43)
where A is the square sparse coefficient matrix, 4 is a vector (or column
matrix) containing the variable values at the grid nodes, and Q is the vector
containing the terms on the right-hand side of Eq. (3.42).
The structure of matrix A depends on the ordering of variables in the
vector 4 . For structured grids, if the variables are labeled starting at a corner and traversing line after line in a regular manner (lexicographic ordering),
the matrix has a poly-diagonal structure. For the case of a five-point computational molecule, all the non-zero coefficients lie on the main diagonal, the
two neighboring diagonals, and two other diagonals removed by N positions
from the main diagonal, where N is the number of nodes in one direction.
All other coefficients are zero. This structure allows use of efficient iterative
solvers.
Throughout this book we shall, for the sake of definiteness, order the
entries in vector 4 starting at the southwest corner of the domain, proceeding
northwards along each grid line and then eastward across the domain (in
three-dimensional cases we shall start at the bottom computational surface
and proceed on each horizontal plane in the manner just described, and then
go from bottom to top). The variables are normally stored in computers in
one-dimensional arrays. The conversion between the grid locations, compass
notation, and storage locations is indicated in Table 3.2.
Table 3.2. Conversion of grid indices to one-dimensional storage locations for
vectors or column matrices
Grid location Compass notation Storage location
i l j , k
P
1 = ( k - l ) N , N ; + (i- l ) N j + j
i - l , j , k
W
1 - N,
2 , j - 1 , k
S
1 - 1
2 , j + 1 , k
N
1 + 1
i + l , j , k
E
1 + N,
i , j, k - 1
B
1 - N, N,
i l j1 k + 1
T
1 + N , N j
Because the matrix A is sparse, it does not make sense to store it as a
two-dimensional array in computer memory (this is standard practice for full
matrices). Storing the elements of each non-zero diagonal in a separate array
of dimension 1 x Ni N j , where Ni and N j are the numbers of grid points in the
two coordinate directions, requires only 5NiNj words of storage; full array
storage would require N:N; words of storage. In three dimensions, the numbers are 7 N i N j Nk and N:N? N i l respectively. The difference is sufficiently
3. Finite Difference Methods
algebraic equations, which must be solved numerically. This system is sparse,
meaning that each equation contains only a few unknowns. The system can
be written in matrix notation as follows:
A 4 = Q ,
(3.43)
where A is the square sparse coefficient matrix, 4 is a vector (or column
matrix) containing the variable values at the grid nodes, and Q is the vector
containing the terms on the right-hand side of Eq. (3.42).
The structure of matrix A depends on the ordering of variables in the
vector 4 . For structured grids, if the variables are labeled starting at a corner and traversing line after line in a regular manner (lexicographic ordering),
the matrix has a poly-diagonal structure. For the case of a five-point computational molecule, all the non-zero coefficients lie on the main diagonal, the
two neighboring diagonals, and two other diagonals removed by N positions
from the main diagonal, where N is the number of nodes in one direction.
All other coefficients are zero. This structure allows use of efficient iterative
solvers.
Throughout this book we shall, for the sake of definiteness, order the
entries in vector 4 starting at the southwest corner of the domain, proceeding
northwards along each grid line and then eastward across the domain (in
three-dimensional cases we shall start at the bottom computational surface
and proceed on each horizontal plane in the manner just described, and then
go from bottom to top). The variables are normally stored in computers in
one-dimensional arrays. The conversion between the grid locations, compass
notation, and storage locations is indicated in Table 3.2.
Table 3.2. Conversion of grid indices to one-dimensional storage locations for
vectors or column matrices
Grid location Compass notation Storage location
i l j , k
P
1 = ( k - l ) N , N ; + (i- l ) N j + j
i - l , j , k
W
1 - N,
2 , j - 1 , k
S
1 - 1
2 , j + 1 , k
N
1 + 1
i + l , j , k
E
1 + N,
i , j, k - 1
B
1 - N, N,
i l j1 k + 1
T
1 + N , N j
Because the matrix A is sparse, it does not make sense to store it as a
two-dimensional array in computer memory (this is standard practice for full
matrices). Storing the elements of each non-zero diagonal in a separate array
of dimension 1 x Ni N j , where Ni and N j are the numbers of grid points in the
two coordinate directions, requires only 5NiNj words of storage; full array
storage would require N:N; words of storage. In three dimensions, the numbers are 7 N i N j Nk and N:N? N i l respectively. The difference is sufficiently