(Parallel Algorithms and Scalability)(2)

r

3

i

eY r

3

i

eY+1

i

y+1+1i n

r

3

i

i

y+1i n

e r Y2

i

+1

y+1?1i n i

eY1+1 ri

:::

x?1i

x

i

x+1

:::

-

x

Figure 1: Graphical presentation of the internal approximations for the solution y, and the 3-stage Runge-Kutta discretization.n

System (8) can be written in tensor notation as

Parallel de nition

Y= e y?1+ h(A M )Y;n

(11)

Parallel Numerics 95/Sorrento, Italy/September 27-29, 1995

methods

Parallelisation of Runge-Kutta methods T

PACT

where Y= Y1; Y2;:::Y], the s-dimensional vector e has unit entries and is the tensor product (in general A B= a B]). If the eigenvalues of A are all real and distinct and T is the matrix of the eigenvectors of A, then the D= T?1 AT is a diagonal matrix with the eigenvalues on the diagonal. By introducing transforming vectors~ Y= T?1 Y; (12) equation (11) is transformed to~~ Y= T?1 e y?1+ h(D M )Y; which is a set of s subsystems with d equations and d unknowns in each subsystem. These subsystems are of the form~ X~ Y= (T?1 ) y?1+ h M Y; i= 1; 2;:::; s (13)ij i i n s i

or

j

=1i

ij

n

i

i

~

X (I? h M )Y= (T?1 ) y?1; i= 1; 2;:::s:s d i j

where the right part of system (14) equals to the sum of products of the i-th row from T?1 and the previous solution vector y?1 .n

=1

ij

n

(14)

The third-order 3-stage Runge-Kutta method, introduced in 5] was used in our implementation to solve the heat transfer equation. This method is de ned by the following Bucher tableau: 0:17731047291815 0:20318569149365?0:02891149910657 0:00303628053107 1:00000000000000 0:57206641687972 0:44394830854688?0:01601472542660 2:83374670845340 0:10181357682466 2:04204807121208 0:68988506041666?0:01601472542660 0:44394830854688 0:57206641687972 Eigenvalues of matrix A are 1; 2; 3]= 0:535870000; 0:46527906045718; 0:335870000]: The corresponding matrix of eigenvector of A is 2 3?0:99698590138860?0:99359718232641 0:98300104580292 7 T= 6 0:07597739963378 0:11046776579844?0:17342135765532 5 4?0:01570182082594?0:02369624427039 0:06028247389871 and it's inverse is given by 2 3?3:347643243690?48:055650853970?83:658467850145 7 T?1= 6 2:438127219799 58:641197577395 128:942194784559 5 4 0:086432480687 10:533989095837 45:483459690559Parallel Numerics 95/Sorrento, Italy/September 27-29, 1995

Implementation details

methods

Conclusion

PACT

3 Parallel algorithmThe parallel 3-stage Runge-Kutta algorithm can be now represented as:set-up loop loop end for each time step for i= 1; 2; 3 Runge-Kutta stages M= I? (h M ); (* left part of Equ. (14) *) P (* right part of Equ. (14) *) Right= 3=1 (T?1 ) y;~= M?1 Right; Y (* the solution of system *)i d i j i;j old i i

y= y0;old

(*set d initial values*)

end

P Di erence= 3=1 b MY; y= y+ Di erence; y=y;i i i new old old new i d

~ Y= TY;

(* Equ. (12) *) (* di erence from the previous time step *) (* new value in time *) (* save the calculated value *)i i

It is obvious that the calculation of M= I? (h M ), and the multiplication b M can be performed outside of loops because all values are known, therefore, it can be put in the set-up segment. If the amount of work associated with the solution of system (11) for s= 3 is proportional to (3d)3, the amount of work for the solution of the above algorithm is proportional to 3d3 . The solution of d dimensional systems is the most complex operation, however, with the described parallelisation, each subsystem can be solved on a separate processor or on a separate set of processors.

4 ConclusionThe above principle o ers a straightforward possibility for the parallelisation of s-stage RungeKutta methods. We can simply take s processors and solve s systems in parallel. But there are two problems, rst, the dimension of the original system d may by too complex to be performed on a single processor, second, the number of stages can not be arbitrary increased. It follows, that the above parallelisation o ers a good choice for smaller problem domains on parallel processors with relative low number of processors. The parallel algorithm needs almost

no communication, therefore, also message passing systems implemented with PVM can be used. On this way, the described parallel s-stage Runge-Kutta method becomes competitive with other nite-di erences based numerical methods 6]. Further parallelisation of the solution of a d-dimensional system of linear equations, which is usually sparse, remains the problem to be solved in parallel.

Parallel Numerics 95/Sorrento, Italy/September 27-29, 1995

methods

REFERENCES

PACT

References1] R. Trobec, B. Slivnik, Parallel heat transfer computation on generally shaped bodies, Int. Workshop Parallel Numerics'94, Smolenice, Sept. 1994, 157{168. 2] D. Janezic, R. Trobec, Parallelization of an implicit Runge-Kutta method for molecular dynamics integration, J. Chem. Inf. Comput. Sci. 34(1994), 641{646). 3] K. Burrage, A special family of Runge-Kutta methods for solving sti di erential equations, BIT 18(1978), 22{41. 4] J. C. Butcher, On the implementation of implicit Runge-Kutta methods, BIT 16(1976), 237{240. 5] B. Orel, Parallel Runge-Kutta methods with real eigenvalues, Appl. Num. Math. 11(1993), 241{250. 6] B. Slivnik, R. Trobec, Comparison of FD methods for solving the di usion equation, Int. Workshop Parallel Numerics'95, Sorrento, Sept. 1995.

Parallel Numerics 95/Sorrento, Italy/September 27-29, 1995