Vladimir Kulakov

Faculty of computer science and technology (CST)

Department of applied mathematics and informatics (AM&I)

Speciality “Software engineering”

Multidimensional Cauchy problems solving efficiency increasing using parallel high-precision numerical methods

Scientific adviser: Doctor of technics, professor Lev Feldman

Consultant: Ph.D., Olga Dmitrieva

Abstract on the theme of master's work

Content

Introduction

At mathematical modeling of physical processes there is a need for finding the high-precision solution of differential equations and their systems. Most often it isn't possible to find the analytical solution, therefore numerical methods of solving this task are applied.

To obtain solution of given accuracy order using numerical methods, it can be demanded to execute considerable number of iterations. Despite achievements of technical progress in the field of high-performance computing systems development, there is a set of tasks in which the problem of computing resources shortage is felt sharply. For example space programs, the medical researches, real time monitoring systems.

At present (May, 2013) according to top-500 rating [1], the most powerful supercomputer of the world is Titan - Cray XK7 [2], which contains 560640 kernels (including GPU kernels). Its peak productivity is 20 PetaFLOPS. It'll be used for the the most difficult computing problems solving, like calculation of Earth climate change consequences.

1. Researches goal and tasks

Researches goal is multidimensional Cauchy problems solving efficiency increasing using parallel high-precision numerical methods.

For purpose achievement in a master's thesis the following main researches problems are solving:
  1. Existing Richardson extrapolation based methods for the task solving studying.
  2. Efficiency analysis of various extrapolation schemes usage.
  3. Efficiency analysis of various basic methods usage.
  4. Researching of methods realization features using computing systems with various topologies.
  5. Existing algorithms and methods improvement for solving efficiency increasing.
  6. Program realization for the system allows to estimate efficiency of received algorithms experimentally.
  7. Test examples development to research methods efficiency.
  8. Experiment results analysis.

2. Researches and developments overview

Theme of Cauchy problem solving optimization is well considered by scientists of America, Canada, Germany and other developed countries.

Ukrainian scientists also working with this problem. Donetsk National Technical University employees developing new methods for high-precision numerical differential equations solving. Also they working around existing methods improvement.

Their publications [13-15] are in top-list of search engines results for Russian-speaking queries.

3. Richardson extrapolation

Richardson extrapolation methods are intended for obtaining the high-precision solution of Cauchy problem and integration of the systems of the ordinary differential equations (SODE) with difficult right parts. Practical usage of extrapolation methods is complicated because of large computing complexity of their consecutive realization. Besides, usage of local extrapolation methods based on explicit basic schemes limited to area of nonrigid tasks. Therefore creation of effective parallel block implicit methods of Richardson extrapolation is one of the most real ways to reduce time of integration of multidimensional rigid initial tasks. Richardson extrapolation

Figure 1 - Richardson extrapolation


Effective from the computing expenses minimization point of view the consecutive method with Richardson extrapolation usage is described in [16-17]. Potentially there are three sources of internal concurrence:
  • system concurrence (it is limited to dimension SODA);
  • extrapolation concurrence (it is limited to the extrapolation table size);
  • basic method concurrence (small degree of concurrence).
Extrapolation table first column values are:

Each of solution approximations turns out at the expense of Ni times using of single-step block k0-point method with different steps of integration:

Conclusion

Increasing of efficiency of the numerical high-precision solving of Cauchy problem for equations systems is an actual scientific task. The analysis of the main existing practices in the field is at present made. Both materials of the international sources, and the results received by the Ukrainian scientists were considered.

The perspective direction of further researches is using of local extrapolation for parallel methods for solving rigid problems development.

This master's work isn't completed yet. Final end: December, 2013. The full text of work and materials on a subject can be received at the author or his head after the specified date.

References

  1. TOP500 Supercomputer Sites [Электронный ресурс]. Режим доступа: http://www.top500.org
  2. The World's #1 Open Science Supercomputer [Электронный ресурс]. Режим доступа: http://www.olcf.ornl.gov/titan/
  3. Фельдман Л.П. Параллельные коллокационные методы решения задачи Коши для обыкновенных дифференциальных уравнений [Электронный ресурс]. Режим доступа: http://masters.donntu.ru/2008/fvti/zavalkin/library/feldman1/default.htm
  4. Автореферат Иванов АВ Экстраполяционные одношаговые параллельные методы решения систем обычных дифференциальных уравнений [Электронный ресурс]. Режим доступа: http://masters.donntu.ru/2010/fknt/ivanov/diss/index.htm
  5. Л. П. Фельдман, И. А. Назарова, "Параллельные алгоритмы численного решения задачи Коши для систем обыкновенных дифференциальных уравнений", Матем. моделирование, 18:9 (2006), 17–31
  6. Designing Parallel Algorithms for Solving Higher Order Ordinary Differential Equations Directly on a Shared Memor y P arallel Computer Architecture [Электронный ресурс]. Режим доступа: http://it.science.cmu.ac.th/ejournal/dl.php?journal_id=328
  7. Video Lectures MIT OpenCourseWare, Arthur Mattuck [Электронный ресурс]. Режим доступа: http://ocw.mit.edu/courses/mathematics/18-03-differential-equations-spring-2010/video-lectures/
  8. A Block Predictor-Corrector Method For The Direct Solution of General Fifth Order Ordinary Differential Equations, Olabode B.T., Canadian Journal on Computing in Mathematics, Natural Sciences, Engineering and Medicine Vol. 4 No. 1, February 2013
  9. Richardson extrapolation, From Wikipedia, the free encyclopedia [Электронный ресурс]. Режим доступа: http://en.wikipedia.org/wiki/Richardson_extrapolation
  10. Control of step size and order in extrapolation codes, L.F. Shampine, Journal of Computational and Applied Mathematics, Volume 18, Issue 1, April 1987, стр. 3–16
  11. Рациональная интерполяция, Материал из Википедии — свободной энциклопедии [Электронный ресурс]. Режим доступа: http://ru.wikipedia.org/wiki/Рациональная_интерполяция
  12. Introduction to Numerical Analysis, J. Stoer, R. Bulirsch - 2nd edition
  13. Фельдман Л.П., Назарова И.А. Применение технологии локальной экстраполяции для высокоточного решения задачи Коши на SIMD-структурах // Научные труды Донецкого национального технического университета. Выпуск 70. Серия: «Информатика, кибернетика и вычислительная техника» (ИКВТ-2003) – Донецк: ДонНТУ, 2003.
  14. Чисельні методи в інформатиці : підручник для вузів / Лев Петрович Фельдман, Анатолій Іванович Петренко, Ольга Анатоліївна Дмитрієва ; За заг. ред. М.З. Згуровський . – Київ : BHV, 2006 . – 479 с.
  15. Михайлова Т.В. Оценка эффективности высокопроизводительных вычислительных систем с использованием аналитических методов// Материалы 2-й международной научно-технической конференции "Моделирование и компьютерная графика", г. Донецк, 10-12 октября 2007 г.
  16. Хайрер Э., Нёрсетт С., Ваннер Г. Решение обыкновенных дифференциальных уравнений. Нежесткие задачи: Пер. с англ. – М.: Мир, 1990. – 512с.
  17. Хайрер Э., Ваннер Г. Решение обыкновенных дифференциальных уравнений. Жесткие и дифференциально-алгебраические задачи. – М.: Мир,1999. – 685с.