Символический образ и его построение на компьютере Петренко Евгений, Аспирант, 2 года обучения, Математико-механического ф-та СПбГУ Научный руководитель: Ампилова Н.Б.

План Символический образ Алгоритм построения символического образа Представление ячеек Представление графа Построения образа ячейки –Точечный метод –Линейный метод –Адаптивный метод –Прямоугольный адаптивный метод Реализация Примеры –Хенон –Икеда –Множество Жюлиа –Отображение с задержкой –3-х мерная система хищник-жертва- суперхищник (1 и 2) –Логистическое отображение

Введение Во многих областях науки применяются динамический системы С ростом вычислительных мощностей интерес к ним возрос В 1980-х годах был предложен способ компьютерного вычисления ее оценки –Этот метод позволяет перейти к исследованию графа(!)

Что такое Символический образ Символический образ есть некая дискретизация динамической системы, представляющая собой ориентированный граф. Он строится по заданному покрытию фазового пространства ячейками {C i }. –Вершины графа соответствуют ячейкам, –вершины i и j соединяются дугой, если образ ячейки C i при действии динамической системы пересекается с ячейкой C j

Образ ячейки

Образ ячейки.

А зачем? Задача исследования динамической системы сводится к исследованию ориентированного графа –Алгоритм Тарьяна Мы предлагаем свести изучение динамической системы к изучению построенного по ней ориентированного графа – символического образа Впервые используется ориентированный граф для исследования динамической системы

Что можно исследовать Локализация цепно-рекуррентного множества Построение аттрактора и его области притяжения Оценка топологической энтропии Оценка показателей Ляпунова и спектра Морса Построение изолирующих окрестностей инвариантных множеств Построение инвариантной меры системы Предложите ваше!

Алгоритм построения Строить символический образ относительно «мелкого» разбиения может оказаться неэффективно. Строим символический образ по шагам с постепенным уточнением – разбиваем каждую ячейку на несколько –На каждом шаге построения мы проводим анализ построенного символического образа и исключаем вершины, через которые не проходит периодический путь.

Подразбиения

Анализ символического образа Локализация компонент сильной связности – локализация цепно- рекуррентного множества динамической системы –Алгоритм Тарьяна ( работает за линейное время) Поиск контуров – локализация неподвижных точек и периодических орбит Локализация изолирующих окрестностей

Представление ячейки Все ячейки одинаковые Идентификация ячейки? –Экономно по памяти –Удобный поиск Equals, GetHashCode

Представление ячейки –Координата верхней левой точки Целые числа –Вводим новую целочисленную систему координат »Размер ячейки равен 1 Плавающая точка –Проблемы округления –Много памяти

Представление ячейки (0,0) (1,0) (0,1)

Система координат Целочисленная система координат –long[n] –Размер ячейки равен 1 по каждой из координат Оказывается очень просто проектировать обратно –Операция целочисленного деления Оказывается не эффективно хранить массивы –Заменим на набор полей Придется сгенерировать код реализации после того, как будет определена размерность

Варианты написание кода class CoordinateAsArray { private readonly long[] myData; /* … */ } //NOTE: It is generated, not WTF class CoordinateAsFieldsFor2d { private readonly long myF1; private readonly long myF2; /* … */ }

Представление графа Нужно обеспечить: Быстрый поиск вершин Быстрый поиск ребер Оптимальное использование памяти

Представление графа. Структура данных Массив из N элементов для вершин Список массивов из M элементов для дуг

Хеш-функции V(x) = (x 1 a 1 +x 2 a 2 …+x n a n ) mod N, где x 1 …x n – координаты вершины х P(x) = (x 1 a 1 +x 2 a 2 …+x n a n ) mod M, где x 1..x n – координаты вершины, соответствующей концу дуги х a 1 …a n – веса. Простые числа

Анализ графа Для анализа графа используется алгоритм Тарьяна –Время работы линейное от количества вершин и ребер –Позволяет локализовать компоненты сильной связности графа – цепно-рекуррентные множества

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

Методы построения образа ячейки Далее рассмотрим некоторое количество методов построения образа ячейки –Точечный метод –Линейный метод –Адаптивный метод –Прямоугольный адаптивный метод

Построение образа ячейки: Точечный метод В ячейке равномерно берем некоторое количество точек –Например 4 Строим их образы Образ ячейки – объединение ячеек, в которых лежит хотя бы один образ взятых точек

Построение образа ячейки: Точечный метод

Построение образа ячейки: Линейный метод Из всех полученных образов находим минимальные и максимальные координаты Прямоугольник из минимальных и максимальных координат – построенный образ Для ускорения процесса построения образа ячейки используется разложение функции правой части системы в ряд Тейлора до второго члена с центром в центре этой ячейки f 1 (x) = f(x 0 ) +, где x 0 – координата центра ячейки

Построение образа ячейки: Линейный метод

Построение образа ячейки: Адаптивный подход Точки, в которых вычисляется значение функции, выбираются в зависимости от поведения функции Количество точек изменяется Выбираются только те точки, в которых это необходимо

Построение образа ячейки: Адаптивный метод Выбираем начальное разбиение ячейки Строим граф подразбиения –Вершины – точки в ячейки –Ребра – связывают вершины «соседних» точек –Длина ребра – расстояние между образами точек Строим сортированный по длине список ребер Если ребро длиннее – разбиваем его –Добавляем в граф новую вершину –Добавляем новые ребра к «соседним» вершинам вершинам цикла длиной 2. Добавляем образы построенных точек к образу Ограничение на разбиение

Построение образа ячейки: Адаптивный метод. Граф На рисунках показан пример подразбиения

Построение образа ячейки: Адаптивный метод. Начальное разбиение На рисунках показаны начальные разбиения для ячейки –Размерность 2 – 5 точек –Размерность 3 – 15 точек. –Размерность >3 – решение не выведено явно Метод достаточно сложен –Задача – улучшить его.

Построение образа ячейки: Адаптивный метод. Начальное разбиение

Реализация Генерируем код, который будет строить начальное разбиение для каждой ячейки –В результате будет работать на много быстрее –Оптимизировано под размерность системы –Нет накладных расходнов

Построение образа ячейки: Прямоугольный Адаптивный метод Вычисляем образ двух точек главной диагонали Если расстояние между точками велико – разбиваем ячейку: –рассматриваем ячейки заданные диагональю: точка центра и вершина. Рекурсия. Иначе добавляем полученную точку в образ –Если точка попадает близко к границе – добавляем соседнюю ячейку

Построение образа ячейки: Прямоугольный Адаптивный метод

Реализация Для реализации всей системы используется.NET Framework 2.0/3.5 –Использования generics Используется генерация кода в процессе работы приложения –Позволяет получить программу, которая оптимизирована для конкретной задачи размерность коллекции объекты представления данных

Реализация генерации кода Использует встроенный в.NET 2.0 компилятор C# –библиотека StringTemplate В сгенерированном коде генерируется реализация абстрактной фабрики –Ее приходится создавать при помощи рефлексии Генерируем классы, которые используются далее как типовые параметры в библиотеке –Проблема, как и коде работать с generic классами от сгенерированного типа?

Неявные типовые параметры Назависимо от того, где именно будет создан объект класса GenericClass`2, его –можно хранить как интерфейс, –при необходимости безопасно привести его в правильному типу и получить типовые аргументы class ICallback { void Callback (GenericClass _this) } class IService { void DoCallback(ICallback cb); } class GenericClass : IService { void DoCallback(ICallback cb) { cb.Callback(this); }

Отображение Хенона Вычисляем линейным методом Ячеек Ребер Локализуем цепно- рекуррентное множество системы Время построения 3 минуты

Отображение Хенона (2)

Пример. Отображение Икеда

Пример. Отображение Икеда. Линейный метод –Время работы 122сек. –Узлов

Пример. Отображение Икеда. Адаптивный –Время работы 641сек –Узлов

Пример. Отображение Икеда. Прямоугольны й адаптивный –Время работы 295сек. –Узлов

Множество Жюлиа Рассмотрим цепно- рекуррентное множество для следующего отображения

Множество Жюлиа Линейный метод 12 итераций 202 секунды вершин

Множество Жюлиа Прямоугол ьный адаптивный 12 итераций 466 секунды вершин

Отображение с задержкой Построим цепно- рекуррентное множество для значения параметра –a = 2.21

Отображение с задержкой. а=2.21 Линейный метод 7 шагов вершин 10 секунд

Отображение с задержкой. а=2.21 Прямоугол ьный адаптивный метод 7 шагов вершин 98 секунд

Пример. Трехмерная модель типа хищник-жертва-суперхищник

Линейный метод Шагов 8 Время 133сек Узлов

Пример. Трехмерная модель типа хищник-жертва-суперхищник. Адаптивн ый метод Шагов 7 Время 1167сек Узлов

Пример. Трехмерная модель типа хищник-жертва-суперхищник. Прямоугольны й адаптивный метод Шагов 9 Время 1548сек Узлов

Пример. Трехмерная модель типа хищник-жертва (2)

Трехмерная модель типа хищник-жертва Вычисляем при помощи линейного метода Ячеек Ребер Локализуем цепно- рекуррентное множество Проекция трехмерной системы Время построения 20 минут

Инвариантное множество

Логистическое отображение На основе логистического Используем линейный метод Последний шаг – точечный метод

Логистическое отображение

Сравнение методов На двумерных системах видно, –Линейный метод работает быстрее –Результат адаптивного метода содержит меньше вершин Прямоугольный Адаптивный метод использует слишком мало точек для построения образа ячейки. В 3-х мерном случае прямоугольный адаптивный метод позволяем получать результаты быстрее, чем даже линейный метод.

Публикации и выступления G. S. Osipenko, J. V. Romanovsky, N. B. Ampilova, E. I. Petrenko. «Computation of the Morse Spectrum», Journal of Mathematical Sciences (Kluwer Academic / Consultants Bureau), New York, v.120, No.2, March 2004 Petrenko E.I. «Implementation of symbolic image construction algorithm», Proc. of Regional Informatics Conference, Petrenko E.I., Ampilova N.B.«Dynamical systems investigation program», Microsoft technologies in theory and practice of programming in 2004 (third degree) Petrenko E.I., Ampilova N.B. «The elaboration and implementation of the program system for investigation of dynamical systems by symbolic dynamics methods». Microsoft technologies in theory and practice of programming in 2005 (second degree) Petrenko E.I. «Implementation of the Morse spectrum computation algorithm», «Computer Modeling of Dynamical Systems Workshop» (CMDS2004) international conference, SPBSTU, Matiyasevich D., Petrenko E.I. «Isolated sets of symbolic image construction algorithms», Stability and Control Processes Conference, SCP2005, Saint- Petersburg State University, Saint Petersburg, Russia. (report and publication), 2005

Публикации и выступления 2 Petrenko E.I. «On implementation of Symbolic Image», Report in Lulea, Sweden, Tekniska Universitet, 2005 Petrenko E.I. Development and Implementation of Algorithms for Construction of the Symbolic Image, Electronic journal Differential equations and control processes, 2006 Petrenko E.I., Ampilova N.B. «Методы нахождения образа ячейки в задаче построения символического образа». Microsoft technologies in theory and practice of programming in 2007 Г.С.Осипенко, А. В. Крупин, А. А. Безручко, Е. И. Петренко, А. Я. Капитанов «Построение инвариантых мер». Эл. ж. Дифференциальные уравнения и процессы управления. 4/2007http:// 4/2007 Ампилова Н.Б., Петренко Е.И., «Об оценке энтропии символического образа динамической системы». Вестник СПбГУ, принято к печати

Спасибо за внимание Вопросы?