Кулаков Володимир Володимирович
Факультет комп'ютерних наук та технологій
Кафедра прикладної математики та інформатики
Спеціальність “Інженерія програмного забезпечення”
Покращення ефективності розв'зання багатовимірних задач Коші на основі паралельних високоточних чисельних методів
Науковий керівник: д.т.н., проф. Фельдман Лев Петрович
Асистент: к.т.н., доцент Дмитрієва Ольга Анатоліївна
При математичному моделюванні фізичних процесів часто виникає необхідність знаходження високоточного розв'язання задачі Коші для рівнянь і їх систем. Найчастіше знайти аналітичне рішення не є можливим, тому застосовують чисельні методи розв'язання даної задачі.
Отримання рішення необхідного порядку точності чисельними методами, може потребувати виконання значної кількості ітерацій. Незважаючи на досягнення технічного прогресу в області розробки високопродуктивних обчислювальних систем, існує багато задач, в яких гостро відчувається проблема нестачі обчислювальних ресурсів. Наприклад космічні програми, медичні дослідження, системи моніторингу що працюють у реальному часі.
На даний момент (травень 2013г.) за даними рейтингу топ-500 [1], найпотужнішим суперкомп'ютером у світі вважається Titan - Cray XK7 [2], який містить 560640 ядер (включно із ядрами ГПУ). Його пікова продуктивність - 20 Петафлопс. Використовуватися увесь цей потенціал буде для вирішення складних обчислювальних задач таких як розрахунок наслідків зміни клімату на Землі.
Удосконалення методів знаходження чисельного розв'язання задачі Коші дасть можливість не лише зменшити час отримання результату але і зробить можливим рішення задач більшої розмірності, що потребують більшої точності.
Ефективне використання багатопроцесорних систем на сьогодні є однією з найбільш актуальних задач. Серед чисельних методів рішення задачі Коши є багато таких [3-6], які досить добре піддаються розгалуженню. Модернізація цих алгоритмів з метою підвищення їх ефективності надасть можливість підвищити точність обчислень і понизити обчислювальне навантаження, не вимагаючи підвищення потужності апаратної складової обчислювальної системи.
Почати огляд хотілося б з циклу лекцій [7] професора Артура Пола Маттука. Відеозапис лекцій був зроблений у 2003-му році в Массачусетському технологічному інституті. Курс присвячений розв'язанню диференційних рівнянь і є досить добрим (на мій погляд) прикладом ефективного викладення матеріалу.
У статті [8] описаний метод типу предиктор-корректор для розв'язання ОДУ 5 порядку. Проведені дослідження, пов'язані з визначенням збіжності методу, його стабільністю. Метод протестований на декількох тестових прикладах.
У статті [9] наведені короткі відомості що до екстраполяції Річардсона, загальні формули, приклад розв'язання задачі з використанням екстраполяції у пакеті MATLAB.
Стаття [10] присвячена проблемі управління кроком для вирішення жорстких задач з використанням схем на основі екстраполяції. Приведена інформація для визначення критеріїв виявлення помилки обмежень на розмір кроку, вибору початкового кроку. Також приведені результати експериментів з використанням отриманих напрацювань.
Як показано в [11], деякі функції, що погано інтерполюються при допомозі поліноміальних методів, можливо досить добре наблизити раціональною функцією з поліномом в чисельнику і знаменнику.
У книзі [12] описані різні схеми інтерполяції, у тому числі приведений детальний опис раціональної інтерполяції а також розглянуті інші схеми інтерполяції, такі як інтерполяція Эйткена-Невіла.
На території України співробітники Донецького національного технічного університету активно займаються проблемою підвищення ефективності чисельного розв'язання багатовимірних задач Коші.
У [13] професор Лев Петрович Фельдман і доцент Ірина Акопівна Назарова (ДонНТУ) розглянули паралельний алгоритм розв'язання систем ЗДР, орієнтований на системи з SIMD- архітектурою. Були отримані характеристики алгоритму такі як час виконання, прискорення та ефективність паралельної реалізації.
У [14] професор Лев Петрович Фельдман(ДонНТУ) спільно з професором Анатолієм Івановичем Петренко (КПІ) і доцентом Ольгою Анатоліївною Дмитрієвою (ДонНТУ) досконально освітили сучасні чисельні методи розв'язання систем рівнянь у тому числі і жорстких. Особлива увага приділена практичній реалізації методів.
У [15] доцентом Тетяною Василівною Михайловою були запропоновані модифіковані методи аналізу і синтезу високопродуктивних обчислювальних ресурсів різної топології за допомогою імовірнісних моделей, що дозволяють аналізувати і проектувати ширший клас високопродуктивних паралельних обчислювальних середовищ.
Екстраполяційні методи Річардсона створені для отримання високоточного рішення задачі Коші і інтеграції систем звичайних диференціальних рівнянь(СЗДР) із складними правими частинами. Практичне застосування екстраполяційних методів ускладнено у зв'язку з великою обчислювальною складністю їх послідовних реалізацій. Крім того, використання технології локальної екстраполяції на основі явних опорних схем обмежує використання методів областю нежорстких задач. Тому побудова ефективних паралельних блокових неявних методів локальної екстраполяції Річардсона - один з найбільш реальних шляхів скорочення часу інтеграції багатовимірних жорстких початкових задач.
Розв'язання задачі Коші для систем звичайних диференціальних рівнянь першого порядку розглядається при переході з точки Xn у точку Xn 1 = Xn H, де H - базова довжина кроку. Обирається ряд натуральних чисел Pi ={n1, n2...,nk...}, n1 < n2 < ... < nk < ... і, відповідно послідовність кроків інтеграції.
Задається опорний чисельний метод порядку r0 і обчислюються наближені
рішення початкової задачі Коші в точці Xn 1.
Виконавши обчислення для ряду послідовних значень i
по рекурентному співвідношенню, визначають значення для
довільних i, j за схемою локальної поліноміальної екстраполяції
Эйткена-Невіла.
Для генерації допоміжних сіток обирається гармонійний ряд як найменш витратний у разі опорного методу довільного типу. Блоковий опорний метод повинен мати малий порядок точності оскільки із зростанням r0 обчислювальні витрати на технологію в цілому істотно зростають. Для неявних методів, до яких належать і дані блокові методи, це особливо важливо оскільки збільшення порядку, а, отже, і числа точок блоку спричиняє за собою збільшення порядку багатократно вирішуваних СНАР.
Значення першого стовпця екстраполяційної таблиці:
Кожна з апроксимацій рішення виходить за рахунок Ni раз застосованої схеми однокрокового блокового k0- точкового методу з різними кроками інтеграції :
lt 
- час, необхідний для розв'язання задачі Коші для ОДР опорным
методом порядку r0 з кроком hi.
Після цього за формулою Эйткена-Невіла
обчислюються наближення T22, T33 і Tkk. Організація паралельних обчислень
може робитися двома способами. Перший варіант має на увазі
використання тільки системного паралелізму, другий - комбінацію
паралелізму екстраполяції і системного.
Перспективним напрямом подальших досліджень є застосування технології локальної екстраполяції для розробки паралельних методів розв'язання жорстких задач. Для досягнення цієї мети необхідно розробити алгоритми з використанням опорных методів, що мають достатні характеристики стійкості : серед однокрокових методів до таких методів належать багатоточкові блокові і повністю неявні методи типу Рунге-Кути.
Також планується створення програмної реалізації отриманих методів з використанням SIMD і MIMD архітектури обчислювальної систем.
На момент написання даного реферату магістерська робота ще не завершена. Остаточне завершення: грудень 2013 року. Повний текст роботи та матеріали з теми можуть бути отримані у автора або його керівника після вказаної дати.