NBS!R 80-2056

The Numericai Solution of A

Nonseparable Elliptic Partial

Differential Equation By

Preconditioned Conjugate

Gradients

Boeing Computer Services Company

Mail Stop 9C-01

P. 0. Sox 24346

Seattle, Washington 98124

U S. DEPARTMENT OF COMMERCE

National Bureau of Standards

Naticnal Engineering Laboratory

Center for Applied Mathematics

Washington, DC 20234

Acni 1930

Final Report

P''Gpared for: for Applied Mathematics

j c^^3 ine6riT^g Laboratory

100 { Bureau of Standards

,U56 3ton, DC 2C234

' 80-2056

198C

C.2
- » -

s.

u
NBSIR 80-2056 %• • THE NUMERICAL SOLUTION OF A

NONSEPARABLE ELLIPTIC PARTIAL

DIFFERENTIAL EQUATION BY

PRECONDITIONED CONJUGATE

GRADIENTS

ATIOMAL BURKAU

OF STANDABOg

UBitART

SEP i 6 1981

{ , , , . (UJ[^ I lV '» '0

no,

. /9S/

John Gregg Lewis*

Ronald G. Rehmt

‘Boeing Computer Services Company

Mail Stop 9C-01

P. 0. Box 24346

Seattle, Washington 98124

tU.S. DEPARTMENT OF COMMERCE

National Bureau of Standards

National Engineering Laboratory

Center for Applied Mathematics

Washington. DC 20234

April 1 981

Final Report

Prepared for: Center for Applied Mathematics

National Engineering Laboratory

National Bureau of Standards

Washington, DC 20234

U.S. DEPARTMENT OF COMMERCE, Malcolm Baldrige, Secretary

NATIONAL BUREAU OF STANDARDS, Ernest Ambler, Director

JOURNAL OF RESEARCH of the National Bureau of Standards

Vol. 85. No. 5. September-October 1980

The Numerical Solution of a Nonseparable

Elliptic Partial Differential Equation

by Preconditioned Conjugate Gradients Lewis*John Gregg * and Ronald G. Rehmt

National Bureau of Standards, Washington, D.C 20234

April 16, 1980

Id thi« report the combinmtion of an iterative technique, the conjugate gradient algorithm, with a fast direct method, cyclic reduction, is used to solve the linear algebraic equations resulting from discretisation of a nonseparable elliptic partial differential equation. An expository discussion of the conjugate gradient and

preconditioned conjugate gradient algorithms and of their use in the solution of partial differential equations is presented. New results extending the use of the preconditioned conjugate gradients technique to singular linear equations which arise from discretixed elliptic equations with Neumann boundary conditions are also givea The

algorithms are applied to solve a speciTic elliptic equation which arises in the study of buoyant convection pro- duced by a room fire. A code was developed to implement the algorithms for this applicatioa Numerical results obtained through testing and use of the code are disciused. Key Words: Conjugate gradient algorithm; elliptic partial differential equations; iterative methods for linear algebraic equations; Neumann boundary conditions; sparse matrices.

The numerical solution of the linear algebraic equations which result from a discretization of an elliptic

partial differential equation has been, and continues to be, the focus of much research in numerical

analysis. Over the past 25 years there have been many advances, some toward improved iterative schemes

(ADI, SOR, etc.), others toward fast direct methods (most notably those based on FFT’s). See Rice [1] ' for a

brief survey of the impact of these advances. In this paper we discuss the combination of an iterative tech- nique, the conjugate gradient algorithm, with a fast direct method, cyclic reduction, to extend the capabilities of the fast solver. For examples of the use of similar combinations of algorithms, see Concus & Golub

[2], Concus, Golub and O’Leary [3], O’Leary [4] and O’Leary and Widlund [5]. The work described in this paper resulted from a study of buoyant convection carried out at the National

Bureau of Standards, [6, 7, 8]. The specific elliptic partial differential equation for pressure arising in this work is used as a model problem in the present paper. The experience of the first author with the buoyant

convection model motivated the writing of sections 1 and 2, which gives an exposition of the conjugate gra- dient and preconditioned conjugate gradient algorithms. These sections contain no new material; they were

written so that this paper may be accessible to an audience unfamiliar with the development of the conjugate gradient algorithm and its use in the solution of partial differential equations. Section 3 has a discus- sion of the model problem, the pressure equation. Section 4 contains several new results extending the use

of preconditioned conjugate gradient technology to the singular linear equations which result from

Neumann boundary value problems. We conclude with some numerical examples from the buoyant convection problem. A listing of a FORTRAN program implementing the algorithm discussed here is presented in

[15].

*C«atcr (or Applied MBthemetko, Ntbo&AJ Enfiiieefin| Leborotory; uid UtthemeticAi Science* Depertseot, Jobn* Hopkins University. Current Address: Boeing Computer

Serrioss, Co^ Msil Stop 9C-01, P.O. Boi 24546, Seattle. Washinfton 96124

tCenter for Applied Mstkematic*, Nsdonal Enfineering Laboratory.

* Figure* ia brackets indicate literature references at tbe end of this paper.

367
i
1 . An introduction to the conjugate gradient algorithm

The discretization of an elliptic differential operator by standard finite difference or finite element tech- niques produces, as the finite analog of the continuous operator, very large matrices with most elements

zero. From an algebraic standpoint we can very often view the numerical solution of the differential equation as:

Solve =6 (1)

where A is a k hy k, {k large) real symmetric, positive definite and sparse matrix. Fast direct methods with minimal storage requirements exist when A is the finite difference operator

resulting from a separable elliptic operator on a rectangular region, and for some other common, but specific, cases. If the operator is nonseparable, or the region non-rectangular, the special direct methods may

not apply. Moreover, the use of general direct methods such as factoring^ into a Cholesky decomposition.

A = LL\

often impose unbearable storage requirements because many zero entries are filled in during the decompositioiL

Iterative methods, such as SOR and Causs-Seidel, solve a transformation of the problem. Instead of solv- ing (1) directly, they "split” A as A = M-N, and solve the equivalent problem through an iteration of the form Afx**' = yVx* + 6; Le., find a fixed point of the equation

Mx= Nx + b. (2)

The efficiency of the solution method depends in part on the appropriateness of the splitting and in part on

acceleration of the iteration toward the fixed point

The conjugate gradient algorithm can be motivated as the solution of another transformation of problem

(1). Consider the inner product <x,y> = x^Ay. This induces a norm ||i||^ = \/ x^Ax on /?* when A is positive

definite. Problem (1) is equivalent to: find x to minimize

E(x) = ix-x^V A(x-x*) = |z-x*| i (3)

where x * is the solution of (1). The problems are equivalent because £(x) ^ 0 for all x, and E(x) = 0 <=> x = X*. The immediate usefulness of the transformation is not obvious, especially since computing E{x)

appears to require the solution, x*, of the problem we wish to solve. Note however, that we can evaluate whether a given x is or is not a solution by computing the residual r = b — Ax. Further, while we cannot

evaluate E{x) directly, we can evaluate its gradient vector

V£(x) = 2(Ax-Ax*) = 2(Ax - b) = -2r.

Hence, r gives us the direction in which E decreases most rapidly (unless r is identically zero, which characterizes the solution).

These two characteristics of problem (3) lead directly to a simple algorithm for solving(3):

STEEPEST DESCENT: Given a guess x„ not a solution,

i

set r, = 6 — Ax,

setx,*, = X, + o,r,

where o, is a scalar chosen to make x,*, minimize E (x.*,) for all vectors of the form x, + /3r,. We can easily compute the gradient r,. It is also easy to compute o, so that E (x,*i) = E (x, + o,r.) < E (x, +

/3r.) for all ji. The mimimum of E (x, + /Jr,) is given by the solution of

368
m*'.fhe-g»c> i^A •!

.,i >93 irtsni«3 r Mho '»mv,‘!^ih -y-i-.n

-'’ ••>n »<!«

,.ft,ipAU 4 ;jw ^v/ A 'uo iu ^yn^o *-4 f 1o •,.>?«»•-.

- '<>9 ‘''Vi''’ .?: l(- 'Ov ?ct>jTjmt'p ini '•'''' i''- ' *•" ' -.i’'*.‘S**%i« ofc -ai'?

' y;K »'»<)

If> C

- ,. \ Tfi&h

thi&,n^m{»::bn’^ Mihb . .lUi-AWiUta A A ;«

•f6l-»iwc “jiit»1 9.1; .»i'K r«:V l*i* • «. '"-f flbo'i^^fr lt*i'*!»> l

..q- tifd -.PU. H.a . i

.f.oil 7 vn ;:>-.ui,. 1- .•rqf -»xij a<- a ^1: w ,r^ ' it /-non : .tofl . v< n,l; •*« '

,vh n ..•vl;»fS: > .. oir.i -r ; ;>«u a»4’ ,-.^ - aAo^,^ /(IjM;, lOi.

jwfi y...iii.h n» b4lll 9t6 ,9hiftf. 0'*9^ sa>. ,!9ti w.v.rr m;p:-.i 9?4<;le:^ 9iVtsi«c«J«;; -

• '4>. n .(• - . ii^' if^oo Ji'

<,!..• to hsaKi:! ,fw'’1<rV' l.tl Vi *Ut4BH.fS«i?.Tl > ».i.i> ,Wi"i-Cia* •' «'• f? 'S « li'OT .«t»i«.'». ; '->.« /

,a, is «.».,-,.5 i TM rfw>'U. ».^d<«.. i.sfwmpe ,.(! -,).:> I.:... ,v •«. - ' * 1 '

^1

' 'SS'^y baxll *> Ar -! ,. -. . P ^‘l “ ^I’fe «mo.t

(^)

.cj a j A -

no rtca oi bfls saiiliJq^ V' «d9crv*bhqw7'.W« >4t .'>« J .a-T **: soo-nini. b. imv-J’'^- 'ills K> vo*/ -, ,.'?w til T

bt£W.Ol rt*:niJ^a 5

i

n..t4«KV BBi.-iiiii-.sh*'^ r;«05» »• i»i>i*>» »J> »i i' 'i8».'>'”' •..! «>.«,.;. '*»•>» •’’*<» ’<!"t'';'- "'*

,

'., .,«.!« » «S a.V.- » .ixj m«N’ . .hit ;/»/•« <'.-- ....bo., «r«: «> •»«>• ;•;'. '•

/Ar.hwoj'ai At t: bail , 0

' h 'I j i/- ‘i i/iV^

,pv ^ (:^.‘..

h')A riiH!. xU«i->rjw ^fltoWio .ton at n „ij..v,.oi. iM» >»U ' • -.'su'ur.'ttux t»<3 F a

.m>L'n I,-.* .Ini'! .:' ./;r a; A> * • 4ii;« .'i^tTp’a - A sifi laaiwti. w<‘i Si ^ .. -!iai V

-

C 1A. 1 - rf'.ftlw tfHwitonbi *?. s ^ MtU ni m ewV ’

-

; .;-- /ait's. !»;;:'

vr,.< . /b>!. V.sj w<*»kt»a}» Mtitni. a ^xi ;,. ..-stMsaowi

,n»L‘wiv>> . ton ’

'*’ “’

jvb * - .' f / 0

-1

- A

-

i.. ' »»»

^

>

• '^07'*'

''''» ' ,,.' 'ijIaw Q9ii&tfc^SJHi v .. *1 .»'

1 '-

;• -i)S o-n ,t) 3

- ^ a: »««*. .. U

• v-'.^> ni. • -

1o rfn h/Jo* f7-l3 fd rw/iii >)“AV ‘
J-£(x.+^r,) = 0

But ^

E (x. + Pn) = 2 (Pr/Ar^ - r/r,).

so

Ot =

r/r,

r/An ( 4)

is the optimal choice for O/. Hence, we can carry out the iteration to minimize E (x) without computing E. Note also that/f enters the iteration only in forming the products /4x, and/4r,.

Unfortunately steepest descent is not a practical algorithm because the convergence can be very slow. We

can obtain more rapid convergence by using not the steepest descent directions {rj, but instead a sequence

of downhill or descent directions {p,} which satisfy additional properties. We characterize the term "descent direction" and simultaneously find the optimal distance to move in that direction, through the follow- ing simple result

LEMMA; //p’^r ^ 0, then

P = minimizes E (x + /Jp) for all p. (5)

PROOF; Simply differentiate ^(x + Pp) with respect to /3: ^£ (x + /?p) = 2 (pM (x - X •) + pp^Ap)

= 2(-p^r+Pp^Ap).

It is a simple computation to show that E(x + Pp) < E (x). Note that /? is positive if p^r > 0, which characterizes p as a descent, not an ascent, direction.

The first observation which leads to improved convergence is that the choice in (5) for 0, not only solves the one-dimensional minimization, it gives us the p — component of x* exactly. To see this, note that A positive definite implies that we can uniquely write

X + Pp = op + 6w

( 6) X* = o*p + 6*z

where ui^Ap = 0 = zMp. This last condition is read: w, z are/f-orthogonal or A-conjugate to p. Now substi- tute the decompositions (6) into E:

E{x + Pp) = (o - o •) ^p'^Ap -t- terms not involving a, cr * or p (7)

The choice (5) for P minimizes the left side of (7), and clearly a = a* minimizes the right hand side of (7). Hence choosing p = P i" implies that p^Ap

(x +pp)-x* = dw- 6 *z. ( 8)

369
wH gr:i!yq<no'j 'i f.i3 *mu J;r> nf»'> j’.x a *>'», ->» •'^ >>:*'’> feay/^-iy^ <}

’ .i<Kiy'Tl6 ,ii ^u-'

'/W woti ?'J rw?"' '9;>'»isfj(rwyi5t,6a »di 48UjB:^e;> I;" f<>irvC( ' JOi^ >l '^.-i

<«%«»»•• ‘^''utf ,

> ».•«<»'.7-'J>-m9^a w

X*!’ iw^« *«»

•aI')''' .‘>r»yi •ari'; •rfatj''**' (•,%] Tiaoi^laaitt .to - irto^ros •^••6

-v«^4i'oV:9at .%-ufi'rtlJ ,«<#»*»?•< y'b-iinA't in y.-oto ot ..iJi b(ati ^<i*

, T '‘'•I {•2i k}^ *.•»»< r>.V!t'ist» -_

M

' ’!

(V’^K'crt.+ - -4,W*<V < ^ iOi*] 5" A *|^“

,0«< ntiU-M -mZ {*)& > •• A-*- a v, rl

Mi'i- ';»»iil» ••* a-n'-i: t-.M i*yn -jr-. «!f tr «<!•.

<(}i-''' Ti»0-4J4'l '‘t?)«i ir-^Vrfj -..fr : 4ifT F* 0‘S»*m**.-'^^ -.:f

^ 3stij •*io» ,*irii! >/T »? *t » ‘wj» iJ .iro/7jst't'«tsi'**a«* l^:itf''n'.ii oKs^b !^n«' ->hw v'

'*' ’ -'Vi ‘If i' Vv.'}

Id)

viib ir '\’fe ' ’AtV^ *

y-t'a'i "< Yv1<) f ^t6 » . -’ '‘if .'I "'W 5%«l ‘‘^1 -'\ts j: - 0 - '»' “'•'td ^

:3 -N't I**) «.tt.

!'

'•<!• furovalf. •»!: • ‘iii

'i nt'"**® :i:,n*vh*srrfon---'iai>-3 t f**i

.^T/V. nfc'e fcflAri '-.^ „mr,:,-ri • u h^-.i ,f V)io sffi ^

'

t»it asilqtKi - >i:» i>-''V

fev ' 4.'i> '*»t> - ’*'t f“ t«\C\'-f jftj

^i^:-ii!MLim * • . / -ikiS/iJI-C ''.i

4

j *

I

' f
The error vector is A-conjugate to p, i.e., lies in the A — 1 dimensional subspace of vectors t such that t^Ap =

0. If all succeeding descent directions are chosen from this subspace, we can preserve the exact solution of the problem in the direction p. The second observation is that we can easily choose successive directions pj, pj, . . . such that the (p,j are all pairwise A-conjugate descent directions (hence are "A-conjugate gradients") and hence, such that the successive errors ac, — x*, — i*, Xj — x* are constrained to successively smaller dimensional sub- spaces. The set (p,}, i — 1, . . ,A gives a basis for /?* and x* — x* must be^^-conjugate to all of the {p,}, hence

must be zero. Thus, the process must give the exact answer after at most k iterations. We now write out the conjugate gradient iteration directly:

CONJUGATE GRADIENTS: Given x,, compute ri = b — Axt. Set the initial descent direction p, to be r,. For t = 2, 3, 4, . . . ,do. Move to the minimum in direction p, and evaluate the new residual

Cli pJAp,

X, + Q.pi

(9)

^*1 = b -Ax.tt = n — o,Ap,

Compute a new descent direction A-orthogonal to all of its predecessors

_ n.JAp,

p.*x = '-.I

(10)

The initial step (9) in the iteration is the step in the steepest descent direction p,, as discussed above. Step

(10), the choice of a new descent direction, is simply a single step of Gram-Schmidt orthogonalization, to remove from the steepest descent direction its component in the direction /<p,.

Hence

Pi^JAp, = 0 (11)

Futher the choice of a< implies directly that

rx.Jp, = 0 (12)

The following identities are derived easily from (9) and (10);

= 0;

ri^Pi = r/r,; (13)

r.Mp. = p.Mpi.

The most important algebraic consequences of (9) and (10) yield only to a lengthy inductive argument (not

given here—see Reid [12] or Hestenes and Stiefel[13] for example)

= 0

}foro//y<i (14)

Pi^i^Apj = 0

370
^

- * ''* ** -i^T

to -Uyitf/li^^ Ja**5 3<ii 9V“.sTn»/ (»** -.? ^-j«Pfia*.'*t^ 4 '-f^v '•>’» -i>;«)a^n! ^».tt'i/-;,Ti » • - 7

‘” •‘* ' 4^#jj5 i%«r»*i-.,‘>4i-4» If ;m‘’

. qf :>^i4,..r #'o.i« . , . ,<«. <a .»v\«nch;a^}fe-!)!Jrj)W»--M»'« n^»C|*'W!w4tt • v.i

hr.- ;’« 8«Off«.^ib J^-'.8r,b »« >V

i'4v-itt» 4»='iw»*wi.* <it«i>9Rii«>«i»> fia *•* “ ' ,v

•'’* ~ »*• *^"**;* '

*4 - UiHWiH'i - .' * 'Jf- *

irtVj'/^ x%iit t9>un*

..,1 »iis^j;jhMir,^-,«:t.i->a .«3;K - r -> n>«o £1’/; -i!a>ji;> di>onmn

- ’ •' aK...,v,? .

lbj-<iif/^i »9<1 ^

sU Harr 5>flA : "ib fti >«’ '>' "' 'V'

'f A% +. ,y. ^ i-W*

.' 4 - 1 +

it »

ffiCk<«>V;'jih«nc 4{,» ’•> ‘^^;>50 ^,tlOT.^ nuilcjitt*’ )jJ-“'»«i^i k 3)i.‘aifl'X'il

'Oi,

,fi K^i. .t

,;,jE .^'/odis ^.9 ..^ flo;t;>CM(.a.,«PWtfcb ni <<: >« !i'4:«i!vU ttfv •

o, ^oitwll,wio»f..ilito

* *'* 7’ ' :' 'VvKao«2ni#< «ti ^,>^o>r!|;v.^^s•»-.H>b v.^r u^.i w»«»a.

(!•>

\*I I

0 3

'3 — .'\ i.i'

«(01)|3rtA (V) I5'.^ V Yik.,-> fe^rK>b i-:. .

' ?

-’'

;0 *

(»: 4

-

n}

if < )

, ^'44, v: Ly

0 -

0, ‘M

OTC

^ «
The identities in (14) imply that all of the {pj are /4-conjugate, even though we perform an explicit orthogonalization only to one descent direction in (10). In the conjugate gradient iteration observe that A enters only in forming a matrix-vector product, Api\

there are no transformations done which could destroy the sparseness of A. The dominant cost per step is usually that of forming the product Api', in this case the conjugate gradient iteration is very little more

expensive per iteration than the steepest descent algorithm and it offers the guarantee of convergence

within k steps. The practical reason for using the conjugate gradient algorithm is that we often obtain satisfactory accu- racy after only a very few iterations. Certain theoretical bounds for the convergence of the algorithm depend

on the condition number, x, of A, defined by.

A.„(/4)

* k^.AA)

(15)

where (A) is the largest eigenvalue of A and A.,,. (A) is the smallest eigenvalue of A (Note; A is positive

definite, so x is positive, and at least as great as one). The following boqnds can be found in the literature (see Daniel [14], for example):

Clearly, convergence is rapid when x is close to one (and takes place in one step if x equals one). For well- conditioned problems very few iterations will suffice to obtain highly accurate solutions.

2. Preconditioned Conjugate Gradients and Matrix*Spiittings.

Our basic problem is to solve

Ax = b. (16)

which is the large, sparse linear system which arises from the discretization of an elliptic partial differential equation. We can assume that the matrix A is symmetric and positive definite, so the method of conjugate

gradients certainly can be used. However, the condition number, x (A), is usually very large for these problems; the conjugate gradient algorithm converges very slowly when applied directly to A and is not competitive with other methods.

The preconditioned conjugate gradients method arises, like SOR, from matrix splittings. Consider

A = M-N

where M is another positive-defmite, symmetric matrix, but one for which we can easily solve linear systems.

There exists a symmetric positive-defibite matrix such that

Af-> = (Af-*'*)(M-‘'*)

or

[(3/-‘'*)(M-‘'")]-‘ = M

371
*r -* ^ w «?«<»« _„ts < *JG. .eS(i» „A »«<«<» «i >*>» •>»»» * *5 » «'«* '»><“•''’• ’’"•“‘a **' f . ,i» «... >m W«a««»fc -i#? .« j» •MMMiV •w*' «•'>> •M**"'’’''?’’

, 1T»1 »41.i xTM» .*• ><.>!(.»« 1 -. ,* «4* «.' , sn «n>.l ’.. •.»'

W) 'H-'.'i IwU

y,ii:..,.| «i A r..<.(«) A to IwteKJ »4< ri ,iw..-k 1..1* K .to ,al«(..!,. .i »fl ,* b».M .d-.rf.w-Ki Adj .fc-to .. to=K, to to ’ - « ;-y^;

«--! */

'. i+;\ }

,-!l VKX V <- 1 /

4bw t 0l .i. ... r

a| j.r>«|q ;{>««) Od

' , ‘A

(df)

' ^

'

'

'

'

f..

l-il .M,ait .-fe-iato K" fcd<.ito»to««b »A ,«?.! torfw lMd« ..!vt,,, ...w

:,W<^.,. to ««. - .d. tod, ,^..to,KK.oW

„b«»a .;>w..v Mb...i ,MOe -iil ,p rf<» ttodtom sto8W,«- 1

->.rf

'4 -*^ to

. . w,i «lo« A«:- , . to »» d‘W«'«5 ““ >w *,»/« Aiin-l»W - .ilf «»j»

' '

1

: ^j64i

f *"U . '•SJ

iTe
(This is the symmetric matrix whose eigenvectors are the same as M's and whose corresponding eigenvalues

are the reciprocals of the square roots of the eigenvalues of Af. We shall not use this form, however, we need

only the formal existence of M~''^.) We can solve the equations = bhy computing

d = M-''^b: (17)

and solving

Cz= d (18)

where C = M'^'^AM'^'^, by the conjugate gradient algorithm (Note that C is a positive-definite, symmetric

matrix), finally computing

X = M-''^z (19)

This transformation from^x = b XoCy = d will be an effective method if;

a) the condition number, x (C), is close to 1 so that the conjugate gradient algorithm converges rapidly,

and

b) the multiplication C-yfor any vector yean be computed efficiently and sparsely.

We shall examine condition(a) first Note that

A = M-N

implies

C = M-^'^AM"'^ = /-(M-'*yVM-'») = I- R.

Hence

K(C) =

(/-/?) > 1

This condition number, x {Q, will be close to 1 if (R) is small, which is true if all of the elements of R are small (The condition number is 1 exactly when R is 0, or when M = A). We want, then, to choose M so that M represents A as well as possible (makes R as small as possible), and such that the choice for M allows for condition (b). We discuss a specific choice for M in section 3, the discussion of the model problem. Other

examples are given in Concus, Golub, and O’Leary [3], O’Leary [4], and Meijerink and van der Vorst [9]. We now turn to condition (b); with a formal derivation of the actual algorithm used as "Preconditioned

conjugate gradients,’’ we show that condition (b) is met whenever M is such that the linear equation

Mz = u>

can be solved efficiently and sparsely. Reconsider the conjugate gradient iteration to solve Cz = d, given an

initial guess X|:

(CGc): set r, = d — Czi;

set pi = r,;

for j = 2, 3, 4 . .

=

pi^Cp,

372
b-j.in

' Ki

1

.,( '

. V' '; V

•/.

'ft- 8r

I,-"' ix; '^ ^>14 ^ U»fJ£ f^’''

:. cry '

> (>’ -

“ f-'

'SiiJ r^'ir' .V.i

i:.. '. ’• v.'>r.‘ '.<>^”'''^ if

,. iw>ii x ^.:-» />’•>•••> '.‘hvjWmvti '<4f k* ;*•

y. % V'* !si'if''l'0'i

(

;• ’ >? «

ki 1 , "''ii ti>x itjSir- ,f f>3> ;:.A

' '^ ii': •'^. t: ?(

(iiif'T’ft ,f

*t^^•% • ..>

•i; •v. '.;< . -: .vi*a MS CJ^ •] V# V. w: oi « *\6'0r;'« .1v Uf

:sTi«^o:: ?'if» »' ' •. ,. t w« 4mh 4-, ,(3) * .-ttKlitffi. -Us- • •'-. «•;!. {'

it«5 ..V&J 5A'# #« 7'iji'rO <*>«• -'xJ

< Sj#? -Jo j5 Jij';

’ i «GJ-' ' ' .tft!«3i,S}C$ (iarJji ‘

•

V, -

•M :^isu

. I it ,

• j: I . >' . ; 'V; 5 rv ! M ' ' '(‘iv r: 30.UUw<»? 5

J n{ >• t ., •3/ ,i\ : '•f ;-cd f ,0 HI 'A ;

' H rxmUhfl^f .»•. i ! '•«'

,0 r-l.V", ari ic -^rit *€ ^ tct 'fs--'

- - L - h«si -,fc!

- "•'

..,'} ^ .: . er' '>

• Vi ^

;S f s\ 'm.

k P‘-

r,' I A

^;S

JSr

V

’?'

k-

-i’)
Zi*i = z, + QiPi

fiti — r, OiCpi

r^Ti

Pi*l — ^<*1 PiPi

In the above, the residual vectors {f,j and descent directions {pj have bars on them to denote that they

pertain to the scaled problem Cz = d. Now view (CCJ from the original space in which we solve Ax = b. Define

X, = Af"*'* Zi,

Fi = b — Ax,

Then

Similarily, we can define formally

7, = d-Cz. =

Pt = M'^'^pt

Then

p^M^'V CUT'^p, p,^Ap,

Updating!, corresponds to taking

x,„ = X, + a, M'''^p, = x, + a,Pi

The corrected residual is

n*, = -a,Cpi)

= M''^7i-aiAM-''%

= r,-a,A Pi.

The Cram-Schmidt coefficient/), can be computed as:

P.=

n^r,

r,*/ (Af'‘ r,*i)

n).

The new direction becomes:

Pi*i M-''\n,,+PiPi)

373
--s. •

^ ) »a'4

^V'SsX5 -.^-^ "Sf

'

. M >, jl 4 I '•'' i"“-

-'.'f ‘ />'" ''''

f.*h

“''

_* fwl) xarsb !» c.-.fj » »•»; ~'»^ W ^ :. --. ,,-4«.», !»<<.- < -4*! <imMi»<t ' itifl-t-tstr

~ V*

4 f*S!?T

-..^s,'.> - tj ‘JT ^

'^r. 5

vu'T

-ir '>

*»s v 4, y i4^ T >? /»''

«t kuc. '’ t b^ivy\^»” »<» V

p. ''>?,. ?

^ Ik ,«- ^

4

,.»'' - f.

' .'.-.rkk'::*" ' '"i

.' 't- -‘

('•j} f ‘iftt’— .»

%

A A

< , V 'f '|.. V. ;

}

', y"0

r- %.: %\

'• " u

% «

, ,

t.
= Af-‘r,*, +Pipi.

The result of these manipulations is that we can now write a conjugate-gradient like iteration to solve the equations = b, but whose convergence rate depends on

C = not^.

PRECONDITIONED CONJUGATE-GRADIENTS (PCG); Given initial guess x,: compute

V, = Axi

r, = b — Axi = b — Vt

solve Mui = r,

and set p, =

For i = 2, 3, 4, , .

compute Vi = Api\

set Oi rjui

pjv,

rJM-' n pJApi

update x,*i = x, -i-a,p,

r,*, = r< - a, Vi (= r, - o, Api)

solve Afu,,i = Fiti

set pi =

fl*t^ Ui»l / rjui ^ rJM-'n

^

finally, = u.., P,pi

We introduced new vectors {u,j and {vj in the algorithm above to emphasize the fact that the matrices

and M appear only one time during each iteration, and in very specific ways. The matrix A appears only in the formation of the product (or/fx,), an operation which can be done very efficiently for most representations of sparse matrices. The matrix M appears only implicitly', we must be able to solve the linear systems

Mu = r efficiently and in little storage, and this is the primary restriction on M. Note that the matrix

square-roots, M''^, do not appear at all The purpose of the matrix M is to sceUe or pre-condition the problem

so that convergence takes place very quickly. The cost, of course, is that each iteration now requires the solu- tion of a linear equation as well as the formation of a matrix-vector product

3. A model problem—the pressure equotlon.

The problem to be discussed here arises in a model of buoyant convection (Rehm and Baum [6]). Specifically, at each time step in the solution of a mixed hyperbolic-elliptic system, we are required to solve;

( 20)

on a rectangle R subject to the following condition on the exterior normal derivative dP , , dr] ~ C(*>y) g(^y) on the boundary dR.

374
m

!• "lift

„fc., 0. 0., ,...:i 4i.i . «h» F-

•„<i,„c5 ^4. «i«t8i»J««’ -•>'A;:-Rifc.>; ' a/jiogiflTO^aJB

' ,t^* »= 0

.•Ji - A 3i^' ..tl 4 ^

,-» -a: ,^%lf, 9V[Av.^

,u =» j 4i *'»«

, . ,£ S « "! »i3f

...%•

- «s

. .%,-*» ^ .» » f. J^ >'-'

' ,n'~ ^

' ,v^.j v\ v»

*

. >vk& hS

['*' '

' ' *^ 'J2'.,. is?

' )

, ,4 ,,.«t. -d' *<i-«a<r- < ««»« »< « ’I *«“

,m- u,.'»,r » Jl« ot *« si ». -m ?

r «l i«/i..-i >^1'> »»J»» » ’ ’ '*“*'

r'iifidj.i-:! MJ*»M.jKaa *3 ' -ir«i U »-.i».« »* 1» «»-ri«;>-'T Jto 1 * F.^^'!'!'* J«?'«A . '»• tuS U#«

* /

>*

(<T)

H,e

^ r. <r . '’'

ii.'.-.

• I i t->

•' '

'

.•>. iS«».

^ v-„.

'Hi

is

'^liA^. it '^i. 4

f'ji 4
Here q denotes gas density and P the unknown pressure. We assume that p depends on both spatial vari- ables. Equation (1) then describes a nonseparable elliptic equation. Since we must solve this equation

repeatedly, speed is paramount Were this a separable equation, the discrete linear system discussed below

could be solved directly by the cyclic reduction routines of Sweet and Schwarztrauber [10]. Were the density

and its first and second derivatives known analytically, the problem could be converted to an ordinary

Poisson equation by the techniques of Concus and Golub [2]. Neither of these conditions can be met, which

forces us to consider the discrete linear system in more detail In the context of the buoyant convection problem, we are given the density q, and g and /, only on a dis- crete set of points; the solution P will be produced on the same grid of discrete points. A grid suitable for the hydrodynamic calculations is:

The functions p and /are given on the interior points; g is given at the circles on the boundary. Note that the

interior grid is offset by one half grid spacing from the boundary.

The derivatives in (20) are replaced by second-order accurate centered finite differences. For example.

becomes

dx

_J ^

0(x,y) dx

Note that we require the reciprocal of the density at an intermediate point an 0(Ax) approximation will suf- fice to give second order accuracy for the operator. For consistency with the hydrodynamic equations in the buoyant convection model we use the reciprocal of the average density.

375
i luilPii#’ •’ afinati'Tii’i aW a,i><OXidhtti ufl *-V a." 3. Q

.;;.iJ5i'i,»? *'Al 'Jvije ftV# /• - i->d:~3*^k * U)

yv.l^.' -S'jlin '4'5^-t3K.'*?dd: . * »vti «»

/l.'.^H:] •'s’i^ JO!’ JiW.fFSoy .\«viJS»ib .>' "i:f0t;3 snj if*i

£'art'»^i''('n.*wi K‘’V;V''.^b I8iu sil 'SspM

•ta'’‘'w J irn v4.>uo-^hpki\hi^o,i :,' '^‘<{1* ji;

;!

Ji.'lsfc 9wm »! ^ sr!’ .'jbn.'.c.'' c?<.«if

, :.• :, f.‘> -flT^ X'isni .r, :}r.»^p i.V-W .«t«s<<W.q ^ff,: '50 i> -iwo yiJj ut

http |V>bh^ri^#9.rf^ifi n..- baSw^bMu :<:< .«wi**J&8wb

4*

"(O' - r»'i

Vr!

I,

I •40

4^

1

"

<* O'

i *

I

>

*

yA

V A

jjij •.* - I ; X'51 .mbouof* .’(ft .?,o^».:>uj ;» 6f /, .?*u.'fr < '(45 »^'

• ^sl'i tnci* }^>>l'.Uif, hh'^ Ksd

»oH Ax%uiv-tl}‘h 9tUuU^n •«» nss^m^ --i-ir.yS&^pik (»? ’•/.>: -.y* '' C.Vm *•

ljhig;-?vit’itttj,i

lirjfcri js>!'/ S(<?

e.j{^<K>‘ni

iX. rr;^ 'A- 4 ..)Ci J_

9lA

'W* Uiw “V t’"44'| B f- Mo : aril i-.-Mpsi SW «

. It .,; ;.., -..SAoybm|}{i{ »tb V.!' ^<i?,T7i r»«v'4» V -to h£W.«9S ‘Vlji, Oi :v»?'

».tii '*o «>;'

'>vV' ><

‘

IM
1 2

Define Qo = Q ((i~l/2) Ax, {j—l/2) Ay), and similarly for Pu, fij, and gij. Then the general equation for an

interior grid point i, j

not adjacent to the boundary is

-d.

The adjustment for points adjacent to the boundary uses the second order centered approximation to the boundary derivative: on boundary k (left = 1, right = 2, lower = 3, upper = 4), the terms dk are evaluated

using the first interior mesh point and an image point (one-half grid spacing outside the region). Formally

the terms di are evaluated at t = 1/2, j at the left boundary for example. The discretized form of the Neuman boundary conditions become

a )

( 2 2 = g,/2./Ax = g,0) (22.)

i-h) = g«M/2./Al = gjj) (22^)

(i-) ( 2 *

2

‘‘‘P'") = gi.ifi/^y = g^i) (223)

i-w)^ ^

-I- 2 = g.^*u%/tiy = gii) (22.)

376
s

I 7

'

V

a *

j» r » vA '» vA »:tisS<'6w h*vs M '• * ''••*^

,

. . fv . N f .. '7!>

* f r- . t jl-

.1? ny't, -•i''V:.i-u'p5 V\^nt;4

i '(-.r) |l-T,"r:r'"^'‘'\

'' 'ATA"}\

»«>

m

,b-

. •> .n.n,. «.» w, :^irr‘^-:;r"i:t7L -- ‘V t’ !7 7. . -nv. s.: .. M,r»o1 .<••,,1,91 - .MW ««, /

. , . . «•!- ^ . f , S vl>. • SiUltM

,, ,„ ..no. ^H^ »!'1».'--’ •'» • ••\. '

,i " V,bo« ,,.l.,.».«l O.M..W

{,S2j

L’S)

USiv)

*1 s'.^.A

\ 1 tA

.- t

,0.^'

'•' ,l'

«

'*1

1 m
For a point adjacent to boundary k, subtract equation (22*) from equation (21,,y) which eliminates the terms, and with them, all references to points i, j

outside the grid. The right hand side is replaced by

f‘j 8^

Corner points are treated by subtracting (22;k) and (22,) from (21,y), where the corner is adjacent to both its k-th and i-th boundary.

We arrange the grid points in the order

{(1,1), (2,1), . . . ,(m,l), (1,2), (2,2), . . . , (m,2), .... (l,n), .... (m,n)} and write the equation for each point in

this order. The result is the matrix equation

where T, is an m x m symmetric tridiagonal matrix, and 0, is an m x m diagonal matrix. We shall denote this matrix equation by

Ax= b . (23)

where b represents the right hand side,/, of the pressure equation, adjusted by the boundary data, g. This is the linear algebraic system we need to solve. We make several observations:

1. is symmetric

2. A is sparse. Only five diagonals contain non-zero elements.

3. The eigenvalues of A are all real and non-positive; is a negative semi-definite matrix, generally of rank mn — 1. Hence —A is a positive semi-definite matrix.

Although we could, apply the method of conjugate gradients directly to —A, convergence would be very

slow. O’Leary [4] and Meijerink and Van der Vorst [9] suggest several different approaches for creating scal- ing matrices M to use a preconditioned conjugate gradient scheme. One general approach is to coDsider

that A originated from a differential equation and let M be the discrete operator from a separable differential equation which approximates the pressure equation.

A specific choice is suggested by Concus and Golub [2]: Let L be the discretization of the Poisson equation

V»P = /

with Neumann boundary conditions (on the same staggered grid). Then

377
.-vrjj (, /S) K^pmh»<r^n ar JJM#;/-^ f^Jjioq r< ,,

X-fl. f»s ).,» 5v>.o4)rf:;jIi Siit .Ihii -i-a' jjbh'wo \.,*,e}rr)pq &j i;,.''.;'^i tU 43‘ivf .t.ntjo) ,

*S“«\

«Jt /tjci t ft;t2-£irbii ;' "> 'j’t'n "‘M smiw insiiJ-i j (,§S)b0i! <[4 Mb,»i3's.3» ;;sa?o9

puWpAi (tl V s?.'f'Oj.| ki;^^pt •’W

«i uijtJo 5!i| arfj Oia ” i>f!* {{n^ ) , i • Ut,B . - ‘.' A'“*<

. - /i, <*.) ,* r,I)>

t^fltiypo. xh. :* ' *;.it d* llp«':'” -irfT

..;!' fl: ..!i. w * ;<. ux- >S >l>i>«a ,*iaJ*att #7sr.<.’^&sbhl 3r.»»(;tt5»t« * w ne m ,t r;^>AliM

•(«i 0£>i|!iaUp‘> ^iiii»ni

•i ,*'xb:xt4ri-,vu|»*ii ..,«»•-«<»{>? . n*»9-i-.; v.J io ,'\ ,^‘^t ..

•• <'»’

‘*’*S.«'-i'> kT;>V!»{: 'vjLsfii •J.rf* '»viO'? 0^ ik»60 '/*» J1*8J\lW t| J-il t '>*' f

?'•/ ?fSJ«i W ^ . i

'>3^43* •»<• ' i »USi*,V«-''b 'i* K ,'i

.xh^m Mi8-<a^K* >«--5 * al isr-xj-nts ksnr K»<m« »*

8^ biupw 9(jr-!j|fi!Siv -.i-so .ti*" oJ a(^'}*k.>^ 1> 3'!3W>‘'* b-tf03 *) •

tt ;'S^ &08 3inh^ii;.M 'i

] :<v4rfe

• i.t Bi 4tr.f'iqm ipO iax^jyrj% fe .’^nosM

'- w'-'k s^j»iPnIfe,jM<i 9>i' U- i -4^jia * *s •<u hxm.igm

.' i; ;/iJ )o *4f l38i 4i^y«kO hWaH^Jva - A

' A

'

‘

.•^^1r.4'ii% t'j.T.-ssaJ''. »h:oa*jw!J a«i>)«vr>t!ib.no^ -oitlHJWod n.fliai(ao»H'irti - vn
L -

3

j , c,/

[—

c,;

I

I c,/

,/

I

Y T- -1

I ^2 !

I I— 4.TM

1 1 i L I J

(24)

where B. =

B,=

with Cl = —

Oj =

Cj =

04

c, =

Cl Oi Cl

Cl Oi Cl

O Cl

“oj Cl

Cl O4 Cl

Cl O4 Cl

0 Cl

1 1 (Ax)^ (Ar)^

2 1 (Ax)^ (Ar)^

1 2

(Ax)^ (A#

2 2

(Ax)^ (Ay)^

1 1 (Ayr (Ax)^

O

Cl Oi O

04

Cl

Cl

Oj

378

We assume that we have available a good subroutine for solving the equation

Lu = V.

e.g., subroutine BLKTRI from the NCAR package of subroutines for elliptic partial differential equations

( 10). Let be the diagonal matrix with entries

dkk = V u**/l k 9

the square root of the ratio of corresponding main diagonal entries of A and L Then

M =

is a symmetric negative semi-definite sparse matrix whose main diagonal is identical to that of A. Hence, in the splitting

A = M-N,

the matrix N has zero main diagonal and non-zero entries on at most four off-diagonals. In the preconditioned conjugate gradient iteration we must be able to solve

Afz = r

This is done without excessive storage demands by.

a) compute w = Z)*’'* r (Z) is a diagonal matrix)

b) solve Lu = w by cyclic reduction (BLKTRI)

c) compute z= u.

For computational convenience, to avoid the repeated multiplications by the diagonal matrix or its inverse, we replace the original problem

Ax = b

by Ax= b

where A = AD~''^

b = D-'<^ b

solve Ax = bhy preconditioned conjugate gradients with L as the scaling matrix, and finally compute

X = Z)"*'* X

This is the approach actually used in the computations reported in section 5.

4. The Preconditioned Conjugate Gradient Algorithm for a

Semi'definite Matrix.

In our discussion of the discrete operators A and L in the previous section we have ignored one characteristic of these operators which renders them unsuitable for direct use in a conjugate gradient or preconditioned conjugate gradient iteration. The conjugate gradient algorithm requires that/f be a positive-definite matrix; otherwise the function E may have zeroes other than at the solution of the linear equation. The

379
,<3 "' til '

. \

"

.'aiJHn'wlfefe -> -ftSl 'Wi.-JC'-fdar,

'-f'.'ir

»»ilS :«»43']x' i i^^«b s».4J %d ;l3-i .

- - iX

fetU tb ’S'? >-*^i3faa hac%uh ai»0 ;^ftib'art>'q».«.w. W ««»*t

Hi u'

ti >iS^i©''Jii 1^, 'ici .*.;'i]! m fl/sis3 jnimt avbfejj

M-U - )v

Jf^3l}5sri%. ^'il

wo1 3 sob^ Jfc fro >f3j’^!.i» ow *»o<’ hn£ (^.\ntv. '.'fns *4jd V, >«jj'i.ri '4J

rrjij? 01 3H4 ‘' wlttfViu twiKtcfrlxrormo ^,‘U u1

•t*i eb«to»a'*-b 3]ge >atfj 9<iifM~r^ ,r a> {fhitm ., M'vi) <f-'»-<S • (»

-’- uA'iVkwJ (i

44 » i 3tti-qfo.'-,a h4i 10 *' Hi xii3aric! Urrttigxib xl f0iri.iaa.Uiq[h},i?K 3^1 b.Vv n| , |j>aw36iMq«ftt*a 'tft.f

laisl^jviq Jani^jSo n*! aw .''ins-mi

^ « Silv

d t» ik fij

a *

tiiyqi/o- ^flstui bn« ,«Ki#i}‘ 5«r^w«uf d»iw /.tA^rrtrtr) fooB.x?»bi!3‘j?3?«> id i •f,|.'»'4«V6

« ew? s'5s« fti bsneq'.r *<iofj*?f»'5qB4Ki3n”i m b'i-ijj <.i “adT

V?- wsl A w|wjcI> ?? v^Hl i

: fii' -frtVinjii ^ # aoUa in azoh oirri e>4i A l»fl« ur« *!

i|i »%.. i»«ib •«e>>«rfdM*»*i»fJ. «« fj*.3ijS V/ :iil«^ «.'(« L f «ivfe®w®Jiiw9ili*»8 9J»54«iao9 w-fT' 4o«'-*'A3^li hmhg^ «Jasj|w.^ief> or'i'-*b WT !jiiJ 4’S fldii fxsM't »<4jo swiuf x*«r t- norMai, «H w.»^^30^4» ;t».;n ?oi
algorithm becomes transparently a maximization algorithm for negative-definite matrices. (There is no need

to change signs implicitly or explicitly to solve linear systems involving negative definite matrices, e.g., the

discrete Laplacian with Dirichlet boundary conditions). However, our operators A and L are both negative

semidefinite; they have negative eigenvalues, and also, one zero eigenvalue each. In this section we will extend the theory of the conjugate gradient algorithm to allow for the special case

of a semi-definite matrix with known nullspace. We shall then extend the preconditioned conjugate gradient

algorithm to allow both A and Af to be of this special type. The first part of the section will be elementary for readers well-versed in the conjugate gradient theory; the second part contains some new and unexpected

results. The problem is simple: A is a. singular matrix. This is shown easily by noting that whenever a term appears on the diagonal of A, the opposite term ~dk appears on one of the off-diagonals. Hence, the sum of the coefficients in any row of /f is exactly zero. But this is the same as saying

Ae = 0

where e is the vector(l,l,l, . . .1)’’. In general, Ax = 0 <=>z = tre, where a is a real scalar. The singularity of A is related to the Neumann boundary conditions for the pressure equation. If P is a

solution to the differential equation so is P -4- c. where e is any constant Similarly, if z is any solution to (3), so is X -f ae, where a is any scalar. But this is equivalent to adding the constant a to each point z</ of the

solution. The singularity of the operators also implies that not every system of equations has a solution. A

system of equations is consistent if and only if it has a solution. The characterization of consistency for these operators is simple to express: The pressure equation is consistent < = >

(25)

The linear equations /fx = b are consistent <“>

b^e = 0, that is, when b in Range But

b^e = 0 <-> I b.-O

<=> j/y = ij(g,U) + gij)) + + gli))

the discrete analog of the integral equality (25)

Further, even when the equation is consistent, the solution is not unique. There is a unique solution of

shortest length in the usual Li norm. For the continuous case it is the solution with mean pressure zero, i.e., n.p^o.

In the discrete case the analog is x^e = 0; again, the mean (discrete) pressure is zero. We shall now discuss the modifications to the conjugate gradient algorithm which would be necessary to obtain this unique solution to a consistent system of equationa For generality, assume that we want to solve

Ax = b (26)

where A is symmetric positive semi-definite of dimension k with known nullspace the span of (n). Hence, the rank of A is one less than its dimension. Further, assume b^n = o, so that(26) is a consistent system.

b^n

(note: if (26) is not consistent, b = b =— satisfies the consistency condition, and any solution o(Ax = b n n

is a least squares solution of(26)). Let the vectors {n,qi,q3,q^ . . . ,qi,} form an orthonormal basis for P*. Then Range (A) = span

• •

. ,q*}

380
b' *p •» • , Ksms^ . r

•'

,;4T.:v "

^' ' '*' '

.. :;

-ilV-ft v«»'-

'''

' '*, ;'

's. ;;‘•S^' 8

Siili ri M9X -- .,^ -

• •• V -,;*,b' *i i.^Bw»'(|'»n"

• >-- • ^ - , r^/aiP iS . . ••' ‘ •*

‘ *• •' •*

^ ;^*.Vo!'^*>' -6

; UfkH* 931 kV'*

.

!# ?fU ' '^>' ''fSiTOJtSf. “'- ^•-'• i'"’-'’** ‘ ' ‘*

f V 1

*

I M*:‘, V»* ^ >

•^

' A* >

' ' 'AV ' ^ * '** '

'

• . .'i * '- -A?*''"

. . • , •••.,.V-*» -M. : 4ifi - cae-^’-rt; . ^

, - . ,, , ^. * ., i:. V/r.-::> 9'i. ,

• •

_ i

_ i

i r . .

^ V. V- ;i»Wj-a>15;V - » -

;

-

. . .. . . . ,t6rs

- '- ;t* - ... .V- - --'S '.!• X V -’S* ii'llWtf f-rtS T- ,. "

,

¥«i^v .-,1

. »• . X - •'••.sii'i

'•!> ip.*'i. ! "i! •’• <»> tU'iUW' "'9 •T -^' ^

)*j2 ^ ^

*‘ *4 /'

_

‘

-- ‘C ii ^

=\iw>, V

• • u.aD' ' V-

' '' - ''

, ,. f , -rij- n'i«5'

•

>}-.=i'!'Xur 9ii‘ s V -lojti-bp ..’l ii'i'*!** ••*'»A?‘’'...' '

,..,',o ., I • ,nn'>u * •^«‘^-' ' ,iig •>?; :.•)'

f " ‘ ^

' /. -M •..>>

'

!’}

'

I

\ ^

.'4' »1 ;

.{; 'riw It?' ' '' '" '

" 4'^ ^

...a .. .

.;!,,i^^ , 4V .vs, .<• I,/’'' —

^1., f. '

•..

'

, H.'?. ir' ' «i ' »» ’« *'• ’ ' ;•=• «'••' _ I 4 t

Ji

' ’

. %r \ \ . .

. .ss ... •' .^^7 ^ a ...d

riKcj^ - ‘

t«.v>

•

".jj-,iia.io9 lo**

‘^^' ’'^

,u, .

• .*V«s^) M
Let Q be the orthogonal matrix ( = Q~')

Then

^ = (n : ; <73 <7*]-

Ax = b <=> {Q^A Q)(Q^x) = Q^b

But, by the consistency condition b^n = 0

Similarity

Q-AQ

fj

it-1

*-l

Hence, (27) really takes the form

0 0 w 0

d.

2] —

d. 0 B •

2*-l

(27)

(28)

Clearly w is arbitrary in (28). The equation holds whenever

Bz= d (29)

a(k— 1) — dimensional problem. All solutions of (26) are given by

where z solves (29). The unique minimal length solution is given by

By the assumptions on A. the matrix B is positive-definite and the conjugate gradient iteration can be

used to solve (29). The condition number

*(5) =

A.-, (B)

A.(B)

A.(^)

UA) ’

381
(' ; s»-

)

V. vrt- f»^ ^J'if.j

’ xt* ' ”1

» .4 •

4*^ ^ i- V)^ y - o

0 u= i'tv’*.? ,'. <i!5.i/«-et) pmuht(6» >rS y<f^n-H

f 0 } .. l->!)

.'> 1

<J. 'sj.MXfi?,

, P-i.. ,

^ ,»1 - ’)n yjO'

. «

r

! *» 1

,-.Vi

»S

[ t

tt

J L . J

>‘*vnns»<fw eu'hn’Mr, o.-fT • .£)at .'tg-uid •» u w

.ii

rtS'fi^ •' ii,?' ifl'i i(i-fq |«sraii:M. «n:>' if —A)*

: 'lo M J'

ntv.g u nv'ii'f t* rf!jf!*»l Ui.-r;fut ti V ^.-'oy ,'>»jT .(J'i;. >i-»viof ?, §i:if.v r 0

rvjs^ -

>aO'^ :i<lt fcifij tOvnrJy'‘-fi'/, '•= mil ,K n. rrtf 'i'itmift ^dT »«k»f o, bS’W
(where we assume the eigenvalues are ordered algebraically) governs the convergence of the algorithm.

We now show that we can solve the consistent linear system (26) directly by the conjugate gradient algorithm, with convergence rate determined by x {B). The proof is elementary: we show that the algorithm,

when started with an initial vector x, and a right hand side b which lie in the same invariant subspace oiA,

solves the problem while remaining entirely in that subspace.

Suppose we have the equation

Ax = b

with b^n = 0 andx,^n = 0. Then the conjugate gradient algorithm, when applied to A, produces vectors x„

r, and p, exactly equal to '"o

x. = (?

n = Q

and

fe]

where z„ f, and p, are the vectors produced by the conjugate gradient algorithm for

Bz= d

with initial vector Z| = the last 4—1 entries of We note that

Q’r. = Q’^k- A,.) = Q'k - (?A (990*, =

- [

•••“

•j

.

where it is essential that b^n = 0. It follows that

Q^P> =

So assume the required properties hold forx„ r, and p,. We shall show the iteration preserves these properties for x,«„ r,ti, and p,ti. The first step in the iteration is to compute

a, =

' p.Mp,

’

which by induction is

0

T "O'

_ n _ Qrq r, ^ Q- T "O'

h Q-AQ -P‘.

pJBp,

'

382
OJi-

' (toiCK'iti *»}«., ;*rt1 V-* • o}t:,i< * ''>}«?J»lt<i> »nS 'V«-. ‘> 'V /</ Udi ,*odi •HOti 9-V

cT!d»*W3U hrh u'w :\pUa>' ei W'vwf Si-T ..^) / 'i A lb :'('*' w.’w Mdfn

'*• jsii 3-rvst{it>>‘fH ii-,4)»t tiJl ni -''.i 1?yd*r 4 ••; d.i'igr. but ,i lyw Jsftmii cii rf" 'w h-^fiais

-f. 'Vtif -i-viiiao ?*rorjr- *?!(*'• ‘JicIwiftiHdifttq

i '>4i S-tb-A -i’ff 3»-0(|qy?

e =5; i.V,,

o.* I ‘ -'^iK ',1

hrl^ - ‘

I—

^

m-

•— ••v

I f> »

• f hcoij.!:. '»Ui •'|ii .';. ;iUl {'. 03Jl>L-OlV| ’.<SJ' '^"y P*i-. Sft' K

b

' taf'j tiU'a b'^ X ^1*9 fl'i.'wPS 5c; ,-j: iiUfiti! d»)tv

L ' i L'"^ j

j-y' I ^ ^ f.-th -

jcjlt «!> dJc^ jI Mr n Vi J's ?>< ft

:.VI

j<* ri' -'iis '»!' r4it uiti^ i!i\(i* .• - .r-i ^'ns. } ii»4c\-«/ is>"’'.‘<'‘*>j'if<j| ;, dj vftrjiiiaiij*- wv,

«>i N s^o'ivfciiJi *»ri' a< «f.*-i» /yv*^ 'i’T ri..'* '•

' t

t’ noifrtsiitiH (frwdv'

«1 r 0

j ^ I

; A

ki .... dOv)

0 "!
since Q^Q = I and

Q^AQ =

Hence, o, = o,, and it follows that

x,*i = Xi + o,p, =

Then

r„, = r. - Q,Ap,

= <’ [7,4-d = [•£•]

That Pi = p, follows from exactly the same reasoning that showed equality for the numerators of o, and o,. It

is equally easy to show that

Pi*i = r^, + P.p, <=> Q^pi*i r

0

] _

’ 0

'

[r,M+/3.pJ

Thus the conjugate gradient iteration will succeed in solving a consistent system.

We should note that the condition that x^n = 0 is required only to assure that the solution also satisfies

this property. If the minimal length solution is not desired, this condition can be ignored. The condition that b^n = 0, thati^x = 6 be consistent, is essential If the system is not consistent, the initial residual r,, and all successive residuals, will have the same component in the direction of the nullspace. Suppose that b (and r, and p,) has a component/ • n of the nullspace. The recursion for {r,}

r<*i — fi a,Api

shows that has a component y

• n of the nullspace for all L This, of course, also follows from the property

that r,«, is a residual vector for .>4x, and b. The directions {pj, and the approximate solutions {x,}, have components of n which increase with {(in fact, rapidly).

It suffices to examine the recursion for p,

p.*i = r.M + PiPi

where /J, > 0. If d< is the component of n in the vector p„

6i*i = (y + Pidi) = iy + Pi (y + Pi-i

’ fJ.-i)) = • • •

Thus the direction’s component of the nullspace increases. At the same time, p,+, is shorter than r,*, in the/4 norm, so the relative component in the direction of the nullspace grows. In the limit, the directions may

become nearly parallel (they are still A-orthogonal but/4 does not induce a metric). We can see this also by

looking at the limiting case when a iteration is started with an actual solution vector. The residual vector (which is not a descent direction) and the initial direction, are in the nullspace—the initial step ai is infinite. The last example given above implies that the convergence rate for obtaining the least squares solution to

383
- .1% *

I': "I

tr- ,,^ J,

ij ,;^ i,m M% no?«1>srtun ./ '. ' '»/C3 »«•.«* vj?^*a fne?5 Si - Amn

<~> ,v'

mdi sJ v^.»1 vClSMiS.# t*A

.ai*‘j«v«i 8 i.'vin*’ «i Hi^iotK/ua rn5rt;50'r]!»?w^w*u- ' ”><<1 ^ud i

^k,5.}SA oalii <l<ST.»r\i» 4{?i !Kfi'} ‘.'IVW^-O- ^

aHj bff'. ,f4 “ t'f

tfiiit i ,(ii®St^<t«l/i'«|t*» 'i:dJ '•« iil its :r<K*.,v, /f?7.<34 »ijS3

J|., u0» .> Jfwtisjt" UHj.:i ’.ir *); ';- •'»«» fi «Jti^«’> «. ^<1*^ *h.tfiS .0 « &V

[ ':} t*' ‘ifi H . Y ? *. »fi/< ^,-

, ®

x:^ijow »:M tnmi sv?<-‘l!oVoa?>- ,«d? 4 6* vii ’• #

m*»;. srd)-^ j.ij •n«r‘;r^w<jii »ri< iu<4 . :-ii' -'iT i »#«» » “< k>'s ««?

i>*ifesqsi

!' .' fc'S'' -fii >’-***SU'v4s n

i<5 '«“' 'fAi Si -b jl .0

i (f-i/.ib t .\'4\ * ^] .' H) t>Wt-+ • ' ~ I"

*>

t'. fiii ovjo 48«; ..,iv Vo *>* ' ' •nv'>

Vfca vu'.f ari* lm»J ‘‘'>V n'» 'rjs«}iit;'f''n 'io :i> « imii' qunr'

X‘-* 41' ; k.i

('• TO- .\'{jtl". 5;Ui vrJniJ fe-Us 'js^.
an inconsistent system no longer depends on k (B). The convergence obtained in practice may be much

slower than the bound obtainable for a consistent system. In practice, we are interested only in minimizing

the residual, which we can ensure by working with a consistent system. In actual finite precision computing,

the residuals and directions may wander slightly into the nuUspace, in which case we are in the same situa- tion as if we started with a slightly inconsistent system. The effects will be negligible unless the rate of con- vergence is very slow. In any case, the effects may be suppressed by explictly reorthogonalizing the direc- tions Pi to the nullspace.

In the preconditioned conjugate gradient algorithm we replace the system

Ax = b

by

Cz = d

where

C = VAV,

V some positive definite symmetric matrix. In the special case of a semi-definite A, a natural choice for a scaling matrix may also be semi-definite. This is the case for the two operators discussed in section 3. We

have two possible cases to consider. V positive definite and V semi-definite. The case of a positive definite V is little changed from the ordinary semi-definite conjugate gradient

algorithm. We take M = (J'*)"', or more directly, V = Af'*'*. The rank of the matrix C is k—\ and its nullspace is

span

where denotes a non-zero vector in the nullspace of A. The convergence condition for C required that r] and pi be orthogonal to The former condition will hold ifAx= b is consistent since then

7, = M-^'^b-Axi)

and

(b-AxifriA = 0

The latter condition is equivalent to

Pi 1 MnA

since

Pi = M'''^ p,

But clearly pi = M~' r, is orthogonal to Af since r/riA = 0. By induction, if p.^MnA = 0,

Pi^JMtiA = (r,*/Af‘‘) Mtia + Pi ipi^MnA) = n^JnA = 0.

XJC)

Thus, convergence is governed by the pseudo-condition number .

, the residual vectors r, remain those

of a consistent system, and the coefficients o, and /3< are determined by an iteration remaining in a subspace

384

of the range of C. However, the scaled directions /?, are allowed to venture into the nullspace of A, and

hence, the solution vector x is no longer necessarily the minimal length solution. This may be repaired easily at the end of the iteration by computing

X* = X —

nA^riA

riAThe other natural case is one in which the scaling matrix M is also positive semi-definite, with the null- space generated by a known vector n*,. The linear operator corresponding to Af'* in the definite case will be

A/*, the pseudo-inverse of Af. (For our purposes, we will need only a method for solving consistent systems

Mz = w. Our knowledge of the nullspace of M then enables us to compute the minimal length least squares

solution, M*u, for any right hand side u). Formally, the matrix V appearing in the definition of C is (A/*

)

so

( 6)

Several conditions which must be met by A/ are immediate. Since nullspace (Q 3 nullspace (Af), the rank of

Af must be at least the rank of A. For our specific problem rank (Af) must be at least k~\. Otherwise C has

rank at most k—2 and cannot possibly span the entire k— 1 dimensional space of possible solutions to Ax =

b. To guarantee that C has rank k— 1, we must have rank (Af) ^ k — 1 and also that the nullspace of Af is not orthogonal to the nullspace of A. If the latter condition fails, we know that lies in the range of Af (since it

is orthogonal to the orthogonal complement of the range of Af). Hence, by symmetry of Af, lies in the range of(Af*) There exists a vector x such that(Af*) x = and z 1 nv We would have:

C nv = A = (Af*)*'* /f 0 = 0

Cz = (MT^A ((Af*)*'*z)= (Af*)*'*^n^ = (Af*)*'*0 = 0

Thus, the dimension of the nullspace of C would be at least two. Recall now the motivation for the preconditioned algorithm. The rate of convergence of the conjugate

gradient algorithm is determined by the condition number, x(/f), which is large for most discrete elliptic

operators. To accelerate the coverage of the conjugate gradient algorithm, we replaced A by the preconditioned operator C = Af'*'* where we presume that x(Q = 1. Our presumption can only be true if

>c(.<4) ^ x(Af), i.e., the preconditioning matrix must have roughly the same poor conditioning as has A. This

requirement follows from the inequality

Jc(C) > max { x(id) >c(Af'*) 4A) )

where we note that x(Af** ) = x(Af). A brief proof of this inequality is given below.

x(C) = k„„(C)/ A,„,(C).

However, the eigenvalues of C are the same as the eigenvalues of Af'* A. We can bound the eigenvalues of

this latter product as:

A_(Af'*^)5^A_(Af'* )

• A„.,„(^),

A.,„(Af'*^)<A,.,,(Af'‘ ) -A_(^).

385

It follows that

A„.(A) A„^M)

= xi^t) / x(A).

The other inequality above follows by a similar argument

We can obtain suitable preconditioning matrices for most positive definite discrete elliptic operators only

by using poorly conditioned matrices. The required poor conditioning of Af may be even worse in the case where both A and Af are semi-definite. The preconditioning breaks down if

= 0.

We shall now show that the preconditioning nearly breaks down, in the sense that Af must be very ill-condi- tioned, if the nullspaces are almost orthogonal. Assume that and have length one, and that

= d,

which is much less than one. We can write and Af* in their respective eigendecompositions

A = UD^ U\

Af* =

where the zero eigenvalue of A and of Af* is given first Then

C= M*''^AM*'>^ = SS^

where S is defined by

S = V^UD^'>\

For each of the matrices 5, M*, A, and X, define the condition number of the matrix as the condition

number of the matrix restricted to the orthogonal complement of its nullspace. Then

x(S) =

In the above equation, the matrix X is the(k— I) by (i— I) matrix obtained by removing the first row and col- umn from y^[/, that is.

y^u =

We now note that the inequality

k{BC) ^ max

x{B) x{C) l x(C) ’ k(B)

j

holds for unsymmetric matrices B and C. (The proof follows from the triangle inequality for matrix norms.

||5||<||5C|| IIC-II.)

386
A

¥

'S?' " wj'

ii'V m

))H4| ist a

M

Vi.

I :'.’.»V"

m %

^ ' v.'i^ IwtrtAi'jiikMAa ’ftccr^ 1

% ,JP'

,,i:i iM sJa^a a<t i^i4,r.4!5|»ffl»^» to^fj s»«fT ,.i8?>»«»*» bartawii^w t« r; *

__ » t <gJ«

|S0! n**t’*4f

S3T

•<b.w>a.tU larft ^^iit iw 41’^ aiii we.« wca M»W t,

' .. . 1M t V . » . X « A Xi^ .t^.. M»A Aa^M^ft»tiiri#f >«ixfv n J*iM>8«rfHU JM«fvlA-a^^ afti !» .baiwfet

avrraay*^ x« ^4»e# kal.h# B#a ,

:j,ia

IW

if»

..»i

.A' '1. ' ’f(, ".'^ '

.

r K TM

'* W- fi

IG)

b<?i»’l'(Vt>' jdl'Ti aw«t.w- K-

^4

f;

' ’>:- %^mm ':i^

Ji

'

.r. %

.fj^j

ly. 'M

^tfsio^ui odi y**t*

A'. 'ii» Hwa,-safiaa^!P^'.s??i W'w*’' „*c a "' ^ I'' * ^>1 ,'jri|ia: -,v

'

'

, jL ® ; • ‘X<^'.‘# ..'

' ,. j

Mamto-i «,hii^!.i »)»«*< wt^i^wHoa )««?i«n> 3 te ’JTM~'*«'’ ll' *“"f

, i^¥' life

UmM'

Em'inbl
When we extend this inequality to products of three matrices we obtain the relatively weak result that

k(BCD) > max

i x{B) K{C) k{D)

I

j 4CHD) ’ 4BHD) ’ 4BHQ j

In the context of our preconditioned operator, only x{X) is unknown. However, Alan Cline [11] has shown

that when d«l.

x{X)=\/ 6.

Thus, the condition number of the preconditioned operator C is bounded below by.

xfQ^d / 6Y /(x{A)xiM)).

Since k{A) is fixed, this implies that x(M) must be large whenever 6 is small.

V. Numerical Results

A code, written in FORTRAN, was developed to implement the preconditioned conjugate gradients

scheme discussed in previous sections. Care was taken in the preparation of the code to make it portable and

to introduce many comments for clarity. The code has been run successfully under a variety of conditions

and has been compared with analytical results to determine its accuracy. In this section a description is given of some of the computations used to determine the performance of this code. The model problem, the pressure equation, was discussed in section III. Special cases of this general non- separable elliptic equation were used to test the code for accuracy. All production runs of this code were per- formed when the code was imbedded in a larger linear or nonlinear fluid dynamics computation; timing

studies were performed in such an environment.

Within the code, two tests are used to terminate the conjugate gradient iteration; these depend upon two

specified parameters, the maximum number of iterations (less than or equal to 50) and a maximum relative residual, c. (The relative residual is defined as the norm of the residual divided by the norm of the right

hand side in the scaled problem discussed in sections 2 and 4.) In all successful computations to date, the

iteration is terminated after a relatively small number of iterations by the relative residual norm satisfying the criterion that it be below e. To test the code under the simplest conditions, a Poisson equation on the unit square was discretized and

solved with homogeneous Neumann conditions applied at the boundary. In continuous form this problem is

-|^ + -|^ = f{x,y) = cos(xn x) cos (in y)

on 0 < X < 1 and 0 < y < 1. The boundary conditions are

= 0 atx = 0 andx = 1, ox

= 0 aty = 0 andy = 1.

The solution to this problem is

^ ^ ~ (in)^ I

y)

When this problem is discretized to second order accuracy on the "staggered grid” (a grid displaced one

half incremental unit 6x in the x-direction and one half incremental unit 6y in the y-direction) as discussed

in section III, it can be written

387
’M190 :. > {‘'T' -Mij i{> iK^vhh iq i'jj ;IriJ “jw n**!'

) r:\Hv,y,

^ ' -

'^cyj

'" "

nrfi M ict' , , -.fcIJ ni^k .- --wwyH .ir •t-ixrr: -. :'/^ 'v fifto ,n,',!cWCfO bf»r.«>;i:,fenaa.'^iq lyo \a - (b «J J -. c rt.'-'Hv; #sri4

.h \ t

'’f'

.(0<,,ix.'‘- bi)\ -U \ D^»

'',;!'i . '.'(ilii.i.. -.V jX»W?; ('rjf'icjmf -iiHj ,i,;'pr •• ',V >X ;•

i. .jsj'.j”-, : :>Ai v' I »' fl! yr>uirv '

Li.i fX'i J ; V 4MJJ nj 9! .03 i"-b !c v?Ti i •»{! 5- "e 'ii.I » -!>,- 'vifc^' ftiMjjys’f.; ^ / yf*'i'5j ‘^TPi'i'Sv

) i.' yu.*«1uv « i •' ,W f .'^h tiiLiji ’'boo m{T Vi.Sfci". f. i y»tx}r. ^•

ci fcfi.'J: . ' ,fo$J^o^ias ;vi i'^nifir •»*>i» cj >^sb;l'y^ •. ''ivySsfyu hi> j^rcs,*? bn .

.:.>(x,,« *' ’ aTR : S> b 4>J fc*«vJ ;'‘i.'TWOO 6,"< < I0 lo nstv'f^

-ii!7»3 \r. 1 - .^/^t 1 ./SfBO <» ; I' luu.ji; j?;t. ^ *..-?> ivbOm )dT

'1 :''i «4.uf» :>i ub ••• .., /.!} is- t *jj 5y.#«ii dts*- *!<{»*

f yfc I;*),,)} ’Ji":!,:,ufr'*y? m \n::n,- ' ', '-fertr) ,Al « K^euwl

T/rr^.ni.jfjftiij;-- f„a Ao'Ji ffl

- vf ;a.*'ybi5T5 <*t *4: b mf f !’;?•» »)wt , 'ti-^o M;i

<iv^4,Itn D/ii. (C3,by .at/po, 10 n&t!* x? vvs.jpnn

a: I

• ^-'on .flit im{ bnbfvSb !-;i.'b{)'.ai fit'.:, Lnujw ofit CS' b’tirtil>i> :ii Iftrbim s-yaisv.rt --nlf) ^4 j'wybfsan

yji'l yUl, •; >,*' H'''. 'isiyqcrf,-. f' *y35' .. i\$ •

' ' t >« , •iauli’tfyH r.i fcjMHif'iix, •;» ah’a bii«d

x<: ' CUTJ'.l li.uli.'OJ :>V(J'1'»\ iiJOIti-IMli <* UriCIl

I '.’i 4 -‘»a I - . 'ifb ai- ' hnu^jiipo .|^<'SMp >:’ >wi'' '

:> ,-fr' . >ilt T»yJ)iT4 T»’b<:!:i v'M »; jt» .. i

f.i (n .*': > i'irtj I ..' < /•(-'•'•Jtwx? 7MJ jC i>^i’-' si '" <

i't >(U<(07 (i Vy>}i :•/ "t? \

-- *•

/* Q IV

,J - j;bt'&

‘»l« 'y7i’ii.illK'"i 'I ! i . t f > 0 b ., [ > X “ 0 Uf-l

, ij r. - xH

• I — V’ ' ^ 'f i ; 0 ^ '' \

; malJ/r, ‘ j.v* 01 ti! btA' 1

' ^»i'T

i ‘

-. t'C’itU ««?••{» .Tf'x) *»<»••• H'”f (’ir: - 't?i)

V ' i' . 'iq.-:;!! L.t^' fcV'*bh^ uiP? y/'niiti'-ivix. b7(,ir>.''3 pj k>»{| 0'>d\V'

- ttf •$ tnoifSTMb^- ‘.>‘P I'i .-b Ji i.: UU/yTiy: loi ":u. . fcmi poj)* •i-.-j b:I. y,“i s6 !«ts Jj»4«-H0'-i

3 '^ n«a ii ,i«'i najyos'it *li
Where

1 , o- - X

1 {Piii*i 2pij + p,^-i) — fij

fj = cos [— (i - V^)] cos [— (/ - V^)l

for

1 < { < m and 1 < y < n.

Here dx is the mesh spacing in the i-direction, d* = 1/m (m is the number of mesh cells in the x-direction)

and 6y is the mesh spacing in the y-direction, dy = 1/n (n is the number of cells in the y-direction). The

boundary conditions are

Poj =Pij andp„»,^ -Pmj for l<y<n

P,.o = Pi,i &ndpt^^i =Pij, for l<j<m

The solution to this linear algebraic system is „

' ^ E-- 008 [!^(i-l/4)l CO. ii-m

^2m sin^—y

+

^2n sin—

Pu =

for 0 < i < m + 1 , 0 < y < n + 1 The solution to this simple discretized Poisson equation was computed using the code, and the solution compared with the analytical solution given above. A small test problem, m = n = 7, was used to determine the accuracy obtainable when t = 10'* Comparison with the exact solution demonstrated that the components of the solution vector obtained from the computation agreed to at least six significant figures with the exact solution. Generally the agreement was much better, being seven or eight significant figures for most values of i and j. (Note that the UNIVAC 1 108, on which all computations were run, carries about eight significant figures.)

As a larger test problem, the equations with m = n = 31 were solved with t = 10"* For this computation

agreement was obtained to a few parts in the sixth significant figure.

A second test problem, a discretized approximation to a separable elliptic equation, was also solved analytically and using the code. Comparison of these results indicated that the accuracy was similar to that obtained in the first test problem.

The code was then imbedded in a linear finite difference computation obtained from a second-order dis- cretization of a set of equations arising in fluid dynamics. These equations describe two-dimensional inter- nal gravity waves in a stratified ambient fluid within a rectangular enclosure. The interest in this problem is discussed, the continuous and discrete equations are presented and exact analytical solution to the con- tinuous and discrete problem are given by Baum and Rehm [8]. Additional linear computations using this code on a somewhat more general fluid-flow problem are described in Rehm and Baum [7]. In this latter paper the more general linear finite difference equations are given, and the computational procedure for solving them is presented. The manner in which the preconditioned conjugate gradients code is used in solv- ing the elliptic pressure equation is discussed. In all of these linear computations, the equation for the pressure is separable; it is only in the general, nonlinear computations that the equation for the pressure is nonseparable. For the linear computations reported in these papers, the number of iterations required to obtain a rela- tive residual error less than t = 10"* or 10"* generally varied between 2 and 4. A large number of such computations have been run. A representative one is a calculation for which m = 15, n = 16 and t = lO"*; in this computation the pressure-solver was called 200 times. Two iterations to convergence were taken ten of the first eleven times it

388
-^, *&*.-.T«v« «s. ni J -«* #»

if«

LTM MT «i.si*.*»».^‘U »i »1m i»li^«isi. tm> »)«\ij”i!*i ,vinMiii>-j fil m s^r i-"®

rt';. ' # ^

***

.it: '®

•^^- „ij.,

'“-•^-

. .

" 15* ,j., "-

OtfiJiiil** *iiT

,

•». -i.

ifi;' ^ ^ J ^ TfiTlirT '('V

W sril ii^sa

^

®®***^j? hiaM^r^if

‘'

- la ' B? noilat^le

>j

1^; » ''i ,£W*isr »»ris4rij!«ii<te. «HU dfl(wmi9i».b’of .^siwiwY

^ M '<r.tf^tti6i> ii>/(iija4>» tfw^ O^utij* sayV> siTi >>a> noi^t^ 'ifei? 9|^Wft Mm

! ftoij(«u&a« Aiello? ‘'Oi sttJ)Vb<»vi<**^v.

- .i*'* M ^ It"»- ' ' .4 .io^taa^ 'iwt

•«ib ‘«flbao4Mi0O9«'ft ro^'fe^i^ aaaW'ttftb^oiinO tfoaii'i «i 9b*»4 ‘mTT

n»»fA t*iio-««i«mil>^wl 9d«V«b 9*»rfT ni

9« * WaeilasWafissi

j ^

«t a-. 9iai«H.«iaj nh‘^1*ia4 ..MT .nmil«i9 '«

.ri<to srib' « o«>ii 'jIw i»/W» ho6 b m *Maop» b«4 9«lt -

BiiJf amu ««^9h&icqirt^ ^awMi bo* *W« ,«Tt b;,« suOiJcta

^| 9iat.9oaTqnw4f<l*t»waw»^4^^

^

•V^yain b.i^~«Va{K»

u otuc«nq 9# 10J a#huij *» »J;,ii9ia|#j.^%'?(it*W

\ '«.' --^ * JT f. r >r' :..- siaOTHiWIHW

-otet * niii.a« Of , ««w 4towtW taab^ait4'A ^ 3

.. > , *

' .IT' (K-> • ^ ,' '• ;gr'^'i|n!^-'rt'Wa.‘iyArf-'l^

4'}.i wmil ctavsh 4i«a" >ift''to'o-Xa»4tf»»§»_ Qi

mii

m\ a

-i'^
was called, each call using about 0.5 s of CPU time on the NBS Univac 1108. Thereafter, each subsequent

call required only one iteration to convergence taking about 0.35 s of CPU. An indication of the rate of covergence of the algorithm is obtained by taking

^ _ logio (Initial relative residual) — log, q

(

final relative residual)

number of iterations

For the computation reported above, this rate of convergence was about 4.5 when two iterations were taken

and about 5.5 when one iteration was taken.

It should be noted that these computations determine a flow field which evolves with time. Except for the

first time step, the pressure vector at the previous time step is used as the initial guess for the pressure vector each time the elliptic-solver is called. Hence the guess at each calling is quite good and convergence is rapid.

Computations of a set of nonlinear finite difference equations generalizing the linear ones described

above have also been run. As noted previously, in this case the elliptic equation for the pressure is nonseparable. In a limited number of computations, the PCC code has been found to perform well in this case also. A representative computation, one for which / = 31,/ = 31 andt = 10"*, was found to take between 2 and

5 iterations for convergence at each call The CPU time taken was slightly over 2 s for 2 iterations and slightly under 5 s for 5 iterations (very roughly a second per iteration generally). In this calculation d defined

above was found to vary between about one and two. In the Appendix to [15] a listing of the elliptic-solver, called FASTSL, is given. To use this code, subroutines from EISPACK, the Argonne Code Center package, and BLKTRI, a subroutine in the NCAR package

developed by Schwarztrauber and Sweet [10] are required.

The authors wish to acknowledge the help of our colleagues, Mr. Martin Cordes of the Center for Applied

Mathematics (C.A.M.) and Dr. Howard Baum of the Center for Fire Research (C.F.R.). This study would not have been completed without their help. We also wish to thank Drs. Dianne O’Leary and Francis Sullivan

for reading and correcting the manuscript One of us (J. L.) would like to express his appreciation to Drs.

B. H. Colvin and F. C. Johnson for providing the opportunity to undertake this study in the C.A.M. during

the summer of 1977.

VI. References

[1] Rice, John, Algorithm Progress in Solving Partial Differential Equations, SIGNUM Newsletter, VoL

11, No. 4, Dec. 1976.

[2] Concus, Paul and Golub, Gene H., Use of fast direct methods for the efficient numerical solution of non

separable elliptic equations, SIAM J. Numer, Anal., 10, 6(1973).

[3] Concus, Paul; Golub, Gene H. and O’Leary, Dianne P., A generalized conjugate gradient method for the numerical solution of elliptic partial differential equations, in Sparse Afatrix Computations, J. Bunch and D. Rose, ed. (Academic Press, New York, 1975).

[4] O’Leary, Dianne P., Hybrid Conjugate Gradient Algorithms, Thesis, Computer Science Department,

Stanford University, 1976, TR STANS-CS 548.

[5] O’Leary, Dianne P. and Widlund, Olof, Capacitance Matrix Methods for' the Helmholtz Equation on

General Three Dimensional Regions, Math of Comp. 33, No. 147, 849-879 (July 1979).

[6] Rehm, Ronald G. and Baum, Howard R., The Equations of Motion for Thermally Driven, Buoyant

Flows, J. Res. Nat Bur. Std. (U.S.), 83, No. 3, 297-308 (May-June 1978).

[7] Rehm, Ronald G.; Baum, Howard R.; Lewis, John G.; Cordes, Martin R.; A Linearized Finite—Differ- ence Computation of Fluid Heating in an Enclosure, NBSIR 79-1754, May 3, 1979.

[8] Baum, Howard R. and Rehm, Ronald G., Finite Difference Solutions for Internal Waves in Enclosures, N.B.S. Internal Report, in preparation.

[9] Meijerink, J. A. and van der Vorst, H. A. An Iterative Solution for Linear Systems of Which the Coeffi- cient Matrix is a Symmetric M-Matrix, Math, of Comp., 31, 137, (Jan. 1977).

389
•IT sn. I , id/, "M m swi; to t ?-<> iiM» t

-W'*'- »*

800.' :'„;( 7-> ' i' 'lo ff» ‘>0

,4i wl i-jM. .< w* Hi « «»»<> H-jW. iHaa »«0 i »«"H<®

,?«, U« Ina

• nW'rwtJita* bwy *

V..*8 tt 10

l(,l»V'- ,<h1 >« . 0,} -

- -. 'rO'1'4 IT *'« "siipi. ,-*n

»7 S Vd,^:;...

’W-?.!*.... »*-.. 'T ,L’j; W > t,oT. e ..*.. .. T

^

. . !?TP<k^ (0vU. , T^!ofcTft*>i»H ••Vi ’’• •* xib«»«5n^ <»-

flAOV. ,Hi f. '.'1.H«:.d,^. , iO,),^w8 !,n. ,.l !".qoi.voi.

h.,j:

> .• t,!i i.'flf

<;»i /!io? ?-t>;i»> V br. «n « -"*• ••'5'i“ «•; 'r?' ;'

, '

.,0 J . «> .•««*.( •> H"-» » .a

4V

«iwot.

i:::,::s“ '.;.p:i/::^

;'

., >-»»«

, :,yy. v>i.1 V.-.« Mnua. ,

vn tini'l n-i-h/St^niJ f

• il tof.-> ;a> M hi- b:*a^uK;i.u..-a ;.3

^

' T%*Vi » ''S

**' •'ii't'"$P jbA«? ^ ^''?S ^ l^»

ife*3 >» *!>'!>'* to »®>*^ »?«*H to1 «j|i«tea •’

.'•^ J;*".

*
[10] Schwarztrauber, Paul and Sweet, Roland, Efficient FORTRAN Subprograms for the Solution of Elliptic Partial Differential Equations, NCAR Technical Note IA-109, July 1975.

[1 1] Cline, A., Private Communication.

[12] Reid, J. K., On the Method of Conjugate Gradients for the Solution of Large Sparse Systems of Linear

Equations, in Large Sparse Sets of Linear Equations, J. K. Reid ed., (Academic Press, New York,

1971), 231-254.

[13] Hestenes, M. R. and Stiefel, E., Methods of Conjugate Gradients for Solving Linear Systems, J. Res. Nat Bur. Std. (U.S.), 49, No. 6, 409-436 (Dec. 1952).

[14] Daniel, J. W., The eg method for linear and nonlinear operator equations, SIAM J. Numer. Anal. 4

(1967) 10-26.

[15] Lewis, J. G. and Rehm, R. G., The Numerical Solution of a Nonseparable Elliptic Partial Differential Equation by Preconditioned Conjugate Gradients, NBSIR80-2056.

390
<» / I

V’

"S I ( ‘ P • « I

<r*'. j . - V, t! , • j
APPENDIX

DIAGRAM OF SUBROUTINE LINKAGES

BRIEF DESCRIPTION OF SUBROUTINES

LISTING OF ALL SUBROUTINES
vSiA "^0 D^!IXi/IJ'
DIAGRAM

OF

SUBROUTINE

LINKAGES

Eh pq O U 5 s K K

(U 1 1 ^ 1 CO 1

EH 1 r

<i: 1 L_ J

Subroutines

from

external

libraries
1
Brief Description

lunrEU -

FASTSL -

HCGSOL -

Initializes the NCAR Routine BLKTRI to solve

u = f on the rectangular grid (vith Neumann

Boundary Conditions)

Generates peurameter vector PPARM which must he

passed hack to BLKTRI when we fiLctually solve

the pressxrre equation

Separates required working storage into pieces

for the coordinating subroutine’ HCGSOL

r ^ Coordinates the pieces

a) Calls GENPOI to generate the discrete five

point operator for the pressure equation.

The matrix’s representation is stored in

the vector 'APARM*

h) Calls NEUSCL to compute a diagonal scaling

to make the discrete pressure equation have

the same diagonal as the Poisson equation.

c) Calls HCGSIN with the diagonally scaled

operator. HCGSIN uses preconditioned conjugate

gradient algorithm with

A = scaled pressure equation

P = discrete Poisson equation

d) Calls NEUBAK to undo the diagonal scaling to

get a solution of the original pressure

equation
X ' f V--' 1 J *i«v.

/j/V H f."'* <’>'» « fJ ?

, ,.-^e.r.- ri;r;.. •Vi?‘v: iXi\’

i! *’> .':iiq .jtT'}-:'

'j-.-T>t-i t;^)'

*i' .v;-5 o:*;;> .':^.'\cji' ::tow ; ^v'.

yn»*? i -.7; -:2

<S4'Up^,'£C;'c. i '^:, ct> '•> ^ "jjOt

?; . 4 , ;ra-j v --. -'.

^v-^‘ ‘>rij i;r;;-'r; v*^ 10'’^/.r

S'rr5 i'^'?: r .j/f : -ol^rtfK^ -'J-pl

^.. ‘I: •:

: !

• 'uy.i^v ^.r*

'Mfj4S-rt' J-'t;7,'4;:V • -’’•T

•

' ' '' ' ^ ; I O

T: jh :i •'«!.•. s- •' i i) ,‘USO

©IXpO (o

-J- :r>l^!^^0.: V -V iilXeiCiDH tOv -?T»: CJ

*:

« : S' K i^.r'fC';, Lb ;Ji.C!i.lt:;>*is

« 1'‘4 i'-" yp- ''•.l.'?' . ^ ’':^£ ' :7'L7 £ A

T;, l.^4 -.;,^s :..,-aei»'i f ? *T

1,1 -^;! i

' •'D'j ‘-••''i

' ..•biv O* X-V’U'L't ." ILtr.' (if

i.,:3 ui^.^

4 C t Ic ; » j

n: .' di:c'ps>
HCGSOL edso coordinates diagnostic information

HCGSIN -

ATFSHL -

NEUSOL -

Other Subroutines

PROJCT, PROJCE -

Preconditioned congugate gradients repeated by

calls to subroutine to compute

Ax for some x

and a subroutine to solve ly = x

for some x

The names of the subroutines are peurameters from

HCGSOL. Here they are

ATFSHL and NEUSOL

Unpacks representation of scaled pressure equation

in APARM to pass it to ATFIVE, which actually performs the matrix-vector product.

Unpacks representation of POISSON equation in PPARM,

to pass it to BLICTRI to actually use cyclic reduction to solve the discrete Poisson equation.

To compute the projection of an curbitrary vector

on the orthogonal complement of some vector

(PROJCT) or the vector of all one*s (PRO.TCE)

I? - To compute the inner product of tvo vectors
» A

•S,'-

V V c ,. ^

.’i'J *"' ' '^, •' 'v “' :.

I.

• ,? «.

;•/• • .0 * : A _ *• . ® ‘ S|f5 i

7w -v*' ; -T '-fo f

-- Li /

; ,'Oi -fOW/

r’

>l Afi
BTROUT - Prints out a symmetric block matrix with five

VECOUT -

Subroutines

TQLl -

BLKTRI -

non-zero diagonals used only for diagnostic

output

,

Prints a vector in a grid-like form. Used only

for diagnostic output.

from external libreiries

From EISPACK. Computes all eigenvalues of tridiagonal matrix, (produced implicitly by conjugate

gradients used to estimate convergence rate of

conjugate gradients

2

NCAR routine. Used to solve V P = f with Neumann

boundary conditions.
....

‘to*l :jlMisxxr:::l^- iij'mp^'-nQis

. 4* o s L:' ' ^ot

-i'7^ ^O ii..t/i^v«®5jls i.Jbi

t©' •»»«<J^'*!‘#v-?io> 00 |>0»tf »

£!f!j33ffl'' '’ *1 fv't’,‘‘"> *1 *”

*i. ^•V*’£G^ Q«f, iT-'^felJ » '3f{-it 5 iiO**

' -• TOOT

- TOW

- IJ!p1?

.* ifTm

,',V
a.

9*

N

<

a

S

<

£

Q

I

08:48:30

su;

It 9

C2t \

H

It > ^

. )t - \ ©

?• 9

<

• U k«« Jn 3

u. n* On N

I «) a

* .as -H H E-* eo

it

it WH it •• J

® bl

K

O

II cn

II

IIM

U

PS <

!• C3 •“ II II"... " u M Cil II " ^

H >< u On

a II §!:

II

o II BS II

II W II •N

» II u a. II w

2=: II s o II vN " H

.

II P

II m H II K II ? K II • W II - II

II o II r <0. II

II •| X

VE

II W

II >• *>

II

It <

fc; ^

»5<

X

» X I

II ^4

II + 5 II £

II a

II u II w A

li pS II t: & II It a a + +

II M II a

II U II m £ w

II ^ II K X

la II M

w

:: g

a

o + 2

+M ^ W

«>; X

It -V utts^ic

q wO

BQ -NO

S-i « II II (A a

s

g

BQ

0^o

X

Cln

It ^ si

I

o

z: + +

I ^

1 ^ “

I 'w •«a

-* I

•t s

o +

II II

II II it M4 S5 ^

II E-C II BS pS II '-' B £ NN B

II ll U S5 • ® K X t " © X

II P Ua II o • a-a © « • u ^9a< M 1 II S O II UP It . NN ^ t

• S ^ t II II H < P w X 1P4 SB X

II ll X u X xo o b S o o !

II •i «2 25 < p u S S5Q u ; «

9

X

Cla

£

I

>:

It «

I M

W

s

a

+ +

NN :r^x

* S ^

• “ *

05 X

X •t

05M

b« I-* ^

2; 1 o

9

OJ

9 w „

r C9 <5 E05 O O 9 U

9

«

05w

>!

It

*

a-> '•1 t-i la w

vMw §&xa

a + w

II e +

9

H

O

U

is &

Ss

u u u u u u uuuu u u uuu o uuu u u

'

I

' O O O ^ O O O O O O O O ^ O O ® O O d 9 d ® o I ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ 9 <9 O ® O O O O 000 ^ 0000^0000000 OOOOOQOOOOOOOOOO

Cl 9 W V© N CO<5'9'-<Clrt'f‘W'ON03<3'©’^ClC5iJ'mi©NOCO'9'^Cl'?9

>n^n--n-n«,n-nnn-ni^C]CJC'JC1C1C1C1C1C1C5C3COC3

^L'5 -©Neco' 9 *-'W«'«fLni©iv.cOo

eOrtc5 eo«eo^'^’i‘’«'vp'«*'i*Tjiij.^<

u>5o

fe5

Q

M

H

J

U

Qa

QHBG.P

AlTSIiL

:it^;^-.

1

::i::t:

w

a.

O'N

r-o

Q

>

it

I

it*

H

ititit

qQ

fa«

u

K

CO Q

« cc

01 §

CO 71 a

•O' ••

flO o

O'

I"\

II II

II 3 II >-

II o II w

H S H fa H U mm

II <a M H

II II

II ai II B II o II £

N fa • 14

11 ^ o II eB

11 >- « II o

II W OB It fa

• I — 1 C

II H ffj >t

i II

s ^ o

^ w

I s

cu ^

CA

Clo.

71a

g

71

SBK

e

SB

5i

IB a? pe; 71

7

) 'n

71

O'

LS

uouuoy uua uou u u u

..>^eOOOOCI'9®CO<SC09®<S>C19COCOO®®®®900<9<S09

71 \ ® O O O O O O O ® O O 0000000090 O o O o o o o

k N F o

<

• u

-3

fa Tf fa N> IT)

J-• CS-<CICO^WONOO'0»-*Cl«^IO'ONCOO'0-"CleO^IO'ONOO

E-CO -'-'--'----H-H — CIWWCICICIC'ICICI

WEitit

it

it

itit

g I

o

as

w

w

w ®

u

0.

O't-

<9

5

p

K

I

m

aH

p

p

ks

SC

^ o

w ei n 5

o w

c

^»• o

C'N

\

P

P

I Ch

b.O

E2Sdl:^

ffi»i>-*as ^b, 8 §S

•“tO^SW-^S

CD _ « 6-

pppp S<: M 00 g| 5 fc.-

„ — M «

k^asppp

• K

^ o •«wCO

K —

fip

u

<

0^u

o

Cl

«

p

s

s

s<

Cl

\ —‘ o o

1 OU N

>p o o 1 00 - E - Cl 1 X B

\ o + o o o

O vO >0 1 >* — o a: tc ® - 1 P

Efc ® ^ u

E E '® ? p? 1 Hn o M M if f- P i b • <! P 00 -fc EE 1 b to eu p ^ 55 1 b5 K — 1 H b. Ol, 1 O Cl • ^ ^ w

BS It —

pW “5 II II t- H P fm ^5 tdO-W^Pr' ^ M M ^ ^ ^

^ s

gg §

tbo

CON

10

O P

III, ooo!

b. b. b. I

OUPUUCJCJUCJUUUbl U (J

OOP ooo O-CJ ooo uuuooo

fe = s

o \ o

PS0

• o

-5

b, ^

P N

1 CO

N P

WH•• J

9 bl

O'rt

u

®M

O

oooooociooo®oo®’^oocj''f^^"<^M^’^^'}‘Oooooooooo

O O O O O Q ^ ® O O O O O O O O ® 9 9 ® o o o o ^ o ^ o o o o o o o

ClW'^IO'ONPO'O-'ClP'J’iC'ONPO'O-'CleO'fW'ONfflO'O-'ClO'^lO'ONOO- — «CvjCiNCIClClClClCICie5C903««e5««CJK

§

I

&3

5

u

p

k;H

*f

ifii a W

K <

i g

*

Yen

ifif

if p

o

g

e> J

a.

O'N

<S> IQ

e

'Cg

w m

a

(Oo

tr~n

— « eo

bbb

sss OQO

n g S

U ^OU

5 Sg

^ S K ooo

0) ® a,

>*

eq

o1*4 >M

O

ei

CO

o

C|) • M M

<-< c < C c

^ Q M M M

> soi d eC <-<PUCdU tfOOQO

SBaoia

owooo KBGQ03CQ

b<M

.J

' O 5^ ir* E-<

I I i egg

o > cw

hM o o<

nw H

H_]C£0

u — ta>o, DHeo^oEo*-, 0^0 M&SHTiSK

BC I-I 00P Cl] S »4 UOOEkJPiJ

H4 CQ O ^

uoquKa.,

>< p »-• < OHWDnO^

P .?2s

^Qobo^5 P^CdSPCU

2 2 S§lc

P .. (t, o • PpEi me

w w OQ < m rd g>Cd«

^ JP5BSPS5 — Pr-Pg^J

' y J »5 —

! 2 OH

<i!ai 0. » ^ _

faofi ocnu —

0(/]e[b< e

00 » w w «

pc: — oo « p? c4

^“‘='23; u

•U J| > Q jp

Cdj

hI

< K

P O

H O

C _) Z w

Cd «

J C-1 +

(I. z

O W

w

(da + HS

mc'

g + a z

a «

a

a

*do

«>H

(*»

a

o

Ci< CdS*—

4

a

a

g

a

z

CO cam z

Cdj

a

a

OUUUUUOUUUUUUUUUOUOUUUOOUUCdOUUUUOUUUCJUOUUOCd

* ©

* H

jr \

Jt J -

X m - H \ K N

«< O

-d

• O

1 - G

fc, V

a a N

1 ca

If »] >-* * H a

f .>] If WH ff •• J

c u

MWCnJ — — MNMC'IC]’--*-**-’-* — — — N — MCMMf] ' N <M <M « W W ei C] CJ IM « Cl

ilO\©I'«e00'O”«ClC9'4*lrt'*NfflC'O'^ClO'}‘»'0l'«aC'®'*CJC0'9'l'3N5t'»C0<^©’-*CJP0'?'n — — — jJMNejCviWCIClClCl«»««OCJC?e5 «C5 'l*^'^''f*^ 4< '©NOC'O-^ClO'tLO'O

’'J"^ 4''^WLOWWWPW
o C' O- •? *« tj- '0Xr'

' ’ O O 0,C 0.S* c; t,^ ts i.' W 0> W O y.W V' V W. Q Oiu O' y *< ,p O ,.; O

W y>l»

t«i^ Ittar IM **!>. 4»^ )Mr '-IT^ tf^ fh#!-' •»*! ->a Mir.' mn f *w-* wi

-m ff^ ^ t*'

im& »*' tm ^ ^ VM ^ ^ «e-f W V? *0

ftut kM* t/D^t ‘ ^ h4f hi*. **'

Cl r- r^'fi/i — ?Sf iy

<»tf ft! 0 » <V r'j '(S'

iv

'if

B •H Cr fil *'>.• C’ ' V •« 'i^'*r *1- <?4''

• »

0,lf

i’ -iS ^ ’* « W *“ <2‘ i) 35 • » »• C< '»^ <V O » o -t? C3 "'t c< W'it- -» 15 '

•!;SJ t"; ft <W t? ts W W i'i w f?. TO S' •* ***' '><.,*-* »•* « *•«

' -'9'#' f'5' W*^ OJ

' ' fj
o

0.

o

N

N

O

'<4

<5

a.

a.

tn

upoK KT. ^2

«5cn • — < M

W - 's: Cl - U I “a

^ [fl o <So

t, a ^

Q 2 cj £:£*

M

3ua;

a>

ttj 33 HC3 + O

B

O

O

>JJ :«1 < '/) S

c >* HO. . |h|^

© 2 - — CO U©OB «t u o ouo< N « 2 — H 2 W

2 e U H

ya-o

55s§

>5 S OO^B BBS

is|l. 2 a. H ; toco *1 can©

2 2 2 0 O B ©

a.,-® H^OO

1 I I

OH-I

©

o H P

b. ^ b. ooo

©be

fcjo2 © o u

+E

r.

e

B

w

u

bio

- © > U O 2

CO w —

f.l I O OU

• J

O J P H O © 73 U © CO > 2 CO 2

<:H©

^||2

CO f- oS

bill

2 W O "-• B — K H

j

B 2fs O

O O H (0

c

BN-4 ©

c«

u<o

B H JO

B b. J O . O S CD ,

I Pp

O

^ ^ 2 ^

b, c, -o a

C E JO~ I I S'-’ 2©©0 -

t-Q-4 B O J 025 U 2 >

u © ^ ^ OHOO

I I I M « <•

1 a

j b. H

< CO J <

O > ^2 B

ifegSg

<0.:;'4O

r, g

C'j b, Vi . Oil''

© ® — i

>

K*'

1 1 1 Mu

II J u J JU p 2 c II U b1 H r“ p II © © - 2 u It t u

>;

CO

b.QQ2

coco A

5 j oo

COM

• u

U ' © J

73 O

<Cd 2 B

2

ea<

g3j

>

3i

.§ \

s;h

\

S3-

730 fSg 2 2 B B

© Sc Ebl J 22 B O 2 22

u

1

p J

to c

© to BOOOO 2

2OU2B

SEb

2©<5

CO ? o B B

2 ^

2 B

CO 5

9t+ + §3<2

S!5

E-'COCO

r^EEE.

S B B B

+ + + + U<© ©OBJ CO CC CO CO K U M U II II U II *=§«<

u 52H

E«ii^O

BEOCOCO

O B2 X

U. •fi CO to

ooooooooouoc^oucjoooc:>oooouoooc.'>oooooooo OOOOOtJ OCJ

N <M M M M - - - N - - - M N - CJ - - - -4 - - W M - M N - — - CJ C'J « C-) W N N B C4 C'J IN W Cl « M MM M N W N W W M a C'J M M

J

[2

^52

C;3 ir- — C! ?5 •?• B >a N © © o •“ M O If B t» to © Cl W -J* B O is. 1 © © — Cl O TJ* SO O »•• © © © -< C! « If B » N © ©O « CM O

B OnC'OOO'OOOvOOONNNNNHNNNNOCS ©CO OO'JoJ'JM©©©© ©a© ©©©OOOOOOOOOS-' —

DECIDE

WHICH

ONE-DIMENSIOHAL

ORDERIKG

WILL

BE

MOST
fej »4 St 4

-

'‘r ' .

Ci'K'Cr'r

UV * ' »T rt

r O j; Vi-Jtii

5-.

x\

Scl' w — - -•- _- V* . 4\

Zi'-i Si S . ^.J c

t iu Cr <U

.s> ."s:

MI*, -i..- o

t ^

’-'? '--' O

toj,. c»

Ucs

r

!fi 3:, (» ;-»>'• rs'^i - .K, ;-».v-- f« ri' 5

.<? W. • m iC,

'..j

oj nT’*'iv ^ , - ;:'lSl.SrJ 'ifl'S ',

• ^C«. .<CCi

S'-;, -j -’' .V- .

- ^'-^J

.7 !X V

II

“Vii- *.• ' :J-; SH—

?

y; f

KJXV

r>, >

• * 3K

./ -

,Y u -, tc :•» i » -' i .4

.•; O' 4

B

* M :S^

«f,i Ui : - ^

. ^ .-i o cs • -

UCSai«X6 «

' Ni- s~ ruJt u.jiif. 1 .a «} 1*.'

u

jC ,x -S.*P y;m

/)h

ca t;

§-

B »: '5 c B »

J< ^ ^ V ci'l^ ^

Tfc. *

du a' ' .w.ViV Xisi» 5« > ^ .yfi.

Ck. Jr ^ 5^1 *•• w'.f firj apC»#

---/ it: U

I3

«£• ' - 4^ ^ lT;

><•* 4# ft -

sr* • V5 ^ ;5 ^ -3

a.-: /? v;

1 3

t

m

L- C

fer*

<^' A

trucyoo «J WO V tj U ' ) U O > U O iJ fj ’ a o C U‘ 'i O V ' V' U vi> Vo <,’ o

if »-b

, . it »5 M t;. wV? -v-w s^* -a la o u to w sow « : 5 p %t w ^ 2 i2 i C;

*'• ‘^1. H I :, 7. ^ t

'* t: id‘ ~ !;S :: r. ^ li.' u.X' ^ '. ^

#r *“4 •2' C* Vi ' ^ ' • ’j? tJI' wy-, ' -f ^ i. " ^ r

*5" ^ '" * J - ^ ^ ^

'.

’ "C' * V> Vi ^1 M’ I--.;'. ”'g- -A c. jfs ift ^'o -IS »t> -^ ,<•„ >3 *>'& 6j Cm''

i L’iCt u; -'.I f.-' V- >•!•< i'l>»-t-.-> v ti, cai*ft.-

'i
fcl- o

<

c.

O'N

« r^ H

^ p e:

I F Bh

o

U3H

co<

b.

£«; 0

b<

1

s

§

Oi

<oeaa

n b Fk

a. o I ggg„ m 7 0. no-ru 7 cw » ® ^UJ

c w « A n>r Ktsboi

uFaS 73 U F WF,

Ps& F J ffl Oh

>-] •-*

§5’

( I

I ^ ^ Sii

11

P ^

'_' K » /<s ^ M 01 as

01 • • • tf PF

•UU.J

u • • a •

• a»a

II

cu

NH

_]F

-• OJ 05

M o< !

73 tJUbiF

acn7)p u

O <DgUM

(£i I a a a W bJ « I 2>u! . — jmFom «ao uf5 os

^ ^ ^

a

o F < a

5! ISu

eo

F

F

F

B

05

F

$<

FH

g g .

01fc

• F

a F

5a• M

F

F*-

>-H W

FF

a Hs ® ^ N d

F F

•-< F

F w FaF>«

B 1

F

a

o

a

o

— Cl « «0 V©

O ' 7)Da

F GCi

^

.

cn ^ SSp o 5 d

B O 5

73 FF • F F

2 fe IK -O

73 r.' 7 F * G F .z tn F F^Tl -Op

G <I F w Hs •— F

73 a < a a

.-^aF

Fgg

B •!

I a < F .J 7>aFU >73FD0

I

F

!f%(4^

. -J5P

a B j iapoF ! a B ..7 Q

B FAF

F 7) K a

a « t5 <r

O O O M UD auFo ft 5

F < C O 7300F ”

P P

— 01 05 '0 K5 \0

F

fta -3 a

Q

F

N

\ • • 73

ft B

F O

— 73 F B

<g

(-> « F e B-F

B B y F a

F F

a F

F F ^ O ft \ B

a ..

C3Q F J

Kft^ F F F >NF«

*

••f

•>i K*

it

ifit

if

ifitw B F B

if O '

OFp

W <F

it M B £ it 73 -

it

* .«• it C B

• vt F F • o i?

, F

it F a

o it CQ B '*0 it 5 a H tf F 5

if t:

Fo

O

o

ft

a -• F O ft O

ooooooooooo uoooooooo oo ooooooo ooo

•ei a

oF

®

o

o

O '©

— MW

it

if

)f it 01 a 01 N 01 01 OJ 01 01 M M M 04 01 0) 01 01 OJ 01 01 01 01 01 01 05 05 a « « 05 « 01 03 01 lO 01 03 01 01 01 01 01 CJ 01 01 Ci CJ 01 OJ 01 OJ OJ 01 N 01 If'

F

['^ F

it¥

it

if

l5 '? N a O' O ~ Cl 05 <i' l<5 'P N a O' G 03 F ^ ;0 'O 1- a O C 0! F W \0 0« a ~ 0! 05 tf* n r> O- a ;T' ® — 01 05 ^ U5 Vf? N CO O -• 01

fj fl {>1 Cl Oi 01 01 01 O! 01 « M « W a 05 05 a « M 'O ^ 'O '0 ^ Ij* 'O + 'O lO » L5 « «> W !i5 l>5 U5 W to vO O G •© '© O « O vO O 0- 0* F
1
I;*:,;?,-.

FASTSL

DATE

071179

*

if

if

)(itit

ifit

it

itit

it

it

ititit

itit

it ita

itit

it

it

ita

it

itit

it

it

it

it

ititA

itit

itX

>-< OCXM 4

X

» *x

* - X

•• •• itX

X

X

X

X

\ \

u

u

<x

^ to so

vO

05 01 01 C'l

O Tf> to sO N N. N N

!3u

O

M

©lEDG.P

GENC3D

**»*:(:*
: - ••'. '• ^ {>'^f - C. IU «
bl

Oh

<J> N

N

S>

<o

^ oS oS ctf Bi O O O O Eh U< U< ^ w w w

00 § kx >!

SB w w w w OOOOO

hSSSS

[-J J

2 Ed U

00 X I

00 I

EBaOi

1 2 s a u

'SkI

00 o ajo 2 a !r - H

; Cd S 9 2.

I S H V5 2

; > u CA a o

1^29^0

, cS -• — O U PaoN —

; £ o c a a L~-2g

I — « « 2; SB ^ggglg

Igggpl ' W fd 2 a 2 a a

><>>-90

a o n 2 2

5<>5Xoo

c -a: c

B !a S ^ ®< ESSMO)

a>i>

, ®

Oh WJ h h « o w « J

^ a a Ed Ed

I Eb a E^ a o a

o

H ><

9><>:>;

H A

u a a a o>ooo

g

M a a a

•—««<!< <

a a aa

ooa>>>

< 2 a a a

tiiggg aoooo 2 aaa

^«g a aaaaH 2 WWPm

a 2 a if, o

9 O Oh id *-1 A-iaSa

g

a

u

XHH

fS CA ^9 . W H «

I OO-iO

I via'Ji

• < 2

I a 9 E:-

1 % O 9

, a >- wj

' ® ^

I w a a ' 02 0 laoa

Ig^sE

2 — 2

lW9i=-

i S a 5-Ed9

I a a a a

"73 I -

I a /: *1 a a a looao

5 o a j

I 2 <<

I 2 O - — P — >3 a o a 2

'Eb-ag « Ed >“ 9 CO a 2 —

[-. - > :d 03:3502 2o

aHS

o a a a

5 AOaS

P

o

2

a

a

a

o

o

2

O

CO2

a

a

o2M

03

E-1

a

>

9

Eb9

a

oooooouoooouooooooooooooooooooouoooooooooooouoouooo

N

\

O-AAAAaraAAAAAC0aAC0AAAAAAAAAraAAAAAaAAArac0aAAAAC'3AC0ac3AE;:AC3AOi;3nc0A a\«w««««9««««e3owo5c50«»«rt«o«a«««nort««wo«ww«««co«rtc3«w«co«««oc;c:« 2 N

Ed O

O

Cl«'Jf3\PNAiS'© — 'M«<flO>OA3'®'-'W«^L'?>>f»NAO'9— N0'TW0>A<>9 — ^!9^<WvO^. Oj'O — C}«^WO — OIMCJWClMMNC1Nrtrt««Oe3WeOWC-5'>?'^<}*'d">J'T!«'tTf'0*Hi‘u'M'>r>WWWW

o • o

a 1 2 - 0) a a r}* o a t1 CO i a -

-tc

.' a 9

3E a

V: atV: •• a

9 a
I

J

<

s

»>

/•!

i^.

•Tr’>-! e -• ^

-2 vA

.^' u a

w ^ ^

- ^ ^ v***

~« ' .'^St*. 1^ C?.‘. ?if> " J> i/5

>*' 4»'»A ;-iK

..,^v ,,^'*i^ w

*•* ' S-

;i. »«» . £

!% .<? f*-. e *v p OK .:i -'''v

•Sfc ».«; ?, isi K-li3 3-ar •.«« > -w -i ' ::; ^ •' 4‘

’"' '*'-'tr‘-0 r

**

% »-

i'*,* ^j »

**A _

!-; 3 fr ’*T.t£»

Li:>V'’^-- v»i i'- r- y . !* » i«n K, -'3 $3

: N'. ;A<; ^ '.• '

. \

*.'? >.

%

<&

Sw

•i <i^ s; .»

‘J? % »*S •“ *'“ CkK... -^.^.P,

a

^ !

UB ^5? e- " /ft- -il '"

'Sl‘a'

i« ^ «.. SS^ 4® •> S7

}r*MS- 'JJi'N.'te

,U »

fV *5 ^

ia u iW wc ??i ..

Sfe

*'| *5>' tfifiy ?<«. -c> vs

}as»

O M 1<

is c ea ^sav iif.A K i<. K *•'

J3-e < -::5 ;/ • jA a . H &

7' li>- >' is? V'

K-J t«S «ry >l^JW So ^' ^10 v

c. a& p yj

* •!'•' .- ..>t* ‘r

'••i :-!>'i;.., K j: S.1 J» -.v«r,

“ vOw-4-^ ... 8u.: f> V ^

,55 ..Si' .is. 55

c? li? a#

{•1® Vi '.'l.. - "Si

5-'5.

e-y? *«*•

,sf if

... jCS^. „* ’Jt tl

."Tv. p

9.k ^ '

ia 4S>/U5»"'

iL, v;feH2

> >

• ^ K tw in tji..fc.. &

t, CT« - (t. a* yi

'!l fii^

$% la V

Sl . i'

-

KJ

v JfevK '• '• K%• ^.j W .V -

-P.fi?.--'' s&.,^ %

^ -5*

' ;s

-y*

w, > i rri yj “rti ..

-55? :.s!s .::2 SSSM .aa _.:^ r.^ •*.

!v :,ry .% o'%j» w t- c w cV V t- v c o.-'j vx? o o W ti? t? <^ t; t.

Q v~

"? -?

i^-;-

»*. '^'* **^ '^aT t: tsi -»g |g t| M

Xm* .

i v« ^ . :iib‘i •* (tS- )»C*| S

.^'.0 "I

c;

. |T^- M.

a y

i^..

.Si

«*

.•-< >

3-* f. gfijifi ^ ^ »•••.

jjvn ^

*<L < ^ <4

>- . a;

*ST-i

ill 5^

.A

is'

£..

b"

.as

b .y; OStS

S^ Hr^'

(£>

jw •.

!b k

.

;.A --i V® ’J

c. ?

w

1“

v*>t w

‘. V O (,:'» ;,ru O .^ r; t.’V

4i

‘ '5ri'.5 ??

V.'

•> ''» •

I gi

V.«a

<?.' T. •£«' 5; j,;.,‘. iy< < 'it * u-

’•• > :e^ T* <'*. *3s' £"v < Ot .tfi 'i!

•• ?> •» »>••>* '^,-- cj: ^ <; . fy t •lis^ If. jfu <!)•*<"«• "V *•,. 'f.

<•’. '." > ''; 1-j. o C3'^ O £o-p: p"Sc!.K.f'> '** ^'>' >'•'

• y '“t ‘V.'.y W "- i> -i’ (V "< -' s7? ' •>

,

3

5. ',T. rjt/r; cTiiji.ct! K ;-, v.- 6ii'j.<»K i' W KU? t?5 W t-- p0t>! y » aft'O^a-v ,,•.. ’:• ^.i!V «.,’» *^0

<: *. s> r-v •!: .rj’^fj.ec^flc ^; O r WsJ-P? fe i» £?-«5 fif K SS’W fi ft.;0 ic yii w.-if ^ « ’*)?*»• tv *; f '.'i t* ftt £•• <• W>: SV 3 :'' ' ^

'S'.i
.'I

Ol.

O'

0

1

A

Es:

Qfj O

A K O . — w p5 S5

;

K < U — I

y ^ A

^ S o

STAca A

U

Q

u y • A A B ^ U

j fca

;s: A A A

o

M

O

’Ji o

= Q

A

U

H

M

£

<

A

<

A

<! &< t- 5 w

I

- S::A wHUtaCA

>> O A 7 0. K

. jaSq J

A

E(b« A A

5§

(Ak

uA

H

9

w

9

5i «o

•A M o

OIN

it

?e2 A A

\ \

A A

A A OC

W “ P», © H WE-'>

Ate <

OD* — oa

A

H a e- /)

,

A • A Cu pea; K

Pfcjop

ggp^l

S r*3 ^

g

tis b CO A

A S

a <

M M ^ ^

GC CC CO a — z

'U • H

R CO A CO 5< OU RU *-• z y w 55

F-» •-• 0 A

u j H a

^ b ^ Ui C^

*- U, 7- O

CO c E- a Z «

as -rf < o E-< wco>>r

®|ay§5

So aha^ Fa u c Ay AhJ w

aiiSS

§ a

o ^ p a a

c ip a«H

a a a ooo

a a a

CO CO CO >>>

a

a

a

a

zg

§a

a a

u < <>

«a^

t’

COI

a©S

I ^ g

' a j

I© o

a

?- a

a o

a

c a

a ©

a

Ol

> >• a a a

a a

0 A K a

a AAA

UUl A Baa A A z a a

a A a u A ^ A A AO A<ao

a

O ^ ^ H

A-CIW (» F

CO

C O Q A A O O' ;.! A CJ A A A A A 'J AAA A A A A A A A AAAAAAAAAAAAAAAAAAAAA

aaa©a©o^aa©aaaa©aaaa©a©aa©©ac3aco©©anaaoc3aaoo©©cdcoaaaaaaffiA©naac3

CO WWWWCTWWWAWC9 »«««««« ^-JAWOe A »rt«AC5Wa«WC3C5WCJ««00«C5 A ©«©«©«©

©

a

a

h- A O' © — Cl A *MO O N © A © -* Cl O Tf 10 O N a S' O -< PJ rt n ® N a O' © >^ Cl 03 !f) vO N © O' O — Cl A •1' ICi •> N « (S' © <•• iTI A

L3 0W©'©'0’>00-i>vD©'C©b*NNt-NNNNt'*NM©MCO»©a©A©©©©©©©©©C'©®0©©00©®©C*--^-'*'<'-*
",

-^r\

*

;r

f-- j

' ..

r- ..

*• '.•• c;.^ -Xr«A ,;'•.• c>c: -

.0

'tj ^ v‘. '• -t; ;

>^r-'

;.J

•

.. ST'-

> ;:v ^x. £

' '

«jf i • v'-V.

-

<

-; V fi

:i

- :'r

' ' '^

’’: .V. ^.' - '

: C' ’

': v

- J - . -. - I

f>-

' -

‘ ;.T A

tSf

•?• >•

!

f ; . i

I

it

* ’4r" >

• -* '.C

^c

6

ir- •

• .. -/^r ir.

;,e %

G i'

1

:^

:

I

- -'"s .

::^ ; d!.-. ^ r:

i- . >a at

. .- K-'r

i ?S ^ !* 1 it

'-Y. ii -:i

r

'- ''

'’' = fr',:*: 7<. V'

/.

- * »f;

‘ “' “’ 2 t ;

,.. ;> 5 ?

# >

I --^V V

' p i> ^,. ' -u Y'

f-

-''' .' ^

' ;• \ -^i

' ;' '

-. 'i

. r - u.. ;t ..** H c .•

' ;: Q :.' c- . ' ' C- c. \ - ; : c ,;i . v’ V : r o '.

A

c

?- f, ^ / ',- y\ ^,- _,•.; -p ^.., ^>-5 , ^. . f.j p.. r~ •, jv

- . •, . ' . „ c: , A' .,-; . *: ..: - , : « ; , .-^ r.- . ' r- .

i

i

I j. o o tk "

< tr^ A *ei‘?

• • u*> .-I .

» ^ r

• ^ i t

•' c. a* .- -.i .

\

*4

.%» 4

:-v

Cr.H.
**»»?.*

GEWPOI

DATE

071179

PAGE

O

a

+ + ES

^ a

I I <-> —

U II

» —

• u

II O

*®

© O

M

>-i

o

- \ w

o ^

o

QO A

w X n

\ u » ©

I © © © w

• bt

9

CJ

+

*-»

+

?

•

• a n ©

H a II II «

p — »fa »-k EQ. U4 • awra'-'^p • xxm«H •-> • a a X w

. p p a a ©

W* w .pbpaP

a a fii«

S O CO ^

rt— *5">

^ w \ a .

-> fS Oi) p — o X « P w

X ^ W • b< tffiiN u M H ©

p II II W

X >-< <*s XX W-ip

. a a X

. a o a b. o

>*

a

\

u

• •-* • :» UD « © X © ^ aw 'b.

, o©

H M

ffl II H 1^CDCD*-)

• ppa.

• o5b.

©

N

?1 P

W

e \

©

SI

•f w

-iS

• fcl - J

\ -• ^ o©©©a^ H® w

H © H K II II O « <-« 'WODOO^^p X X - H kM • u Cd k-* .©ao, ©

w . a c b, u

h

©

n

+

S-' p

® •-• K9 CD v-k el I

S

o w

u

. 05 \

- a Xa©

aSc4 .p 9

gg « I. ©

• — CDcnp

••< XXH • u w .©2© ^ >wau

$

3

5

U

P

\

P

a

P CO •-* J X w ou©a PP •b.

, a® E- II S

" ' acowa X X •-*

• UU W

• a.. j a a.i -

' kJ bi (fa

©X

0

cu

a

1

bia

o

o

Ph

>p^ u

CD «

X X

u w POJ ©

+ +

CD CD X X

a a

g§

CD CD X X

a a

§ §

w w

© IIP p ^^aoo

pap 0 O II II

1 I ^

II 8 -^ ^ ©

5 §iig

*£ (fa a «< o

a w p p o

a

©

©

CD

CD X

X a

a p ga

> p

p o

o

-)

li

a p

©

a

p p p o p u p p pp p p p •p

paaaaeppaaco>^aaaaaoa>*aaaaaapaaoaa>"aQpaaacO'<papaaoroaaaa©©oco®© WOPWWWWPWCOPJ'^WWPWPWW'tWWPWWWPrtWWWWitWWWWWW^WWOWW :-;«««« CO

— -•'-*-'^PlP)CJC'lC^(MeiCMeJC'l«««««««« 0 W^’<»"4'^<’'^’iJ*^^^W©WWWXIftWWW© 0 ©©©©©©©©t'-l'-t-

TT

Uio

*c

cu

c«N

r-o

b-' Q

£

7)

II

<S> 00

b

o

u

u

o

sS

I-J U • tap w

w 9h u

^ bJ R Hb cc UK U (N o« S lO U H p >c K pa • O UK

u a u

o

n o o a •• O' a ® * - « S n

a

CJ CJ u P V

7T U CO K

X o p

COC0030000C000 K z

rt e? e? o 00 C5 u

• • o

- ^

o g n

CL, € *

. S s it H u •H o it

it

• •«••«•• P

CO ^ UO » N to O' © u c.

' a (w !>• (s. CO w » a ^ »< «M ^ ^ o

K a B if KU ©

»!<

oI

O'N

f-O

lx]

cn

U

•© f3

o § <«• (.: Q

a

o

Cm2

K

s

2:W

£

s

5C

ac

(A S . .^Is

£^S:§

*C 05 X

I

W

w

-3

b

® 1 B B B

I ^ 1 a K p 2 pj ) Cd 05 a?3pa;?E 1

1 B a >i c < u u 1 a

} a a p

- M

CQH

BCDU

b] £ U

- W C

O H O.

•< «j 05

05 j —

:•• D

Cd B - :

<i:< ojb”

scaS:

-JOO'

05 >-

05 B

Cd ^

>= I

« J

A la

II Ed3a<

o

05 <

U

tOmu

s

B Ed Eb >— EdH

Cl<

mJ gg

EdS

gc

— »

05 >d So

tfOj

I mJp

>• . £QIb

Ib

22

OEEd^

3§

• BEd O B

^3

® p 00 h

H§

w

050

Cfl

'“"9 p

BC^

*-• cu

>;

05

5?EdB

b<O

EdO

O)a

0»•« a

1

a

o

a

05 a

X

EbO

EdO

<

a

2

g

B

o.2

g

B

f-a

§

a

oe: g

A » CC £i pS^JfcjEd E-- P E- — Edp

«e w®

B £za a

2 g r' H g

w ^ p 2Ci e

a 05 o

'0 O fd H

a S ^ a o

fe-oo ^ sse^«i M o a •-> p >pax

< < Ed e- <

Ed Ed O S

B a 05 > w

«Ed— > W

J Ea S bo S Ed C' g 'll * [*' a

a ;.’ H 03

<<3* X

Iw

:32

s

.M

.>4 73a

t* a

a

p

Ed>

o'/

EdB CJ H II QN

a a

a

ra

05<

I w

>

a

o

05a

•-* o •“ a

a a ^ o

a

>

m

EJEdUUEJEdUUUCJUUUlJUUOOUUUUOEJEdOEdOUEJUUEdUUUUUUUUUUUa

*

05

Ed

B —

*~‘'^t'«aNv9'6'ON'OO'NN'O'O'OONNNvO'OvO\O'O\OvOv6vO^'0v0O'6O^avOv9'O'Ov0'Cvdv9ONN>OOai2'vOv!d''0C'OO 05\COSOOOOOO®OOO®OOOOOO999OOOOOQOOOOOOOO9OOOOOOOOOOOOOOOOOa ON

2

^

• o

I - G

a If a N

I 05

It - a -• C'l a 'f* n MO N ca O 9 -* Cl rt •^' lo -P N a "S' O *'< M rt 'f lO <f' N C3 ^^ ^5 — W « i!9 'O C! -\ o -M f1

.

7? lO o f. C3 c> ! c; .:• o ?

* Pa — — "-I — — N Cl Cl « ei M « Cl Cl Cl ?9 CP rt C5 « O C^, CO O CO C’ 'C -tf- ’J* <• -C ^ «• >? S'? '^. LT •^ L-J L5> to

It J

,

tt W P

It •• a

€1 a
' 4

.P

w:

-a .

,5

- t", ; v'

, iT)

F.Vfi

. - '

. '^3

«- .?g. • .t <.:• >- •jI V J

'• ‘i V ' .-'V:

-*•;• ‘V ' ,'

i

r!

/'C.

ii»

.:a

, .1

- v'

iC'

- '1 ”i.i’'

. ’ V?

' v'*

' « >;.Z^

4^

P'S

,3

Ivft.

" , ''•

, I

i;' ' .

',

•••V

^ ^ nf.

•

4- '

' •'

u"' 1

A--.

.

I '

' .( A'

• »^r

•\W >v

t 3

N.»* 8 J 1 'f &a

4

. j ix '.‘1 f’ ) 4t

'•^.': .‘‘r

.i

*..1 (, Bi“' > 1*^ 4' k-' 9

Jial a: .fs.' <?p t;:v 9.^

(

t

(1 i« '

>

' %•<« ;'*) 5^'' A'

' ^

: V*

.J.

%V

{

1

A$

,J> - : kV .A

.25 „.,

' ^ i,iir- "'a *V c ': }

"'• J; y;

:

f ii-

. .', ••' .

'?

« S'

'al V.: ^:5

>

(:TC

....

,_j.

•->’4 liL-

*; t

r 3

* =*.?

r •'i*- -J:

.i‘-

:-S’ W . V^,

.vt*^: i.

;? o

9

-•

' "y

i- *

I i

S,:: / ). CH v«J

'

5 y^i • •• i

j

\-m: IhJ \^'

st>^K

y

1

’“^

? \ J

-'.1 U* *j»»

V > Uu* '9 ^;

'-5 »$-V.

-•r* y. *5^ ^

•ar. V'

N-,

‘Hi ^ i'' 1

ir-^ »’

. i

s: ,.,.

a S'

'.

. : Z

:-5 ^ S .'(

* r.-

>

V-. fj t > i'O

'- . H ^ ^ •> i

(

H

e>

,*»

f«i

:»

'

V > A

-'

•fSnc

,

V

c-l a

•C»"Ci 3-

5^

- * ’

i'j *!:

u'

U

5»? -^'w •, , jpav ! ' •;' WQ'»< ~'''w >-' ,i -J,c Q« U

& ,'<• C' . . / .

‘ -t p {

•

... V . .•

. <5- .,' 4 .:v ^

C: 'i .. '<..’ .’ '..' J5 V' '“i. .- ’.. 'S'

.. >- .- 'S^Xf fK '^' ‘ i ' "

!. .

, ff. J'*'

a’„ .

'•-^ -

^i

fsfc

^

' 1 ' ..'k V

i*‘ Sv -''fti' . > .iipj.* ’’? . V*, r C cal^ "V a. 'y<J- V -s ~ . .. ^ '*.-.'i^ -V .C.C1> «?•;« -^-.V' ’- p A'.':.

=‘. .;«t...v..».K,

.:,;i|- ,

' *

' Z: * ' • .. .A ..-V.

• ', ,• ' ,f ','••< •,,-«

•• 'A " C V

•f
ON

N

<S

I'J H

<

eu

•• UCQ

pas

j P -- jPhh < u a »

U b] u u

• s> ^ o

Pi ca <

ViiQDUb

H- Ec,

bl SCOGC J Oc « -

. U ou u ><

cu

a. e

u

a

u

B> u:

*5 ^ W P «

8

ffl « a s ^ u u Q a

<q >Q w

«OPRO^h 3 p » j F « » - w <

pa o o OD J

F Q 85 r

fco

b) S

E “•

<- b< aM

uan

I

oE

OE

E

O

a

p

00

E

0

1

a

o

w

E-2;

o

u

bJFaJlj.

u ^

^ b. >-p j

b: o a E ^ IeoSFW

fc. F p »

OOQ AHE

s p X p M O E JU O- X a ^ S c-* E ^ O, pSF

U >* F O «

J U J

P J i:3 <f XU 55

p — y u

U F g g

O

a is ‘ < F FOF a

af£<aso oaao

w F F - «

Vi n b) (/] a a

u -wSf

< a -< u

s J N tJ ^ 2 -Sg E 73 C" *3 >*y a® a;s ®^irc

fisa E — 7i W b^ uaa EO

E aw o^cow

?: O E w <! o a — K a

U fc, J 5 7J

UUUUOUUUUUUOUOUOUOUUOUUUUUUUUOUUUOUUUO UUUUUUUUUUUU

000000000000^000cd00d00'990^00®®0000000000000^^***0000000000^0

s

a

F '0 ^ o « M « -J" w © N C3 A ’^ M :5 '4' U5 o N a O' © -* c'i a <i« ii? 'f< t- a O' <s *- cj o »r to >o N a •> o <'i co ^ m ^p N CO F :> — N « 'J* K5iortvc\o>o©>ONOvoovc'©Nt-NNNNt'*NNFaaaaac'3oaaa©c©©©©©c>a'0'0®®oooo©oo~ — —
iJ P' O 'P V C U O ‘.:j ip p w P iSf C </ V P P V O Uip.c u g> P P c p u . j p y u t.- '.ry

a- -i' ;.- - e- *•;

i3 ^ tf*'' t r „ ^ ffi ** ': S-.,a <v <V O' 'i C. < V- ^ O C O ^ ® *r^ ® <Jv<i* , P <§^ O' 'i

'•. «.."'<» <,VV' <t, a' ft; 'i. .?-u e A. 1^ 15^. ^ l*t 1 \t'S t

ft W i»^.

K;' /' “ f* *^;. *5 .f?, » fft fft .: • jsj' ..; -- - *• ft'.’ C 1r>'5 ra-'p"' .it « .:- . ;,' -6vr ©‘•4

(1^ (>»w .'/>. (h*> lk^•> • <>» -j--

‘

tt'- '1 •# >af cr(»> »w »s, t Jtf .i cj ik' cyjSf .'< ••• .4 .-t Vi

') :<.> ri; ft, <'/ ,''3 “* ft ft' ' V

>'

'.fty a-'-ft.- ftv , - I >
"i

cu

c-N

N

o

(Ti

o as c c

Eig

as w

§

73bJ

CJ

= ijs

«tOHS5 O •- as H

^ tj o S

o <

u

tfc >.2®

capu

r< 'j £ o <: M bj OU J> 7) cQ i-i

ft, h* a

ftu 2

CQ

f-U

:iu

N it H if

if ^ CS CQ

. I I s

w -• o o • w as B K

73 ® ® '- CQ O W • • II II 73 £ ® ® II II r fsae

£- II II >-• ^ £ E D

< « « 2 IS 73 « 20 wOO«U jgg-HtfassHS

^ o o o o w U EC ts « u 2

a.2

S £

h ^

u

a.*^2

*; '

53

*^£

®

®

®

<c

g

a;2

O 2 1^ 2 (ba, ^

+2

2

o

>

u2

7)

Z>u

2

o

U|b

j

CA>

b]B

2

2 ^-^2

Ij

k; « H*

C4 A

^ « •*f « w if 2 ^ ^

^ ^ 2

+

, i_i O

^ w W

© xa • II II © HU.

u > 2 uh 1 2 1 2 II /-V s b -5 «J «^2 1 1 II £ < II II ® 1-1 »-. CJ 2

Q O ® NH 1 M ] O 2 w O i-^ 2 X II II 2 2 u •J 2 E-22 2E-* 2 2 II 1 < 1 2 2

2 H '-' P ,i H W O O O

J « 2 2 1 £ 1 U2^ 2 0 U

Xai

££22

f-E- wrj

*n 9Q2 2

2 2

b] J

«2'

X0

N

W

iJ1

c

y

©

fi

\

<*'

a

u;2

\

©

• II 2

O /-« ©

. ^ es

. W •“ 2<wwc H 2 H ^ O

W ;J U

M

U2

I

2

O

o

©

o

©N

o u u u o uyyyyy uuu you w u u u

if

vf

Ifa t>'t^Ntbt^^*©©t^©©t^©Ot«NI^©©©©©t^©©'a©©©©vO©©©©©©©©©©©©'£Nt^t»>QvCOO'C©'COO©© ©© 000 ©® 0 ® 000 ®®© 900 ®©®©©'^©© 0 ©©© 09 ©© 09 ©©©®®©©© 0 © 9 ©©©© 0 ©C©© 0 ©

73U

ifj 'O N >5' ® r! 9 rM.O \© N M O' © — W ® Vi* (n © N 2 2“ ® Cl 0^ 'f* W v3 N W O' ® Cl CC n '» I'* 2 O ® -< Cl CC> 'C- ’O S. N 2 O' © — Cl

C; Cl C4 Cl Cl Cl Cl Cl Cl N W « O C5 « e?> « W «« rf* ^ iji ^ -^ «•<}• ^ 'i* ^ » W L? W ’O » W :0 :.0 W ® O © \0 vC S >© v© vO -i! N N N
- ; ' V'\>/

w

1

S?.

> m.. ..T )

wtv* V •'•'' S'

»%*

t

, r-

.J N

*«’ C"

?P»

/a

a

'-i X*

Sk. V'

. -', o

/ h» gpl-^ I-# ca'is

4> 5?r. <

i4

"4 ®

V. }>i jJj

V.

a .. o tj'sC

-• O if^ k:?:

.K?'.'a

I

»;qfaiv4

sfi -3 !#. >-1 ^pF i-' ii. •

..4

®

('ll

f,:

ta

as. U3

•s

11

ff^ K- V, >-<

iSA <

hs0? J:

C"

ly

',.•' M

.s; O

J }•

•r' if

f*i wO

rrO *>•'••• *

s.‘ >> i»”

it js ‘ (It* , i»'

[*) >rj •»»

ggli.5> = !? o Sl

^ 9» •

?•', T-

.5

y- • Ji* 'V S1^S

"« V.

-' ^

(> II >

iv

«S'

SS: Ft:

••j i.^ 1^3 0

'JO

ifI(

)i

I

•!

I

IS .*5. 1 1 1

I -

t i I

.'

» 5» «

t I

) :ri I

/ » J ^

I

I

•

! 1 i, "~ !1

1 i

1 .T« I

( i

J ••'

; }"' t

I y I l - I

s

)

I t

i J

o

3>

' *1^ . in.

l li . :-’;g

'» <*!-

V •> » . ;.'

»-n

(A

V*

' ft

:JX ti:® s

f X* o

JW.H

.t).

.<1 ^

»« (- « .o o :

.. « ^ ;rs3

tl ^

'***

5a">--{-. . U

H H S • w c: o

., t- s •

t/'

mA

iss

{Otd

Q

s

' n , '••' l.ll

, M *

5? >4

se c

' >

' ,‘ » • '

V

; %’

-1^

»ir1 iik"* 6

>s

,ri aff”

a

» vv ^ Kiw r- ip’ - o ^ ^ ^

I

O 0*1 > ;x

>, i- Tt

f-) oc*~ •. ^ ' i W- •. an *~ ® (? (ti

-?s'* . i»i ' fe

<t .1 ;.>• i*r .A

'‘X

>«• * s.-n; •-• fi «• -~J. gggl^cfea"’

si 35 to

>o h

??w

, aa*<

54 0 W

O •'i >A . ; w ^ »• a. I:«f SS' f5: S'

' '»

' v«r O O fj o o u o a Q w V O V o u o o o o o o V. o c w o

«!r’ C

\'^l c- V '•«' A-'; <;;» V ^ 5S.' HI *^> *'! a* «> -v v 'V <U.4f O' O' o <v <S’ fti.A- w » o O' q.'ift’Hp 4* >'1'«-’1 »i ®* 4' ’*s * o< H d J !l'

e-:* a- S, » p. s;; c^'^&<&'C O'® ?• O 5> ® $ C '*?,«» <u 03> $ c -“ <& P P'S P PO ® P ®,P ® P P P ® P P'P P ^

_ . t?f O

•il H H 4’ t.- 'ttf 'i' c ' 4/ <;<i '.' !* «,

•s' 't'

^1.' ‘' H«.’

' »*7 ^ tkia

. c;-).' ^ ^ ...

C <1 G..pJ t b:»* Cx. « '*Y >9 lit ii^ O’ k tf P A’t. V :! 2

'** *•' k ;i' stjiM'ii

'®‘- *' ^

«,. !,v ixf **». .•« »~ * ,wi ’fx Wf ».) «H Ixi.Nw Itt *"' »». »* •• .» X*. *•« w*9«* ir» V- ** 4-W 'cCs< .

O

.-J

o

-3

'1

35>

ff'

*f' M'

n
N

N9

I

(=)

9

Oi

r>

o u KP

\ CS I

2 h

o >] K >

^Scs

CD >J p bjh

II n "

(Tg-'

O

C5

S

c

p

u

o

>

o

u

> > « cS -< K PU c .p

Oh SS Btf _ Oh s ei w w \ ^

cu

Co,

-H*Ui

9

<i»'

e;INN0

1 h

O

t:o

NU

W Oh a h CQ i ^ > I-. I-. flS M 2 f- W •-) w a 11 W 2 5 o II h MM W o H ^

7) 2 II - 2

II a, 2 H o ^ a w Cu - 2 ^ **4 o < w ^ iJ Oh II *-• Oh H u H

W

2 5! 2 b<J h O © CQ W

<; O 2 E 2 o u 3 >-•

C

o

Cl

s

lg

: u5

^ BtJ 9 U

® H

a

a.

s:

o<

«

9

Cl

K

u

.JI

7i«

9 ^ II upr* Ch

y *- a 2

ca

a

o

%

1 ^

Cl \ —

• u

^ a.

pH M

Esl a •

10ciU

o c.; o UUCJU uuu ou

o

b

o

o

99

-CICT

i

o

E?. o

K»9•9

d

o

Cl5^

xS

Clfi

\

C5 «h ® «

U<S>

Oh “< -fil

s

o

s

=> 9 aoM CQ

< t>

nJ O

\ t

•O 71 U. I lO K O •WO

sSh^i WCXgi • 10 Cl a 2

03 Oh 2^0 K

e -gPO ^ • • • •O

o le lO o

HO

ag

O u

i

o

w

©

9

- Cl

w

oc«&oo®ooooooooo®o<$o®*^oo^9C9^«**ooooooooQoooooocoooo

sc3

u

a

It

-V( H

•It if

^ n vp N © O' O -< M fO 4< lO '9 03 C © •-' Cl C5 4* W <0 r- CO O ® « Cl C5 4* «0 ^0 N CO O' O — Cl O •«? »' O t- cn O -H N*N«-tHt-i>NCOCOCOOfflOeO©COC3 C' 0' 5'©©©© 5‘© 0*© 0®0 ©© 9 © •©©"'’^•^’-•-' Cl C'l « ^ -H « ^ ^ ^ ^ ^ ^ ,H -H -< -H -H hh — -H .H -H Cl Cl d Cl Cl N Cl Cl Cl Cl CJ Cl Cl Cl d Cl Cl Cl Cl Cl Cl d

d

Cl

o

u

w

Q

C.1 w

71

Ci

tif

•• if a if a if

>-M ff H .jt

P4 kJ

Sc; o © 73 2 O

u

a

2

2

Q if £5 if 2 if w AC

ifif

• t:

Oh U «• o Q p

2 2 W @
fes

I'

**•

' ftT

b

1

ct

»? <!S » i.' » «>P •w f£i

53' o

tai

C'tc. C

; a »"i U 'Jt fe ;a c

I:

*« .*1

?>3 W

WM

-S '4

:k /

w'"iv ***<

-•X

I'

r: :s «-jf

r*.-^

'

,..3 ‘f^ '*. & 2

' f

., ,« > *-t "i '* t?

'*'

<v •-* o<4 ''

ik'.a

i:i

>“J

Ml

•43

i'4

' fN&i'l-

«. ^ e» , ^

*-» Q 5^

f*4 S^'-. ..td

< 'w.

-

. ‘'VL .

,

'•- ^ ^ , 4 'N

»w "^ o

Cil M.C

•4

fcQ

;5S

•• o

v‘

I

c

(f* »> w

.€5f0>

,. *4‘*

h-i^» Ji

.s

tWff ''1* ^

• w .> |S^

'>V: t?

r-*<

'2: }.

»iTf i

*

o

'if Cf) 4

7U'a , >

Sg:

>r.i

Sli

rW:-"'

fe< * > w

a^?«!

Sb

i^'9

'4K

, -t

,3* l-i

«#< ..4 V. *

y* J. ' ’

'»

4JJ w

:fi4

c„.

liJ !»

' *w»

io

!T3

i-‘<

IWfio

o

U'i

;,fi'

, X*"

'I

' f4

3

iA"

5Si

}Mi» ^

tsj >,.fi ,'4

>%» «4 fft I

• .-'t.

£iSt

|V4 |..'W

<« j U '5 .'•!»

5; *r,j 4r <> SSi , -. i* i-**! ’.«« ^ H -V'

. iZ.-. h''

©

’t*'

0

^ s.

'

.r{ . *''>?>“ S S^ly yir«

lw4f'w'' ri ' .

' w

M

ii'

O

p. -> \ o '410^^ O y

• /f* « , 4i j

,:t S. r i

'5' ‘i*J^

:t R

^ 'b 15 3 ^2 :. ^. . ^ ^^4 © ^ ^ b ^ 'fe .•» -w b ;^. '* fc U ^ t

’ ' ’ "’

»'>, , i4»

yf
C'

«<

N

o

<a

• ffl M o ^ w ^ p /-\ II fa Ed B BBfa IJ Bfa w

fa U F It '-J 5

fa « E II P Cd 71 ^ B U II w F

II w K

II B ^3 • • II pBSP J

< u. p

I < U (Zi

C5U

Czi

c'rp

vo b

'J* 71 a

®

c I

• o K X, '• B O i

C l V3 ^ W >0

SC ^

^/2 U3 ^

:§2

B J I U U ^

Cd - p SC O P

O M ^ 73US

I Cft Ei^ ^

iCA CQ

B a. S lih

SdPO^ NN FoB O •-* J

nJo

OQCU O C/)

I B J

lO <

u u

io ^ I M CQ

I B

^ W

1^

I N U i S 71

I • B •“•

•-' B

I

0

1o

U]

B

B

CO

CdB

a.

o

b^

- 5C Ed §

CO fa

Sd B

(O (d_ ©

CO >J

^:9 . fa ^B

faO

B

H

B

B

©“ fa I CO I B

fao

(S

OBBB B B B B

« < ^ ^

O

>dfa i4Ed B OB «

fa fa CO

. 1 9 U

fa Ed ;x: B

faB

>•

fa

i

XM

B

B

I Cl

B c? o

fa

^ w

as

^5

fafa^

p'^

fa<

a

BO

fa

fafa

« E

COB CQ S fa B O

fa

fa0

§21

^

§ a

z

o

'OB

fao

u u o <o U Cd Cd CJ u u UCdCdCd CdCdUUCdU CdCdCdCd ousdcjuoocdw cdccdcd uyy

r

K

a

fao

s

B

\

fa •-“ 0'-C'C*®WC'J00M ©©©©©©©«© CO\--'>NNWW(MM’--<-*---*-CI- 0 N

S®n

• u

• -H O

ts^ fa N

1 CO

fa ^

e- a

faWE-

•• fa o u

I'* Cd Cl CO <M.-5 O N CO O »** M C^ ^ t- C3 -> d -< Cl ?5 1^- O t"* C5 ?\ C ^ ^ ^ ?0 \0 N fC t*' T^ <• :o r< »-• ^ ^ ^ ^ CM W CJ C3 Cl d M OJ Cl W CO C5 CO CO O C5 CO CO C3 CO -t -e ^ ^ ^ -t to W I-' -0 L'5 LO LO
c-

**' c

is,

v-5 tit

rs c

f;

•tj

>?

Jh

'4

1

*»

S

» «i« "i^

«!»

JMTij (*' **!

iT'. . > ,.t?_ o

•-«* •s •<

w .,

^•»> U

>

p- "!> t‘

f'-' M '•

f;.: w

«5K

r,'^ J0

:<U

iC'

s

I

' *»

L\ O -.-^ 41

i:^

fel'SUta

ci' S4

-ti

’V^ P'

'V

A!

•:« ?s

l‘^'

r*S

I S?'

'«r

a

•»)

'.•*» sr<

s«

*Vv

•f

,

ii!

!-0 IS

>-5S d

C5

JV. A

C1

;.5

2H

?5

Pi,

W-*

rsM

I

I!

55w

f»P

<4i

fe

:<S5 o

i5. *<

ri

:

. k>

la.

Ck’ r?

‘ Ci

t:U

« '‘i^ ^ ^ '5p. S3»

tS

fi5IW

1.

}

..'1 w r‘^- ‘ 'i.

. -•’’rt

. ft!* ' ‘

V»- jwj

IS.’

> t'" ll

»fw (*« cr.ta i‘"

,?g

3?

W

;\'>^

U

I

t-

> -53 S3'

f« tSksfS ?* 6^185 : t.,

S'., 'S'? r

\ /%....«

'A'' - 1' '.Vj'i^

•; a'8 . V -

<?^ W,*. y^ fiJ

fe ?; tS

‘^'

.' .«» ‘ 6« ;.« 'V f'S *83 C'

I ?**V I »x„. .“Si W f-tO&O

rfs'ii " 3SO (SJ -4l

'*’ '^4 ,-. S *< ^ .c- j® pt ,« O

'

y;

" Ik ^ C < =“• ilM

l>

N »..'

i ,. fv* s';p a

. 5 .' w ;

;.' ^ «*rS*ii;*^, ..-4 ".j ^ .. ,>> i£<. . . ae

s

’” W, o ^ *’<

{ % . V* 1,,^ .rj ^ f y w p

u , "i

,

**‘-s fe'

I-' ', "•

£C{>^ «

'"«

wife I

C4 '3g c % ^ (tip y (43

4le I

u» ,

, felgSSiS PU‘ 3S* PI-<

1^ ^>v

(s4 > ks? U•J

ij ,:

(IIt «

' « ^

^^»i

^

*U' .S Icf ^,

.' , ,Ct¥

n

i| *'

it

II

ItM«

)l 11

Ot'!' P'T'J

3a.*..

>t* w

AJ m

<T> *C it • S, <,

'. 5,5 r.5 p O y J,a p S;*! p> o pU P P P, P O O p O O P a U P O p j pp p p

<?iSti-iii*v >;t*0 -po 5 r «'»''? <IS> “If itf.f* (''••« V3 J».-1S

<. . kM*.' ;‘‘ '*.f Vi 5*r t’^Hv ^ l-v

*’* i.f f-3 W f'J n J-'l

'

' *•' >^. •'

I,' I <\i"e

t'J • * '" ' ' «-» 4* ^.-i ' :'& *• «*> P'i<5 H ,•; I ^ 3» fc> y.*.*Y.^rt •V.iRi.'«f*,4.n K •• ..

-*!. ;,. Ct -i* •;* y tJ ^ t- -ir /j/'Vi* 4' t>, '. «(>• i'8

'

i'-,,. 5

'.,' ?<l'‘’'i -V'f-j '.- K I.'*'

I

* • fc.1 ItK K(Hr->»* #«» .

;i- 6'-‘nii«i

>

I ',v

F>*n

W ’.i

» *?> o lie -ft /«,. * 'ii ^' o if.' <P •'!

^ *3 »T ,*•• *

*,£5 p.

'"« ,t O'*

1 -.1 .T'l-H A j

r.. ,o

’V,.',

:i
N

N

<S>

Cl

O

cC

r.

vv

<

>-k

1

1

dCl

o

«) g ^

3

.J

>

w

o

.J

3 s

• ®

® a: » H \

I <J r;

tco

u

.

c

u

o

o

u

a

§2

w

COK

o

, u

as 3 = J M ® Pii j^Ci 2 K II b <c g

IIU

ISw Q> Pi II < 1-1 C uc

“II X o •-- t<

• !-l§ ^O&b,

« H S CO

\

\

66

m h M M

dictf x X

»

o

I

CO

9

o

C9

as

*a^ u

X

p

X II ^

t-

.J s

5

O X

PiX

6

s»*«

H

s

cCX

X

I

o

fe

t-

/•-.

?5o

<

§

X

'/) CO

X

o

r^: o

g

N

U

COA

H

h

y

y

o

3t

if

f '

'..• V 'j y y j y yj cj u u cj o u u u y c; y y y yy yyyy y u y yyyyy

i'r G's^€^0'0000®®®0®®®®®®®9®®€'®®0'0®0®0®®0®0®0®0'0'®®®®00c^0®^c'®^

y

o

o

y

if

vf

r- cT. ^ — ?i « •j' 1!^ V© r« CO 3> ® M p !o '© f'* 00 O' w c5 'tin \o N n o c?- ^ i o n P O' oi -.o ni< to .c t

• "i o' •? iO?^OOvO'£''5.0\£>'©OvO'Ot'.NNNt'»NNNNNCOCOCOcOCOCOCOOOOOdO'C'C'CO'0'C'C'C'C'C3©c5®®OCO-3 —

^ •»»-» ^ ^ -i^* —

111-

-^0

CALL

GENPOI

(M,

N,

flTl'tX,

FLIP,

lUIO,

CLPDEF,

X0,

DELTAX,

DELTAY

Il'i.

20

1

LOWERS,

UPPERS,

LEFTS,

RIGHTS,

IIU.

20

2

ALPHA,

BETA,

GATSLA,

F,

X,

iiVRK3)
V ,Q o r C'.uov 'uw ^ wq o c,y q c^w w yocuv

' '. ..O' ' i

1 - ~i t -a' 't: &c-m/s> o ® o •". '?.,'&«>. .'li.'e-- wiNift ie» <1? o.-st »««?« <^ <s'<&<5. *o>» <i «

V • '- '/? — - S3**' «'*»'*« »»».- jl-J i'.J.J.'S >- w W S *''* V? W **« ^ « •«'<'>i3 - O «w l'> q. '«' ^ H '

I

" •'*

.-J rx V f:**,"' v'rj'i®' .<i «v

' *V. «.•> ft'— i< ^ •.fe.JJ. •iy hf tO- <r" 0».*i4' '"s -• «*5;'^ Stl

'i c>-<: ^ c ?t 4 ;* •'5 *'<•.> •?, <.? «/ O * (is 'Z'^ !»{?;> ®.fc -'. •< v} <>, -j/vit jv 0- c»

*-

»• A 4».v iMk .< !>:*•} ui..^ .

;;
NATURAL

ORDERING

USED

N

t-

<S>

<o

cn A

o

« <N N

tfci .

*----r-US

R

Pho

gR Pd

cn

II II s U II 0. ^ ^ ® ca ^ Ci M Cs] O O

«N wx

: a •I II

Ut>.^

<S>

b U<

E^ Er-

(k, k cn W o

O cn (A R R CM U o O R K

V u o O •«< Pl. A H

(» ® ® b

.j w

>-] ® ® o

CM Cl - cn

H 'M oop W 5;; P

U M U

fcJ r- S 5

tfrsQDK

w o aa p

i P oi w uon

C6 pi

CDOu s:

r<N w PdO W .

a. PCcu J w

<^fc, o —

^ PC H 04 01

cao « ®X

w PdO

Pd •

O. CC

a<

<1 Pti o —

7i

S3o

CPK

H

K

O

u

ptl 0

1

a

I

o

u

®

o

® ij

P5gIb

cC o

B< U

5 w

WC4

•

c-i u. bb

E-H

z; K »—1 l-M cC laC

ILi 0<

Ph. u.

CM

I g gi

? R /-> . \ ® « + JC«' « ^ ^ te o

<fiS c w ^ o § - “-§

® w rt K

• Pd II II G> •-< ® g ^ , ® PS « '-' g W cu

II E-* PC S3 M >w SjnSPS^ O J R O •- g^O ORPC guo U«»

®®

CM

W

H

K

>*< U

04o

^ §

soa

Pdu

(A

CdQ

P

>-O

®

CM ooo u u ® u ouy ouo uuu o oou

*T

fv ®®®®®® 0 ®®® 0 ®®® 0 ® 0 ® 0^ 0 ®®®®®® 0'®®®®®®C1 ®® 0 ®®®® 9'®'3'®®®<3'^1 ®®® 9'® 9'® 3'®

ii M C'l CJ ?J C^i CM CM Cl CM CJ CJ CM CJ CM CM CM C4 CM — f1 CM ej CM CM — N -* — M — CM -» CM CM — — — — Cl — Cl CM W — 04 -' CM — — — N

>JC

u

CC

w kT O l- PO <^ ® « Cl ca ^ n 'O ^• W •S' O IN C5 ^ « \0 N O ^^ ® C>1 WM* «r> ® N ® O' ® CM ca <• W 'fi> r* CO ^ ® — M CO ^ L3 N CO O' O '• Cl ^ — -*-'CMCicicicaciciwcieMca«««coo«««caij'^^iC'^^^'4''M*^i!a«otoo»wioi.oww»co'3 vO'©'0 -ovo^v©NNN

IkK
v>f

vV

3

t'

*v?

:,4

ipi c

Sti

r

•

U'u

w*

iB:

>•». is

» ra

•’3 ;;

'5^ .?

W - ff

V- 4i

i ; ,i.». *»• >»' % > a tt O !'. >

•

-^i n

.'-. r ofJ . Ci

o

©

y>

trd

I-W’

C ’ c ...-; C!> -k

U^l

f|U- s^

a

-n

fo I

“ <*»4

i»x'

t^\

HiM( ^1^

(INK *N»y

if,

» o, & ca

.•t;< «(- O « * , ^ • * f:,' vi* (»«&.; 5 ,. *1 ^ Ml j' ^ p

•*5 »S5 j

' tl35 £i»

i'4 ;s;Q ,. t '5.%*-' .•’;

»'• '^

fcV. Tj

’

r,i . T M S?,

n’ :i ^,*"

!»*•

.4

Clo

o

IVce§

•>W c

r*»i. it?'

fo5':«^

<4 f.

u?o c?

<t' Sr u

i

S

S

nfci irt r^

«s K

--‘ttS i

,i» *lf r P

;3»

jAw a

IsJ

<«<

c» 31

ji'_

»

>?« ',< ti

(ai «u; '3

S'S'

£Z ...

T* . ,-,i^'

u iJi

iO,..

’-5 '?<>

"''» 4h/

|I*4

-‘ I’ 'M-'rO

f.,%.35;^

' ly ,7^ wm, ^

.'*1 ^ < ' -n o I.'? ''fl ' fca

'O, W'U!,»^

^

c. I?.

. r.5 'g ^

U !’‘'' '~ 4"-

'

|^^ .o’Ue

'i, ^ ill

%• M

t-a-H

*** ^

i- t Irk*

Vtli »

' '

J?' l>

i.^ V1

I’

V4

ftl

S2* S4- €•»

•o

I

»ii3' O'

a ,»; 'fs6 o

tv

-.;« &«.

-.1

.ri* .4 t*

O

ss

< U (»,

v3>(»-' "...

", f? fv

,"S .;-

Au«i.

a.

fVM

.^5.

<»

o

Q

. , '}« I

.iS",

t"? o <«; c :.j c;-'C -'J o p u :P' O V o Q44 W

,''K ;'.!f

» »!? «. O cs- ', *r •*< i<5 y>' ,/.) VS,'*

; 5» C '» <0 O (t» •<'/ rli !'?• O i!> K> O 'S> O •*> O'C '>•

«•?. ....', S 'v' ® P -t ^ ^ f®' S? Si S ),ef j/5 .TO, »« '#5 «f >• i4,"*- i4 W V' { ,' f“ 14 tv iij-#"' t'-‘ V'' i'i -t'.. W 14 0

W-

« s**,**f«*. - y t m ^ '*, . « *••• «. '• * *; k • *..'4. N V -•< t '.^. < f '»*',* -• T *•«*«,•• •- . *

'fk'-r f« -4 t.'i 4 e- » 4

‘ 4 'r, .11 . js .5 f> ri *''• '« < ** (&•> '« 52 y% i/m 4 3 s^' «, %t'* ;?r t ; «' >w ®» ***

•~J ^ -r.JK^ far MT *•' 1.4 , to »a !»«• «• »«• -tayr^ %< ,IIW »a .*>» ^.af »".« •“ A ,•*“ '‘‘*’ “‘‘ "“ '•*<'“ i" ’* •*• '**• •*‘ ',' '* ^ '.*•,»-'*» »*
bio

<

S'N

©

CJ

Ci

CJ

•<

Ct. 05

o

^

II

o u

M

M a< ^

Pi J CB

t- t=i u j

C J

lx< Ui ^

'22 —

U

C ® J

O •<^ Og^

• PS 5- w — s> h4 C^ Q

•tg

h to eu-HJ

^ ? u

Ei<

aso

§

y < (d CH • y

Ei^ Ed 9 < Eh as

CD a Cl u O NP« ^3

CM Ed

Ed ^ w 0^5 a 0. QQ y

o w P 9 (» >-3 02

u

QD

SC \

*^ K —

- w>!

bi u u

II — U

^ s

® •“• — (K w w ^

C5 fr. K< {-

8S o o

o o

s o

M «

CM CO

Ebo

>-

C?U

USy

CM w

!3 ! ® o

— J

(A y

cu <

W u

S|likHi o3 asO( goo ogoi Sbo uSe!

o

9

S 3'

M NN Q2 CC bS H

9tH

9

9

9 — eu

CI H -S

«>« s** ^

co oc

• P II PLi II Hose'^a

SS »»* pJ ^

- JE-Ph

OS iJ C. — > jge;

w y Ed P cu

%

o

p

Cuo

CC

I

EdOio

o

2h .S 0U|

O

u

CCp

9

— c* eC 9

Q CM

^

5*^

« Ed P

t . ^ § n w td

^ J Ed

&,p \

Ed • —

Edg«^

u ed H

g gi..

j ^ o

O — u

s 905= y

o

y ' w 9

s

\ o

u

9

I CM ®

P ^9

OEy Es

V-* —

9

ii rd

SI

(BI

9

O

o

y

as

9

o

u

<9

a

9

EQS

Ed

M

y

w

y y y y y uu y yy y y y y y y y

O O O fjs ® ® ^ Cl 99999999999 — — 9999 CMCMCJ — CICMCM — — — — — — — — — CM— -CM- — — — — CM — — CM — — — — — — — — CM — — Cl — CM — — CM — — d — — CM W Cl Cl — — —

•y

C5

CBC3y

cc

C? — «9 O N* P 9 O — Cl 9 *f Ki © N C3 9 9 — Cl CO M* lO '>> C- P 9 9 — Ci P 9 » ® N P 9 9 — Cl CO ^ 1 C- •£> t- I’D O' 9 — CM CO •?’ in "O t* CO 9 9 t^NNNNNNPPPPPPPPPP 99999999990©09099999 — — — — — — — — — — C1 C1 C1 C1 C1 C1 C1 C1 C 1 C1 P

^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ei CM CM Cl CM Cl Cl Cl W CM CM CM CM CM CM W CM CM CM CM CM Cl Cl CICM Cl Cl Cl Cl
v; - -

'ft -iJ * 't Vy t> t? « -, t' 75 *‘r

**'' *^ ‘ ^ t' -O ^ 'S •> ' « ,£? ‘^ ; ' “*- • v O /t <s '&>X UK ^ » ’"< .|fi

'y~~ "Mr ’•« -« i? '"M I' ’«' <"* '‘"r ' •» W' '»

rf'. -.::> -I' 'T- ^ c ls- t-t tn ** f: W t'J «

i 5

>

; V”. »->5 ’

*.' Vl «•

/;*,- |is

, '•"

i-' • ?) .-} . •,:. h ;' ! "

”'. ?/*; »:»?,. iii'jfli..'

•“.. t or <f!f ti> C- }fJ - f

,' W5 -I fj* Y

'

' 1: rj *'• *"9 C? 0'-^ *" **' • - '*•

Xi !'•> 7 *

*•'.> O'- *v *<.

' *!%

'> .t; 4?

.? C-" ^ Vj I v.^

t. *IW ^
o

c

0.

S'N

o

o

Cl

Ui0.

2

Oh

0. 22

Sc B

SJ \ H

' B U

*j >; cn < II U II II X O

I-] lO r< !b ^ O U Q

ISCl

rj*

?

B

O

u

«

s

lo

^ Ha (Jh:^

9

9

B

i

••

u

B

15

(A o •

lib, Q a CAB

• a 1 O •• b.C0 X

u

oa <«> o

HwM (ij o S

< o

[l4 M 3 Pi a NN ft yu

SCQ

E-ffl §

ft

ft 2 h »-« NM

Eb< u

>

y V t>o

a

a

' P3 M M S rfi rrcco

B

II {*3 ft

II O ft

11 y <1

II t-> s H >—

1

n BU ft w

o

EII •- 13 o •—

II ft B -« B

11 ft K ft

II ft

II >*p > ft r_ M ft o o-«

II 71 E- « cc u ft U < •5 * B • u wP ft < d < d

n y II B U ft § ft C ft

11 0 M <s ft ft

II ft ft • » »

II KB <w w

u u u uc:;uu uuuuuuu (J

Jo

b

S

OO

Cl

H

s:s

ob

O

C?

nJO

(Au

o

a

*C4'^Cl«^Ci'"«"*^*^ClClC)C]C]CIC]ClClClCl

— c’o»?>wvt't«co<j'S*-*cic?'^L'5'&N05o'0-'Cie5'«f‘i'9\©NOOs©-<cir>^w-©r-cjc-©"*cii:^-}'nvCNe5a*s-<crpJ^oc:t-t3 e5CT«©WrteO«?0'J'^T*«^^*i*Tt«<.^,J<«IOI!5IOttjt5lfl:f>WL5vOxO>OvO'ONO'0'd'0‘SNNNNNNNNNNOCO«caOCOCOC3a d Ci Cl Cl N Cl Cl W Cl Cl Cl W Cl Cl Cl Cl d Cl CJ Cl d Cl N Cl Cl Ci Cl « N Cl W Cl Cl a Cl CJ d CM W CM W Cl Cl Cl Cl C3 « Cl CJ Ci Cl C! Cl C l M Cl Cl CJ
c

rfl m.’ S'/’f-. -

<r^ #c f'v • ' ' ' •' > :.

'•. S5i *? 'A - > > St " ' " i '' ' £( f"'- r* t‘‘' <?5 •: ' Vi w ic w t^'

r,” t.^ -^1 'S. ; 'S/c* *' ® tl *' "•’•' '’?! '<5^ <'4 '

’ <4* t- O- -tJ nJ fi Ta J ?,!• Crt "« f*s: <• ^ '& 'I'” >’¥* it

• ••“ * r> iy(^ "-In » f** n trtm w*^f> i«

•.«.:•?. 'Ir

?*f *r> •<#' *\,' **i fA ; t>; '.j n-nvai?*'
b4 O

<

O'

h*

a

\

CO \ © • • • ©

M \ nn a CVJ • « © g

CM U • U3

On

' CM /-^ 03 5 Ok U vN ^ *N © " fa On © bl • b. S • • X 01 O •

u

09 W

S e:

OUl

5D •*

a 8

H 2 ^ a

u u

q 3

u a. 3 ^

OT X

B ^ X ^

o wX

o

X

o

t*<

a

bl

O

u < X

s

8

o

uu

C a, “3

BB

x^

w a

O.U)

o

b< oc

w _ o o

73

«

«

s.

iso

W

50

O

I

a

a 55

ss

fe -

^ —

73

C5

05&4

cio

0c<

?

\

K

o

E-X

-'c^ J

u o

U CO >

a:o

\

X

Cd

OnO

n

Ed

0.O

K

O \ A

A X

V

73 J J « g

CJ

326 H ©« w A (0 • * < \ — •-' §.

“aC^N 2-

X ce

CO32

X X

X o

KX

a

QQaX

<

X

X

<

X- ^

i

-

fe

X

«

o

O © © © ©

w w W W

Cm E- H E- E- fa X ;_i < 53 s

X 2 2 g 2 2 2 2 2

o o o O o o c o o A Un f-j b. b PM ^N pN © W © © © © O $ © O © » <• L5 © N © © © © © « © © © o © ©

01 03 © © © 01 © © «

X

9

X

9

C3 X

oX

©

«

o

bl©

N©

05

oX

©

n

o

«

u

C3CO©

\

©

c

bl©

©9

A

A

b.§

©

o

<j

o.

\• • o U N td W yj

fai ACO

01

• O ST b, tJ

it © • • n

it © s itit fa *

a

iia

a o©©©©©©©©©©©©©©©©©©©©©©©©©©©©©©©©©©©©© N Cl ri OJ CJ (N OJ ca N d Cl N 01 01 CM W OJ Cl W OJ W M - - - - W iM N N M CJ M - W — g 2

O A

X P

o

7)O

U

er*

J- © -' M 05 T 1 5 0 N © © © — 01 O Ii5 O N on © © — 01 © '}' lO Nt N 50 © © ’« Cl 05 lO \0 CO©©©©©©©©©©©®©® 0 ©©© 0 ©’^’^”“'~**^’~’~'’^*^^ClClC10iCiClCM

Cl 01 'M CJ 01 01 CM 01 CJ 03 Cl « © C5 « « « « « « rt « 09 « « W « « « « W « « « M 05 05 03

M

EblA

X

ta

*

*

*

K

X

O

g

a
•>f HP'

'A-' '< '•:M

' V*

,f

' 'f'#*

If*

jf«•:<>

O

tjq

::;i

«ja

fi.j ?<

s»c•r**

'4

J)c

C503

>-<i

CH

<Si

k.

' <•> /

O

<»

•»v .V

«4gft

•4O

;y

'.4 ;no

ft

'.'.'1 lv

,-x

- -4 fS‘

*«

H'

c:

o

w

k.

«>

kJ'

'

,

;¥.,v

»

c

«-r

buc

U?

C4

vV

SA

&

'«

iJ

.‘ii< I

’ ®' if

0?

F-w

V

soa

Js^f «l

f.' H

p

S

t3

I;

.' <V

' 'IW'

•» • 30

: P-4Cl it ^

„ > o - fe o

IP C V.

'•’Ct

dlp

s

...'’I;-! f

a t'

; HI: » C

a' ^ 4

.1

::4':i

c*X

«

. w r; C ‘ i. -' O ^

U V

ft S ^ ^ "4 o “ SS S :. ::s -4 Mt

I

' M S-‘:!Si »

g .g' t •45 ® O

rt . .r ,45 ©

Ow <j5

<5 44 . Ok C

fJ ' O

rt'.

'•.* '•«

ns

?>

<S »

,4'«W

:r-

«*i|' w3

••

I

0 ; b

rjj:

vt). C5

•0

>wr , ^{5

* HO" 10

'U'. u

I

S'

.O'

;n>

i;' §oj

I a-

• f

i>H 0>"/

,

ft 4> . r-'i Wi ' -4>

'. 1^ •

" -!i I .0 . 'c

•4«r

Mtf t:/

4> W

>

•4

t^V S

S.

P 5“

ci 0

"^n.. r;0 C , *-•.,>

C5P>^l4

’ hO w

’•

’M, .i»

rt4 O W J4J

i!' $'Ha ^ .0

«4 ,V»: ^ »-

sJ

'

»)a

£3 «t ^1

•i>4 i. ft O

4. i.., h

’

"?)i ic

O '

I - s.

•V

^ ,

*• 1*-^ 1

' i‘

Iji , ' . fc'.’ >ri «

. a

0 ., V3 O

O

'S? o ft o

Vi.„o a Cti w

4 ' O 'ft ft

' ift ' . * ,12 § 8 S ^ S £ g « 8 msg m'S'HSS g fi S

*

I

.-! ?

*' 3' • 'S?? K *?.K i'iS'sf. fig 132 4 2 2 §,K S.Sf4

).' Wf* S't.? }

?'? *. * ?

i) t!0i^'K9'Kt»'<»Ci'-t^O PJ 0»« 0,#> «>‘1«>C9 W-ftrV « ^'.W r «» •'/ W WO# M M S'* .<% »;»'• ,r • • -.t^

it

I•r

.^

« «

I

,/.4 ^ V *i
(T' N

N

<9

Q

^ O u

u e

i(/) IP

QQ U

un

II

II Hp II

II HP II B H If B • II II B >B

y GO U

II

It

IIIf 3

GOBB II uu II -OP II B II O — < 11 II H Hp! II Sh II O II H O u X RAN II B II o ^ S Cm II W II

II BOO II • yy g B^ m

11 O W II B II bi O II -By II So N

» >Bgo II H E j3s II H II

w

0 J R n O •-" H H ® «! H tJOUU ti

sc B M

- O It g„a: — C •-< II" P > ‘O; II §

J <-• u OH II 00—11

II M >S II

I, M — II

ii B A U II

II H 0 B II O

SB 9a oo

S5

OO

PH r* — —

M M

O O

B 0

O O

O B

e o

h (si O O

99

OQ CO

SB

§

U1o

\

X!

!3UO

o

h

b,o

C5

GJ

00

00M

O

g£

GO

uiU

g

7)J

GO«

CQg

GO

O

GO

g«

“o•Cri -

g . CDf-OtCJ

i-i — <

-B0&4 - — faCO

B

O

i|

\

M M

B B OB

BH

PhB <

-o

'<

mJ B B OH W

GOh|§

b, B

bi goo

B»

Iii4 H I*- CO c o

B B B

B U

CO B

g«g

2 ^

s uH W

CQ — ffl — E

B!3d • H r* gg^2

OH L-* j - BB O OO B

B B P O PBPOH 73 Shb K ^ OT O

BuBr/;

>o

— I

I —

+ — B

+ — BNwO

N O

OnJ O W

0 % — a

»f N

it ”o• w

B

II B

0

B

u u u o cj u o o rj y o o (j uuyyoG'yyuoyoyuouuoyuyy u yyyyyy oo

N

it \

« 1P —

if 1a —

^ 1

1H N

B C

P iNH

• U

B 1 >-* H - o B B 'J' —

1 CC

if J —

V -B

y- HM

¥:

if f H

it •• J

Cl 0

oococococgcaocococococooosoQOcoosoooooococoaocoaoocooocaococococeco‘»caoocg<3«co — 9>o^0^cooooacococopcoc^co

I ^ ^ ^ ^ «i^ ^ ^ ^ 1*^ ««4 ^ ^ «v4 wm wm 9M «« ^ «b4 vi4 «i4 ^ w4 #i4 ^ ^ ^ ^ ^ ^ ^

'«MO'^«'ONfO(?'C' — NC’jttWOrv.Oe'O— NOtflf5'ONa0(5'®-*N«Nf<L‘J^r-MC'O — »r \S> N CO S' O N O O

^t ^ 'j* ^ ^ W C3 L" W « » W

a.

O'N

O

CO

(=>

PIo ^ o

u

w ^

« /-« p; B

'EI U

s

§

B-4U

§

(dB

X

tt]

o

u

0.

PI 00

?r

»7if a

u

B

B 5 R»0 t— 1

. nJ B H

II II p It II B • 9 • . Ui JO . J

B

M «

^

U u o u

©

ouo

cocococsoocooococococooocoaoco

CM

+

+

CM ®

u o

S2

w

CM:liS w

r

+ N

o

<B

B

O

**O' E-* H© J < • + • NO

* B

« < >-s B

"S3

a w

B

B B B

B «

o

d

B

B B

9.. O

-«U{ - J

CO CO B II B B u s>-« « «

>*1

B B

dw. J B J_ M J,, PM 0 rjB J B J

< + < + H M- B u ^ u b P ^ . 0 b a *^..0 p 0)45 0 JP Oli^P 0 JP OBP CO ^cn 3co nco «(0 V P 50 BP B m Bp BP ^ u 0 D u OP II OP II OP u OP II W M 7) «co — CO — 00 — w

<! u ^ 1^1

§CU

00 B

•< II 13 U

P OU

CO B

'i II vO ri ^ JPK

§ CU

CO B

< II N

h4CQS

g

<

COB

^ II O

U

H<C II C' U

^ € 0 J UP JU p5 p

P B

COB CO

UUCJ UUU UU VU UP u u UP CJCJ UCJ p

pcocos9PPPc3cocoaooasocopaeoc3ppc3apapaooaaococ3copcoacococooocoaoQGOc9coapooo3c9ppo3

t- P 1.7' 3 PI « ^ lO V© N P > ® >« CM (."p '}• 13 \C N C8 O' © Cl C^ ^ IfJ vO N* W O' © “ PI '?> <• O N C3 C © —* PI CO ^ » vO ^• M O' n -< l3l3:3'©©'©'©'00'©©‘©'ONNNNt'>NNNNNPCOPaPPPOOOOaC'©©©©0'©©©©©©000©©0©0'-''’ 112.

18

C

LOCATION

OF

VORKING

STORAGE

110.

16

PPARMi

10)

=

SUBGL

+L

114.

16

G
» »

2

'

: :-.'i <- V

,”i i, •,

‘-. / w 1 V' .- ». b.^ •, «.; j .V ,t'

-3-': •’ • ^ ;

hi . 'A *'?

m

A4 .'

', ' '3

5<

* .0

* o I e;j

ip-

.» vS

•

.f -A

‘>9

1

**' o.> . ' '’' -' ?' • ttX^ I.' 0*^-

. , rW

..'tif .

.

<

•»’

J/ *,,’ C? .> '..' *•>,’ r.^ sU^

SI; t? . •: :‘hi: t' f ' ; , ' '' '5; ' Sfei i:; ^ a* Cf ^ »5> C\ V'

' .V ;ii « C. •; ':' ^

r^. * ,f ,,. »*. » ' » -.:». J '. .vs-!. • )»«, • c *-> V* *— Wt V« '*•'*> '''' .><- W vi M i«- •» . ,V W . !..> - i, ». •_ f.

C-. rs ’'

't •

. ., ;r^‘ -<1< I :•' <jf > -i ''. ' ' t: ‘'f u y S . V V, krr

.1 • ?' >/:

, '>& ”

* V. ‘i 5; -,i r 5 “w ^

'(rO-M*!: is? «: «» *t <•

•'> <,' «* . . . • iiJ V3 «' ... „. -V *« *.; ; ..^ .4 .. i ,5^. /j, x;

,

y f-; ' •'. <5i5

••;. rt'T* <» <V
113

.

18

C

116

.

18

C

IKJTIALIZE

CONSTANTS

FOR

DIAGONA.T.S

117

.

IS

C

113

.

21

SFACTR

=

DXDYSft

119

.

21

IF

(FLIP)

SFACTR

=

1.0

/

SFACTR

rt

bi

'i

.3.1

O'N

N

0

1

k

on

. h. ® <

-* 73 • Ck © ® I 1—73

II U II II U II y .J 3^ ^ ^ ^ n iQ u u

CQ a © OQ c © ^ © 5 b © p

73 ra 73 73 73 73

ou Ch rv. pi. B.

P-4 P. Oi. P. P. P.

«M I

|Q 2

a ©

gg

+ + + < CQ U I .§ § §

!

M 73 73 73

1

II II II II 73 7. CQ ^ n u s K p p ®paQM<<<p

— 737)73a.a.P.H

§ 8

®©

— I o

^ a u

ggg

73 73 73

p4 B. P.

pH B. p4

73 I tfl + + +

II II II hJ m3 — — — m u a m3 m3 • P p P ^ a u

073 73 73 ggg u II II n 73 73 73 WWW

-m3 m3 m32 £CM <MP(2 SBP OPO£Qh^<<S ®PbPB.BHpH->

073 73 73 B.aHfl,H

SS o o © u

®

m3 O

73K

O

73

73

W«O

OhH

5

Cm -6

^ p V P

®

® . — — — • Cii • 0

.0 0

y ® q

^ 1^ «»* fc, u* u < < rm ®

b, 73 73 I ®

+ + + < ea o

ggg

73 73 73

Bh B« Oh

Bh Oh Bh

» m3 CQ

E9 n

p

7) 57i 1

BhOh Oh U

gggg2 73 73 7372 ^ 5

Oh Oh Oh Oh Bh Oh Ch Bh

- K

M. ® H ^ ^ ^ ^ ^ — ^ia®NOO®Mj B

w w w w w w E ^

****es!«sea ^

< <c "I; < MH

Oh Ou Bh Oh Oh Bh Bh

Bh Bh Bh Bh Oh Oh

II ®

II II II II II II . . II ^^racauw^H

gggggggs tt 73 73 73 73 73 73 —

m3

!X3

— CJO 'i*

®

o

®M

U

B

aiI

b3

U UUU

(BM.oo-H-.-H — oooacococc-'- — COCO — - cocooocoeoco — — — COCO — — coocooocococococooooooooeoooococoocooo

hH ^ hH ^ ^ ^ MH hH »H MH mH f1 ^ Ml MH mH hH hH HH M. hH ^ ^ ^1 HM hM ^ HH hH M. hH Ml mH MH HH hM hH Ml MH MH MH HH mi « MH HH mH HH

%a

O — C3 O ”t «5 %e N 03 O' © — C3 « -4“ O O Jm CO C> ® — C) CP T}* Ift '© N ® O' ® — C'» ej '/ W o !' fS O' O — M C^ -4* O '5 t- © ® — Cl

Cl CO M (M O C4 CJ Cl ?>! M O CO O O M O Ci CO O CO ^ •'J' H}"^ If W O Lti K9 Ift LO lO W l« W 'HI '<5 O ® ® © >© vO 'C IM t- N
tr

9r

c3

i4 <:; m t>T

tti' #

s

A *^' r,Sc . - , .

’

•-ft' *V

•••ai vs ^53

§ ^

&'4 -

*1w.

sa

fc> as

iR 'iv*»

C9 -A '

'£

:y- ,^*!^

‘.'...r**

•• •'^•"*'*^(5^

Vf^ 'S“ i

• ;-.f*

•*. . ; i')/. >.' *\ V’v'A

' ’

‘ '

. • . '. ^ /

• ’ Jjf

V

j

V

•

' -

' / ,."i.'f '

.. i.r ,,

' '

' t ,.i

'V >:«UJ

t ^ •^. r*

V*- ^ .• '<• <?•; *?:•

‘t' >• J'•*"- ’ •*

.:} VJ ^ *$

^S 4J .S v4 pO X

J'^'

^

• '-i<. , .>!. '

P'4 'i'f /4 3.1 CP

t» o

+ +• •

>

)>' V. y

'

^ «

T> .<

*tJ 41“

»i. 's', *-

V fH !2qr4»

vV Cf !W

&. .30 '4

Ui

<SJ ‘.*’5 ^ •

C’ t **

j. r n »f M

it- • '<i5 •*'i • r* .1 M >‘l- *f 4 -fi

*“> ,S - W • <

_. -1 .•sU' W 'i* i»4 Sfe p p S ft Of

«.< -. ' “•

j (»^

« ^ » H " t>

ft ,« 'jy ift w ^ 4i^ tXl

^ S5 r2 ci p .

;-s S' *» p-'S .-<; -t: •19 pT -0 -. 9

O

99»*> 0 ;.' O O

>

r

v\

tvt>s

*1^ tt* wh 4-^

H>

C'

I

w*

?“ 9 o

J5» «

t,

*

>-« in »-* "Ui ;, "s •4>; ,<s

’' ‘-^i >-**

ui

••1

V-3 *4

O ,;9CW

/: ' jf

i*

jti •. >- flj.OS W ij

if '• l» I -

: , V. ;

, - v v c.^ 3 « g> 2* ^ «V?- fl-; fIII' k kslDiS'll-S «* gS.S

ryif/9^'0- «s< •». li' *"> **»i ^ ' ‘ *« ;

'^h: ..1
Ou,

O'N

N

a

I

>

i

i

I

i

\

I

I

\

I

(

i

4

£

)

\

\

r \

y

y ei y

y W y

* y > \ y

y y ^ y

y y O • y \ y y (iCi — y

* y y cs o y y sc h if y y o W y o y y cn y

y y 00 CQ y

y if -< y

y y o y

y y Ed \ y

y y Sc y

't y y 05 \ y

y . —

y

S5 H y y

y " • y -1 w b < y

• y y N - o J y

u

— W C5 <f

u o

iz.

. Pia.H•— o

pSEe>o

w

1 0 if Cd U Cm O ®

— N C9 ^ 10

td

U

if

if

if

if

U

P

iffif*

*

c'cococoo'cocoaococccosciooo'cacocococococoooco

u

u

OQO

o

N

if

• ifif

if

«-<T*IO £>N0C5''5>-'iMe5-^IO'Ot^C0'3'O-"CMO'J‘n

N^•N^-r'.NNCi^oocoeoc5c^cocoac^'^0'«^0'0'c^

o

I

Edo

(d

if

ifif

y-y

y

u

©

o

«<B.

O'N

N

O

Q

X

c«. o

HU

P

o

§

u

??

o g

H fo P O

(m U

«o u

in K

00o« uuu o

o

<J

t-H w M

tx P

• w B is XX +

J! , a. u

II M

« u 00 « . M II C3 6> B Ss O' o O &< C (S>

II 1-1 M H O

B H O • B5 59 euo O MB o

“-K - a U S M

o •• 4fK*

a

O' « M

h- M ft \ BO P

it ^ 00000000^00000 B CO a \ CdOOOOOOOOOOOOO M

, ii t- • • B a 2 it K

•U O it

• it

- - d S it o< ?!* M it

» ^ pH N it

*

j 1 09 it

ii P- >t - cr; — Cl W Tl* K5 'S> N O o> O - 01 « Ph

it px 50 M m.

! ^ p. O

it O ft

yr •• J B ft ® M M ®

XU

0.

O'N

N

O

E

-1 5

Q

i}

fia

a

CQD

K

HK

O'

’S' C3

H H jssi

WUUtiiiii

w Cfi DO w ^

, 2 o

jsodS&S’'- j 3 »o . .

BQ M P II II <1 U V iS • » *4 -i" « 2 q^ 5!3 + piC "““SSsS-^^g

-* a 5 CQ o — *- H P

® as S M « o O «

c^O UH

" Q O

U

9’«•

O

u

u

9 <9 99

UOU'jyy'JUUOD^U ouwooo V«y

O'N

S=«

U 9 K

• O

^ o)

fci I?N

I a

71 p;-

r" CO « t-* e u

9 O CJ C-) M iM N CO © 9 0999999990 9990999999M9999999COM9999099999 O 9 O d O O O O ^ O O 9 O O Q 9 ^ O O O ^ w o o o o o o

Wf'?’f*iov0N90'®’-'lC0'3'li0©N«©9-*NC0'*'lfJ©N«O'® — flCO-ftOOt-vOt:'©

@HDG,P

**‘~r.*'**

WEUSCL
v-Ff-.p-

;i
9, CL

N

©

©

V

w

p

§

N P

G Ou

O'

”4* O

O

;poQoo

I X

igr

« o

fafeE- • M QJ l»-l ;kbpe-

>!<«^S

>• &S o

Fffluo

« 2 i|

g|^i| MC)»;OP

I

. 8 '^fe

>< -< C 35 o

CO f- •- r. u wo^

^ cdoe; ^ ^ M ^

CL K 35 E- S'. 1—

1

o w ^ « E-PWJO © <! O CL M p«h<3 »: S O U -3 O

P

I w

ififO

P

I* w

a*Q

n

CO CO I

M CL P

, NO I

g

« S §

SpoE-fa

s

o

n

1^

! O j

CJto

>:•g M O

^.§

MU.

E-is

o s

t; •-«

el

o

>*0.

=i

s§

a?

S o

o5KQ

gou a. p«

©2M M

COB

IIS 3 ou

il

HM

, u, u. O H- 1-1 Ui

CJUOOOUOCJCJCJCJUUCJUUUUO C3 UUUOCJ oouuoo u

©

u

COpw

iE5

J'N

\ J -H 0 - N Vj \ ® O

P N

U3 ©

3S

• O

«5

fci ^

CL t1 CO

©^® 000 © 0 ®©© 00 ©©© 0000000 © 00000000000000000000 © 000000©©0

< c:J ?i C5 ^ w >.0 N cc S' ® N « 'f to © N C <r © — 01 w •«#• w 'O t^« fO O' o — « »?• 1.0 ^n t- eo ^ o — ^i i>“ vp r- O “S' o ^ lo o

E-a — *-->0103 0101010101 01 ^lCJoe5 c^»eJW««w»'^»f^'^•^^’^••»i•^'^•^wwpppp ^3

NiJ W h*

100

CONTINUE

200

CONTINUE

. cuo

-< III!I

O'N

t-<O 1

?;

•'(

•» iI

vO

lO

g;Ouwou

CA

C>O • CJd

.. tt a vt s 5t

trSt

ni -Jo

^;- o CO

ii tx S3

«•

K

c*

Q tt

w t:-

•>c ji

ft »*

vi* C-. ft u * C5

it o a * fe: W U (jy

Cn

O'N

N

«>

O

o

>

2;

Oh

a.

o

'JO o

u

s

OJK

C<i.i5 « Q

® §

- C/J

O'

Tf«

o

O'N

\

iJ) ^ ^

£) \ CO &NW -3 Z.

• u

I 'I hH QJ

Cti 'J' Oh N

I CO

U

CQ

II n

>* 00M

Oh

Oh

hJ m oSCO Sc

B_]

-CQ

Cft?1 ^ u

pl

B 00 w—"fa <! ^ Oh

>1

I

04

Oh

S

U

00B

CQW

S

CQ

0^U

O

B

I

I

\

VON

BeQ

OhOh

go

- -1« <4 L** '3 fH '0 Cv w w w w w J5C

o

B

Oh

Sfrt|3« ^CL*^Cl«&«CU0u

<CU fi4 AmPuC^CUOuC^w 0kww WWWWWW

OCOCOJXxS

— 6b b« Oh Oh U< 6b (C4 Cb —

li HM— S S5

b U II U U II SbBbSkk ^^CQCQUUB

ggggggg CO «j CO CO 00 CO CQ

X

CO e6 bH o CQ P B

O

S

U

Ed M CQ aHH

CQa

5

e

o

>*

OhO

u

II X

-ggBB O M bH -OhHB

o o

a u

s

S2

00

B

b]6QO

bn

H

u

i

9U

O

o

w

g ?

§

8

u

B B

B

UCJUC^UUUUUUU U'JVUU uuu uou u U U U u rj U Cb

CQCCCOCOCOOOOC'O'OOCO — OO — OOOOCOOOCOOOi>CIM(M9>flOOO — — — 00 — — — — — — — Ov00e0C0CQ00C300O'CV‘9'Ova0i3vw'9'Ov

Cl W ei W N W CO Cl M W N CO W C9 a M W Cl M N cv| eo « 09 CJ N N « CO » ?1 09 09 « M CO CO W M ei W W « C! W M M W W Cl Cl W |?1 Cl Cl

iJ —

c-H c3

hQ

U1 h*

•• J

>3 W

C'l«4j'W'©r*coo'c3 — cjeO'vfiO'Oi'-aco'® — cioO'tiooNcoc'© — •Nc?<i'»cvOl'-coc''S — ?icO'4i*»ot*oOc'Cf — cicc'f'i.oo „,HbHbHHHHHHH-4,b-.|jlC\jp|C'3ClClClClClCJC0C0C9C0C0C0C0C0e9C04j<'^^4j*^'0''i"«'4j«'d*'„^lf5cf>»u5L'6I.O

fel

rQ

\

\

vj O b

^ CJ C5 •<#' »-< 04 ’-' X ® O ® 9 X 0 9 9 9 1 X N >-< 01 1s X

•Xi O ; X

u uu uu uu uu V h X

V « K bl O

CO 00 O O' O' CO is V

K ^^^,-i«,Ov^^C0C'C300iM«>3'O'Cl«'00C0C0 3

H COCOOMCOMCJCMNWCMNCOCJiMMWC^C'JWei 01 01 01 01 CM 01

• • cu

.JO (i X

w X » X

bj X

£? X

• X

>'• CO C' 9 -- *1 ^ O V© N 00 O' 9 ’-' 01 ?*' '^ IrS '0 t* h

y CO ‘S' 9 «-< 01 fXi 0.

if IOiOI»'0'0'OvOOvO'OO.Ov£iNNt'>Nr'*Nt<NNNCSCOCOCO PO

X- o

X 1a p

X

1% B

9

<

a.

N

<S> S

a

u

•"J 0

01

O

&

u

u>-» §

0^

E- w K

O P

— m

O'

'!»• n

o

O'\ w «

tj ~i

“i \ © ONP5 ©

PL.

• U

I •—

< O

fc( '<?’ XN

I OS

i

o

S g

fc S «

X i

i

edu

O

ce: bJo

s Be

• » NH X w4 G p • U n II 9 _ II

II ©

P

2S o © 9 Pu S ©

H p

Cl O o p o l«-4 P o a

9

O U O O <J O

WO^WWOOrCWWNrtTfWW'^CTW'^WO'^MWWW 0009000909990009900999999©

H CO

.JWE-

•• J

9 W

;« 'I* W N 03 O' © »^ Cl P %• 1.0 © N CCl © O -* i'1 P ''»• M

^ >-H i-< «<H ^ fI C-j Cl Cl t'i Cl CJ CJ

tCJ

I

o

u

Tjw

a

p

g

I

u

E-<

M

M.

4f

11 H

H

a

u

o

X

U «)

» Ul

o,

O'N

h-

<S>

H

U

qcc: 0.

(UX

X

r"U-5

o:

cu

u

as

coq - «

n

<M O

— w

O'

•O’ a

o

C'?-

, \

e-* (j — ^

\ O

Q N

s

tu

• u

'-• o

lA: c- ^-

I CO

-J -1

i

I

o

C4 0^

4fH ?

Z%pM ® OOu,«

85 H

Izi O

o

o

o

o

«

O'Cl

b*0

V

1

CON

19

o u o u y o

OOOOOOOOdOCQOOOOOOOOOOOOOO^O

• tf-'C'lCO'4'0'5NOOO'®»*<iMOv‘i9'DNCOO'®-<C!e;Tl*l9-CNCeO' H 00 OJ N O') C4 01 CJ 04 01 1?! W

WH

«• aa s ita

a

Cd p

o o

85 u

>

S

q •> € 4t S *

r

itH

« EuJ 3uo

n

M

n

1)
ysO’^Cl

*

>
o

O't-N

S>u

rj

s:£

H

o

o

u

u

>

a

£

tv O

w 05m

?5 »

-'fl

O'

rt

<2)

o

U4u

9

E S

I .~. -N o o

o o N—4 »—

I

E C5 o o

E S

o o

X X

E E

ggN-t M

Q Cl

:x;>-

a E

a

u

X

s5o

H".3

i4U

O

nJCQ

pH

r-3

O

CJUCJUUU

E

a

M

X

E

i

X

o

<<

Cu, E

a

o

<

OuE

_)

n

X

ssCm

I

H

X

a a

I) \ Jt nu H

II

II II 0 ft. E II <

U II X ft. O' 0 II Cd E ® W <fi II HH II <

E <C II ft. ft. 0

- 0 II a a

a

O'M

a

a

u c; u o wu uuu

a

ob

O

<S> ©

o

o

o

H - 0\000®®©®0©©©0©®©0©0®©00©©0©©®®®©©00®©0©0© U IHho

• u

I a « o

fc. 0

> ft. t1 X

a J -H

. hH

vj H 50 .JW H

* •• J

@

M rt '5* rt VC » . X O' =9 -< O '!*• n vP t» CO O' ® CM C> W >0 N M O' © -< ?>1 « lo v© t« re O' © »4M^M^>HMo4^«-C4C'l6]<M©101CMM0]6i©©03©C0©©©C0c0'}*

END

ELT.

ERRORS:

NONE.

TIME:

0.101

SEC.

IMAGE

COUNT:

40
I'

1

L
NBS«n4A (REV. 2-ec) U.s. DEPT. OF COMM.

BIBLIOGRAPHIC DATA

SHEET (See i nstructions)

1. PUBLICATION OR

REPORT NO.

NBSIR 80-2056 (NBS)

2. Performing Organ. Report No 3. Publication Date

April 16, 1980

4. TITLE AND SUBTITLE

The Numerical Solution of a Nonseparable Elliptic Partial Differential Equation

by Preconditioned Conjugate Gradients

5. AUTHOR(S)

John Gregg Lewis and Ronald G. Rehm

6. PERFORMING ORGANIZATION (If joint or other than NBS. see in struction s) 7. Contract/Grant No. NATIONAL BUREAU OF STANDARDS

DEPARTMENT OF COMMERCE S. Type of Report & Period Covered

WASHINGTON, D.C. 20234

Final

9. SPONSORING ORGANIZATION NAME AND COMPLETE ADDRESS (Street. City, State. ZIP)

Center for Applied Mathematics

National Engineering Laboratory

National Bureau of Standards

10.

SUPPLEMENTARY NOTES

Document describes a computer program; SF-I8S, FlPS Software Summary, is attached.

11.

ABSTRACT (A 200-word or less factual summary of most significant in formation. If document includes a significant

bi bliography or literature survey, mention it here)

In this report the combination of an iterative technique, the conjugate gradient

algorithm, with a fast direct method, cyclic reduction, is used to solve the linear

algebraic equations resulting from discretization of a nonseparable elliptic partial

differential equation. An expository discussion of the conjugate gradient and preconditioned conjugate gradient algorithms and of their use in the solution of partial

differential equations is presented. New results extending the use of the preconditioned conjugate gradients technique to singular linear equations which arise from

discretized elliptic equations with Neumann boundary conditions are also given. The

algorithms are applied to solve a specific elliptic equation which arises in the study

of buoyant convection produced by a room fire. A code was developed to implement the

algorithms for this application. Numerical results obtained through testing and use of the code are discussed.

12.

KEY WORDS I'S/x :o twelve entries; alphabetical order; capitalize only proper names; and separate key words by semicolon s) conjugate gradient algorithm; elliptic partial differential equations; iterative

methods for linear algebraic equations; Neumann boundary conditions; space matrices.

13. AVAILABILITY 14. NO, OF

• PRINTED PAGES

Unlimited For Official Distribution. Do Not Release to NTIS 66

1 1 Order From Superintendent of Documents, U.S. Government Printing Office, Washington, D.C.

20402. 15. Price

TC Order From National Technical Information Service (NTIS), Springfield, VA. 22161

.—^ $8.00