Abstract master's qualification work

Introduction

Systems of ordinary differential equations (SODE) of large dimension is an essential tool for describing the set of phenomena and processes of different nature. High computational complexity of the numerical solution of multidimensional initial value problems requires the construction of efficient parallel algorithms for the integration of such systems a modern efficient algorithm for the numerical solution of the Cauchy problem for SODE should contain management tool integration step based on information on local aposteriori error. One of the known methods of assessing walking distance error is the technology of local extrapolation, possessing a high degree of internal parallelism, and consequently, the benefits in the implementation on parallel computers. The aim of this work is the development and analysis of the effectiveness of parallel one-step extrapolation methods, as well as software implementation of the developed applications.

Relevancy

Differential equations and systems of differential equations are an important tool for describing the set of phenomena and processes taking place in the world (physical, biological, chemical, etc.) The results often represent a system of differential equations of large size, which makes them very time-consuming decision on uniprocessor systems. Multiprocessor system much ease this process, which makes the solution of the Cauchy problem and further development in this area relevant to the present day.

Scientific novelty

The parallel algorithms for the numerical solution of the nonlinear Cauchy problem for a SODE on the basis of explicit and implicit one-step schemes with built-in ways to assess the local aposteriori error: the local Richardson extrapolation.

The purpose and the objectives of research

Objective

The parallel algorithms for the numerical solution of the nonlinear Cauchy problem for a SODE based on explicit and implicit one-step schemes with built-in ways to assess the local aposteriori error are offered : duplicate step, nested methods, the local Richardson extrapolation.

Tasks

To explore multistage parallel block methods for solving the Cauchy problem, the solution of the Cauchy problem by mentioned methods on computer clusters using Microsoft Visual Studio 2005 and Technology of Message Passing Interface (MPI).

Solution of the problem and the results of research

The method of the local Richardson extrapolation (Lre) is a generalization of technology doubling step of Runge rule [1-2]. The idea of the method is multiple fragmentation of the integration step, and also in the multiple applying the computing process - the local extrapolation (Fig. 1).

Pic.1. Technology of local extrapolation (Animation: volume - 49,7 KB, the number of frames - 9, the number of cycles of repetition - 5, size - 692x459)

The solution of the Cauchy problem for systems of ordinary differential equations of first order

considered during the transition from point to point , where H - the base length of step. A number of positive integers should be selected in such way that: and, accordingly, the sequence of integration steps: , where . The base numerical method of order is set and the approximate solution of the original problem is being calculated: . After performing the calculations for a number of serial values of i, using the recurrent proportion (2), – extrapolated values for arbitrary i, j are determined (Fig. 2). The process of calculation by (2) is called a polynomial extrapolation of Aitken-Neville [1-3]:

Here, the quantity b is equal to one in the general case, at the same time, it is equal to two for the symmetric methods.

Calculations by the scheme of polynomial extrapolation, when k = 4

Extrapolation table includes:

1. base numerical method for solving the Cauchy problem
2. sequence of grids
3. recursive rule for calculating the values of the approximate solutions

Effectiveness of the LRE is directly dependent on proper selection and combination of all three components. Method of Runge-Kutta of 4-th order was chosen as a base method. The method is symmetric. This means that it has an asymptotic decomposition in powers, and each extrapolation eliminates two degrees. Then, the number of rows in extrapolation table is determined from the following relationship:

Pic.3. Extrapolation table

Consequently, if the k lines of are extrapolation table are calculated, then we have as the approximation of the highest order for symmetric sequence methods, equal to 2k, and the accuracy of the approximation will be - (2k - 2). To get the integration steps we use the following numerical sequence: , allowing to use the property of symmetry [3].

The advantage of this method is that it gives a complete table of results of calculations, which form a sequence of nested methods, and allows us to estimate the local error, to choose the strategy for the methods of variable order and to control the integration step. Table (1) contains – an approximate solution of the Cauchy problem, obtained by numerical method of order with a step

Extrapolation methods have the advantage that you have an opportunity to change not only length of the step at each step, but also the order of the method. Consequently, the extrapolation can be considered as a method of variable order (table columns) and a variable step of integration (table row).

Potentially, the calculation of technology of local extrapolation contains three internal sources of parallelism:

• system parallelism (limited dimension of SODE).
• parallelism of extrapolation (limited dimension of extrapolation table).
• parallelism of the base method (low degree of parallelism).

As a basis for computing is an explicit numerical scheme, we have the real opportunity to use the system and extrapolation parallelism.

To get the variety of integration steps we need to analyze the numerical sequences, formed by a harmonic row, powers of two, rows of even numbers [X]:

Effectiveness of using the sequences of natural numbers for calculating the integration steps in the method of local extrapolation can be estimated from the graphs in Figure 3, which shows the dependency of overhead costs for the formation of integration grids to the length of the extrapolation table. In using the same base method the most costly sequence is , which actually repeats the process of doubling step, and are the most effective sequences are and . The choice of the reference method of integration based on a study of the influence of the order of the method and its properties on the amount of computation required. Let the reference method has the order – , the length of the extrapolation table is equal to k, and the number of stages of the explicit method - s, we define the size extrapolation table for the solution method of order r.

Pic.4 The overhead when using the number sequences on the number of lines extrapolation table for an arbitrary reference method

Summarizing the results, it can be concluded that to reduce overhead costs in the application of technology of local extrapolation method should be chosen a base method of small order, in particular, a second, but with sufficient stability properties. However, there is another point which requires analysis. Theoretically, there are no restrictions on the length of the extrapolation table, but the computer memory and accumulation of rounding errors, limit the length of the extrapolation table from the top and is usually used . Therefore, to obtain highly accurate solutions solutions there is no other way to get a decision by using the technology of Richardson which uses the base method of high order.

The general scheme of the algorithm of local extrapolation:

1. getting the size of the extrapolation table by using the extrapolation method of necessary order;
2. distributing data between processors according to the used type of parallelism;
3. computing an initial approximation by using the base method (first column of the extrapolation table);
4. calculating the values of extrapolation tables by using the formula of Aitken-Neville;
5. some the necessary data transfers between the processors are performed through the control processor according to the chosen topology.

Conclusion

Comparative analysis of the dynamic characteristics of parallel algorithms for local extrapolation based on explicit Runge-Kutta methods, has showed that the area of applications of LRE is a highly accurate solution, the complex right side and multidimensional problems, however, it requires careful consideration of all components of a parallel system to make such decision to be an effective one. It is planned to make research using different topologies, different numerical sequences to generate grids integration and using of implicit base methods suitable for solving stiff problems. The results will be used by using the parallel libraries of numerical analysis for a cluster WCCS-2003 of Donetsk National Technical University.

References

1. Хайрер Э., Нерсетт С., Ваннер Г. Решение обыкновенных дифференциальных уравнений. Нежесткие задачи.– М.: Мир, 1990. – 512с.
2. Хайрер Э., Ваннер Г. Решение обыкновенных дифференциальных уравнений. Жесткие и дифференциально-алгебраические задачи: Пер. с англ. – М.: Мир, 1999. – 685с.
3. Холл Дж.,Уатт Дж. Современные численные методы решения обыкновенных дифференциальных уравнений. – М.: Мир, 1999. – 311с.
4. Вержбицкий В.М. Основы численных методов. – М.: Высшая школа, 2002. – 840с.
5. Арушанян О.Б., Залеткин С.Ф. Численное решение обыкновенных дифференциальных уравнений на Фортране.– М.: МГУ,1990.–336с.
6. Foster I. Designing and Building Parallel Programs. – Addison-Wesley, 1999. – 302 с.
7. Немнюгин С.А., Стесик О.Л. Параллельное программирование для многопроцессорных ВС. – СПб.: БХВ-Петербург, 2002. – 400 с.
8. Гергель В.П., Стронгин Р.Г. Основы параллельных вычислений для многопроцессорных вычислительных машин. – Нижний Новгород: Изд-во ННГУ им. Н.И.Лобачевского, 2000. – 176с.
9. Арушунян О.Б., Залеткин С.Ф., Калиткин Н.Н. Тесты для вычислительного практикума по обыкновенным дифференциальным уравнениям.// Вычислительные методы и программирование, 2002, т.3, c.11-19.
10. Thomas Rauber, Gudula Runger Lecture Notes in Computer Science 817 [Електронний ресурс]: http://citeseerx.ist.psu.edu/viewdoc/download&rep=rep1&type=pdf