NAG Library Routine Document

D03EDF

+− Contents

1 Purpose

2 Specification

3 Description

4 References

5 Parameters

6 Error Indicators and Warnings

7 Accuracy

8 Further Comments

+− 9 Example

9.1 Program Text

9.2 Program Data

9.3 Program Results

1 Purpose

D03EDF solves seven-diagonal systems of linear equations which arise from the discretization of an elliptic partial differential equation on a rectangular region. This routine uses a multigrid technique.

2 Specification

SUBROUTINE D03EDF (

NGX, NGY, LDA, A, RHS, UB, MAXIT, ACC, US, U, IOUT, NUMIT, IFAIL)

INTEGER	NGX, NGY, LDA, MAXIT, IOUT, NUMIT, IFAIL
REAL (KIND=nag_wp)	A(LDA,7), RHS(LDA), UB(NGX*NGY), ACC, US(LDA), U(LDA)

3 Description

D03EDF solves, by multigrid iteration, the seven-point scheme

\begin{array}{clclcl} A_{i, j}^{6} u_{i - 1, j + 1} & + & A_{i, j}^{7} u_{i, j + 1} \\ + & A_{i, j}^{3} u_{i - 1, j} & + & A_{i, j}^{4} u_{i j} & + & A_{i, j}^{5} u_{i + 1, j} \\ + & A_{i, j}^{1} u_{i, j - 1} & + & A_{i, j}^{2} u_{i + 1, j - 1} = f_{i j}, i = 1, 2, \dots, n_{x} ​ and ​ j = 1, 2, \dots, n_{y}, \end{array}

which arises from the discretization of an elliptic partial differential equation of the form

α (x, y) U_{x x} + β (x, y) U_{x y} + γ (x, y) U_{y y} + δ (x, y) U_{x} + ε (x, y) U_{y} + ϕ (x, y) U = ψ (x, y)

and its boundary conditions, defined on a rectangular region. This we write in matrix form as

A u = f .

The algorithm is described in separate reports by Wesseling (1982a), Wesseling (1982b) and McCarthy (1983).

Systems of linear equations, matching the seven-point stencil defined above, are solved by a multigrid iteration. An initial estimate of the solution must be provided by you. A zero guess may be supplied if no better approximation is available.

A ‘smoother’ based on incomplete Crout decomposition is used to eliminate the high frequency components of the error. A restriction operator is then used to map the system on to a sequence of coarser grids. The errors are then smoothed and prolongated (mapped onto successively finer grids). When the finest cycle is reached, the approximation to the solution is corrected. The cycle is repeated for MAXIT iterations or until the required accuracy, ACC, is reached.

D03EDF will automatically determine the number

l

of possible coarse grids, ‘levels’ of the multigrid scheme, for a particular problem. In other words, D03EDF determines the maximum integer

l

so that

n_{x}

and

n_{y}

can be expressed in the form

n_{x} = m 2^{l - 1} + 1, n_{y} = n 2^{l - 1} + 1,   with m \geq 2 ​ and ​ n \geq 2 .

It should be noted that the rate of convergence improves significantly with the number of levels used (see McCarthy (1983)), so that

n_{x}

and

n_{y}

should be carefully chosen so that

n_{x} - 1

and

n_{y} - 1

have factors of the form

2^{l}

, with

l

as large as possible. For good convergence the integer

l

should be at least

2

D03EDF has been found to be robust in application, but being an iterative method the problem of divergence can arise. For a strictly diagonally dominant matrix

A

|A_{i j}^{4}| > \sum_{k \neq 4} |A_{i j}^{k}|, i = 1, 2, \dots, n_{x} ​ and ​ j = 1, 2, \dots, n_{y}

no such problem is foreseen. The diagonal dominance of

A

is not a necessary condition, but should this condition be strongly violated then divergence may occur. The quickest test is to try the routine.

4 References

McCarthy G J (1983) Investigation into the multigrid code MGD1 Report AERE-R 10889 Harwell

Wesseling P (1982a) MGD1 – a robust and efficient multigrid method Multigrid Methods. Lecture Notes in Mathematics 960 614–630 Springer–Verlag

Wesseling P (1982b) Theoretical aspects of a multigrid method SIAM J. Sci. Statist. Comput. 3 387–407

5 Parameters

1: NGX – INTEGERInput

On entry: the number of interior grid points in the

x

-direction,

n_{x}

NGX - 1

should preferably be divisible by as high a power of

2

as possible.

Constraint:

NGX \geq 3

2: NGY – INTEGERInput

On entry: the number of interior grid points in the

y

-direction,

n_{y}

NGY - 1

should preferably be divisible by as high a power of

2

as possible.

Constraint:

NGY \geq 3

3: LDA – INTEGERInput

On entry: the first dimension of the array A, which must also be a lower bound for the dimension of the arrays RHS, US and U as declared in the (sub)program from which D03EDF is called. It is always sufficient to set

LDA \geq (4 \times (NGX + 1) \times (NGY + 1)) / 3

, but slightly smaller values may be permitted, depending on the values of NGX and NGY. If on entry, LDA is too small, an error message gives the minimum permitted value. (LDA must be large enough to allow space for the coarse-grid approximations.)

4: A(LDA, $7$ ) – REAL (KIND=nag_wp) arrayInput/Output

On entry:

A (i + (j - 1) \times NGX, k)

must be set to

A_{i j}^{k}

, for

i = 1, 2, \dots, NGX

j = 1, 2, \dots, NGY

and

k = 1, 2, \dots, 7

On exit: is overwritten.

5: RHS(LDA) – REAL (KIND=nag_wp) arrayInput/Output

On entry:

RHS (i + (j - 1) \times NGX)

must be set to

f_{i j}

, for

i = 1, 2, \dots, NGX

and

j = 1, 2, \dots, NGY

On exit: the first

NGX \times NGY

elements are unchanged and the rest of the array is used as workspace.

6: UB( $NGX \times NGY$ ) – REAL (KIND=nag_wp) arrayInput/Output

On entry:

UB (i + (j - 1) \times NGX)

must be set to the initial estimate for the solution

u_{i j}

On exit: the corresponding component of the residual

r = f - A u

7: MAXIT – INTEGERInput

On entry: the maximum permitted number of multigrid iterations. If

MAXIT = 0

, no multigrid iterations are performed, but the coarse-grid approximations and incomplete Crout decompositions are computed, and may be output if IOUT is set accordingly.

Constraint:

MAXIT \geq 0

8: ACC – REAL (KIND=nag_wp)Input

On entry: the required tolerance for convergence of the residual

2

-norm:

{‖r‖}_{2} = \sqrt{\sum_{k = 1}^{NGX \times NGY} {(r_{k})}^{2}}

where

r = f - A u

and

u

is the computed solution. Note that the norm is not scaled by the number of equations. The routine will stop after fewer than MAXIT iterations if the residual

2

-norm is less than the specified tolerance. (If

MAXIT > 0

, at least one iteration is always performed.)

If on entry

ACC = 0.0

, then the machine precision is used as a default value for the tolerance; if

ACC > 0.0

, but ACC is less than the machine precision, then the routine will stop when the residual

2

-norm is less than the machine precision and IFAIL will be set to

4

Constraint:

ACC \geq 0.0

9: US(LDA) – REAL (KIND=nag_wp) arrayOutput

On exit: the residual

2

-norm, stored in element

US (1)

10: U(LDA) – REAL (KIND=nag_wp) arrayOutput

On exit: the computed solution

u_{i j}

is returned in

U (i + (j - 1) \times NGX)

, for

i = 1, 2, \dots, NGX

and

j = 1, 2, \dots, NGY

11: IOUT – INTEGERInput

On entry: controls the output of printed information to the advisory message unit as returned by X04ABF:

$IOUT = 0$: No output.
$IOUT = 1$: The solution $u_{i j}$ , for $i = 1, 2, \dots, NGX$ and $j = 1, 2, \dots, NGY$ .
$IOUT = 2$: The residual $2$ -norm after each iteration, with the reduction factor over the previous iteration.
$IOUT = 3$: As for $IOUT = 1$ and $IOUT = 2$ .
$IOUT = 4$: As for $IOUT = 3$ , plus the final residual (as returned in UB).
$IOUT = 5$: As for $IOUT = 4$ , plus the initial elements of A and RHS.
$IOUT = 6$: As for $IOUT = 5$ , plus the Galerkin coarse grid approximations.
$IOUT = 7$: As for $IOUT = 6$ , plus the incomplete Crout decompositions.
$IOUT = 8$: As for $IOUT = 7$ , plus the residual after each iteration.

The elements

A (p, k)

, the Galerkin coarse grid approximations and the incomplete Crout decompositions are output in the format:

Y-index $= j$
X-index $= i A (p, 1) A (p, 2) A (p, 3) A (p, 4) A (p, 5) A (p, 6) A (p, 7)$
where $p = i + (j - 1) \times NGX$ , for $i = 1, 2, \dots, NGX$ and $j = 1, 2, \dots, NGY$ .

The vectors

U (p)

UB (p)

RHS (p)

are output in matrix form with NGY rows and NGX columns. Where

NGX > 10

, the NGX values for a given

j

value are produced in rows of

10

. Values of

IOUT > 4

may yield considerable amounts of output.

Constraint:

0 \leq IOUT \leq 8

12: NUMIT – INTEGEROutput

On exit: the number of iterations performed.

13: IFAIL – INTEGERInput/Output

On entry: IFAIL must be set to

0

- 1 ​ or ​ 1

. If you are unfamiliar with this parameter you should refer to Section 3.3 in the Essential Introduction for details.

For environments where it might be inappropriate to halt program execution when an error is detected, the value

- 1 ​ or ​ 1

is recommended. If the output of error messages is undesirable, then the value

1

is recommended. Otherwise, if you are not familiar with this parameter, the recommended value is

0

. When the value $- 1 or 1$ is used it is essential to test the value of IFAIL on exit.

On exit:

IFAIL = 0

unless the routine detects an error or a warning has been flagged (see Section 6).

6 Error Indicators and Warnings

If on entry

IFAIL = 0

- 1

, explanatory error messages are output on the current error message unit (as defined by X04AAF).

Errors or warnings detected by the routine:

$IFAIL = 1$

On entry,	$NGX < 3$ ,
or	$NGY < 3$ ,
or	LDA is too small,
or	$ACC < 0.0$ ,
or	$MAXIT < 0$ ,
or	$IOUT < 0$ ,
or	$IOUT > 8$ .

$IFAIL = 2$: MAXIT iterations have been performed with the residual $2$ -norm decreasing at each iteration but the residual $2$ -norm has not been reduced to less than the specified tolerance (see ACC). Examine the progress of the iteration by setting $IOUT \geq 2$ .

$IFAIL = 3$: As for $IFAIL = 2$ , except that at one or more iterations the residual $2$ -norm did not decrease. It is likely that the method fails to converge for the given matrix $A$ .

$IFAIL = 4$: On entry, ACC is less than the machine precision. The routine terminated because the residual norm is less than the machine precision.

7 Accuracy

See ACC (Section 5).

8 Further Comments

The rate of convergence of this routine is strongly dependent upon the number of levels,

l

, in the multigrid scheme, and thus the choice of NGX and NGY is very important. You are advised to experiment with different values of NGX and NGY to see the effect they have on the rate of convergence; for example, using a value such as

NGX = 65

(

= 2^{6} + 1

) followed by

NGX = 64

(for which

l = 1

9 Example

The program solves the elliptic partial differential equation

U_{x x} - α U_{x y} + U_{y y} = - 4, α = 1.7

on the unit square

0 \leq x, y \leq 1

, with boundary conditions

U = 0 on ​ \{\begin{array}{cl} x = 0, & (0 \leq y \leq 1) \\ y = 0, & (0 \leq x \leq 1) \\ y = 1, & (0 \leq x \leq 1) \end{array} U = 1 on ​ x = 1, 0 \leq y \leq 1 .

For the equation to be elliptic,

α

must be less than

2

The equation is discretized on a square grid with mesh spacing

h

in both directions using the following approximations:

Figure 1

\begin{array}{lcl} U_{x x} & ≃ & \frac{1}{h^{2}} (U_{E} - 2 U_{O} + U_{W}) \\ U_{y y} & ≃ & \frac{1}{h^{2}} (U_{N} - 2 U_{O} + U_{S}) \\ U_{x y} & ≃ & \frac{1}{2 h^{2}} (U_{N} - U_{NW} + U_{E} - 2 U_{O} + U_{W} - U_{SE} + U_{S}) . \end{array}

Thus the following equations are solved:

\begin{array}{crclcl} \frac{1}{2} α u_{i - 1, j + 1} & + & (1 - \frac{1}{2} α) u_{i, j + 1} \\ + & (1 - \frac{1}{2} α) u_{i + 1, j} & + & (- 4 + α) u_{i j} & + & (1 - \frac{1}{2} α) u_{i + 1, j} \\ + & (1 - \frac{1}{2} α) u_{i, j - 1} & + & \frac{1}{2} α u_{i + 1, j - 1} = - 4 h^{2} \end{array}

NAG Library Routine DocumentD03EDF

+− Contents

1 Purpose

2 Specification

3 Description

4 References

5 Parameters

6 Error Indicators and Warnings

7 Accuracy

8 Further Comments

9 Example

9.1 Program Text

9.2 Program Data

9.3 Program Results

NAG Library Routine Document

D03EDF