Конференции ИВТ СО РАН

Тезисы докладов

Для нахождения гарантированных включений точных решений дифференциальных уравнений используются методы, основанные на символьных формах представления решений. При этом на разных этапах реализации данные поочередно обрабатываются и хранятся как числовые данные и символьные данные.

В докладе рассмотрены структуры данных, состоящие из формальной линейной комбинации корневых помеченных деревьев. Операции над корневыми помеченными поддеревьями производятся вложением структур данных в ассоциативный набор данных. При этом определяется гомоморфизм алгебры операторов в алгебру деревьев. Это позволяет реализовывать параллельное нахождение символьных формул и повысить скорость выполнения гарантированных методов. Приводятся примеры исполнения.

Постановки многих задач решения дифференциальных уравнений содержат данные (например, коэффициенты системы, или начальные данные, или краевые условия), значения которых неизвестны. При этом заданы лишь границы, в пределах которых могут изменяться эти данные, учитывать необходимо каждое из значений данных. Необходимо оценить все значения точных решений (трубку траекторий) поставленной задачи.

Для решения этой задачи предлагается класс методов, обеспечивающих гарантированные включения всех значений точных решений. В основе построения этого класса гарантированных символьных методов лежит символьная формула аппроксимации оператора сдвига вдоль траектории.

Напомним некоторые понятия, на которых основано описание символьных этапов гарантированного оценивания множеств решений дифференциальных уравнений.

Определим символьную формулу (аналитическое выражение) как последовательность имен переменных и знаков операций, которые нужно проделать в определенном порядке над значениями этих переменных, чтобы получить значение выражения. В силу этого символьный метод (аналитический метод) -- запись численного метода как метода преобразования символьной информации (символьных формул) на языке математического анализа.В дальнейшем при записи символьных формул, аппроксимирующих оператор сдвига вдоль траектории, допускается включение в них числовых констант, с отложенным выполнением арифметических действий над ними.

В этом символьный метод отличается от численного алгоритма, основанного на исполнении конечной последовательности действий над конечным множеством чисел. Чтобы строить символьные формулы, аппроксимирующие оператор сдвига вдоль траектории ОДУ и позволяющие получать достаточно точные включения множеств решений (например, интервальные расширения), необходимо получить формулу, хорошо приближающую точное решение, и выполнить алгоритм преобразования этой формулы.

Поскольку при этом естественно исполнять операции символьных преобразований так, чтобы обеспечить эффективную загруженность памяти и уменьшить время исполнения, встает задача оптимизации символьных форм алгоритмов. Для этих целей в статье предлагается параллельное исполнение символьных преобразований. Пусть в задаче удалось выделить однотипные операции над данными, которые эффективно реализуются на компьютере с параллельной архитектурой. Тогда анализ структуры алгоритма и его оптимизацию достаточно провести на уровне этих базовых операций.

dy/dt = f(t,y)                  (1)

Алгоритмы решения систем ОДУ (1) основан на обработке поддеревьев с однотипными операциями. Ограничившись крупнозернистым параллелизмом и соответствующими ему многопроцессорными архитектурами, параллельная форма символьных формул приближенных решений, используя запись арифметического выражения в виде дерева и обработку поддеревьев с однотипными операциями.

Одна из реализаций гарантированных методов предполагала представление выражений в польской обратной записи. Техника распараллеливания польской записи использует при ее анализе такие специфическией свойства, как бесскобочность и схранение порядка операндов первоначальных выражений.

Программная реализация предложенного метода преобразования символьных формул основана на рекурсии. Это связано с рекурсивной природой данных. Применение рекурсии позволило создать достаточно эффективную программу построения гарантированных оценок и привело к уменьшению вычислительной сложности алгоритмов.

Для описываемой задачи был выбран стандарт в области систем, ориентированных на обмен сообщениями,--MPI ( Message Passing Interface ). Использовалось то свойство, что MPI способен учесть различные представлений данных на различных ЭВМ. Декларирующий механизм MPI позволяет описать структуры данных произвольной сложности.

Для проверки результатов выбрана система уравнений, описываюшая химическую реакцию с участием восьми реагентов. Эта система была предложена Шефером для объяснения роста и дифференциации растительной ткани при высоких уровнях светового облучения независимо от фотосинтеза. Готтвальд предложил использовать ее в качестве тестового примера. Численные результаты были получены для компьютера с процессором Intel Celeron(R), CPU 1,8 GHz, 256 Mb, а также в мультикомпьютерной среде. Расчеты проводились для 0 < t < 321, время счета составило 579,5 сек.

Примечание. Тезисы докладов публикуются в авторской редакции

Ваши комментарии Обратная связь

[Головная страница] [Конференции]

© 1996-2000, Институт вычислительных технологий СО РАН, Новосибирск
© 1996-2000, Сибирское отделение Российской академии наук, Новосибирск