Кулаков Владимир Владимирович
Факультет компьютерных наук и технологий
Кафедра прикладной математики и информатики
Специальность «Инженерия программного обеспечения»
Повышение эффективности решения многомерных задач Коши на основе параллельных высокоточных численных методов
Научный руководитель: д.т.н., проф. Фельдман Лев Петрович
Ассистент: к.т.н., доцент Дмитриева Ольга Анатольевна
При математическом моделировании физических процессов зачастую возникает необходимость нахождения высокоточного решения задачи Коши для уравнений и их систем. Чаще всего найти аналитическое решение не представляется возможным, поэтому применяют численные методы решения данной задачи.
Для получения решения требуемого порядка точности численными методами, может потребоваться выполнить значительное число итераций. Несмотря на достижения технического прогресса в области разработки высокопроизводительных вычислительных систем, существует множество задач, в которых остро ощущается проблема нехватки вычислительных ресурсов. Например космические программы, медицинские исследования, работающие в реальном времени системы мониторинга.
На данный момент (май 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-точечного метода с разными шагами интегрирования:
где 
– время, необходимое для решения задачи Коши для ОДУ опорным
методом порядка r0 с шагом hi. Затем по формуле Эйткена-Невилла
вычисляются приближения T22, T33 и Tkk. Организация параллельных вычислений
может производиться двумя способами. Первый вариант подразумевает
использование только системного параллелизма, второй – комбинацию
параллелизма экстраполяции и системного.
Перспективным направлением дальнейших исследований является применение технологии локальной экстраполяции для разработки параллельных методов решения жестких задач. Для достижения этой цели необходимо разработать алгоритмы с использованием опорных методов, имеющих достаточные характеристики устойчивости: среди одношаговых методов к таким методам относятся многоточечные блочные и полностью неявные методы типа Рунге-Кутты.
Также планируется создание программной реализации полученных методов с использованием SIMD и MIMD архитектур вычислительных систем.
На момент написания данного реферата магистерская работа еще не завершена. Окончательное завершение: декабрь 2013 года. Полный текст работы и материалы по теме могут быть получены у автора или его руководителя после указанной даты.