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

Санкт-Петербургский государственный университет

На правах рукописи

ООьОЮ»^

Ловягин Никита Юрьевич

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

05.13.11 — Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей 01.03.02 — Астрофизика и звездная астрономия

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

О ;;1Мг'| ¿Ь \1

Санкт-Петербург, 2012

005016193

Работа выполнена на кафедре информатике математико-механическ^ факультета Санкт-Петербургского государственного университета

доктор физико-математических наук Лавров Юрий Аркадьевич

доктор физико-математических наук, профессор Братчпков Игорь Леонидович (Санкт-Петербургский Государственный Университет)

доктор физико-математических наук Соколов Владимир Владимирович (Специальная астрофизическая обсерватория РАН)

Санкт-Петербургский Государственный Университет Аэрокосмического Приборостроения

Защита диссертации состоится « г» » МДД_2042. г. в ^У ч. СО мин.

на заседании совета Д 212.232.51 по защите докторских и кандидатских диссертаций при Санкт-Петербургском государственном университете по адресу: 198504, Санкт-Петербург, Старый Петергоф, Университетский пр. 28, математико-механический факультет, ауд. 405.

С диссертацией можно ознакомиться в Научной библиотеке им. М. Горького Санкт-Петербургского государственного университета по адресу: 199034, Санкт-Петербург, Университетская наб., д. 7/9.

Автореферат разослан «1.9» Опр^лЯ 20 года.

Ученый секретарь диссертационного совета, доктор физико-математических наук, доцент

Научный руководитель: Официальные оппоненты:

Ведущая организация:

Общая характеристика работы

Актуальность работы. В настоящее время развитие естественных наук невозможно без применения вычислительной техники, в связи с чем требуется разработка программного обеспечения, содержащего реализации современных математических методов. Фрактальная геометрия нашла широкое применение во многих приложениях, в различных областях знания [7, 8,9] — в физике, биологии, экономике и др. Фрактальные методы анализа данных требуют больших объемов вычислений и использования специфических математических понятий. Особенность фрактальных методов такова, что многие задачи могут быть разбиты на классы подобных подзадач, для решения которых требуется одинаковая структура математического обеспечения. В связи с этим для решения ряда задач, возникающих в различных областях науки, требуется создание специфического программного обеспечения для численного анализа фрактальности множеств исследуемых объектов.

В настоящее время существует множество программ, таких как ГгасЮ-Ыата1 или Спо&а^4с12 по генерации фрактальных множеств, рассчитанных главным образом на визуализацию или моделирование фрактальных изображений, а исследователи, применяющие численные методы фрактальной геометрии в конкретных науках, не публикуют и не выкладывают на сайтах создаваемые ими программы. Также, из-за крайне большого объема вычислений, уделяется мало внимания ЗБ фрактальным структурам — в большинстве случаев исследователи не имеют доступа к кластерам и суперкомпьютерам, поэтому важно создание соответствующих прикладных программ именно для ПК.

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

'ЬЦр^Дгас torama.com/

211ир:/^по&ас^4d.sourceforge.net/

зультатов.

Хотя представляемый пакет и берет свое начало в космологии, его применение возможно и к другим подобным конечным множествам — как в астрофизике (например, грануляция на Солнце), так и в других областях знаний (множества молекул в газе, бактерий, людей, предприятий и т.п.). Программный пакет Э\УР представляет собой интерпретатор разработанного языка сценариев. При создании пакета автором решался ряд задач программирования на ПК, связанных с большим количеством точек (в пределах 109) исследуемого множества в многомерном пространстве.

В рамках современной космологической модели (АСБМ) однородность распределения материи, постулируемая в модели Фридмана, обеспечивается однородностью скрытого небарионного вещества и темной энергии. При этом переход к обычному видимому веществу (галактикам) требует дополнительных гипотез о возможной связи скрытого вещества с видимым веществом, что создает трудности в предсказании крупномасштабного распределения непосредственно наблюдаемых галактик [12]. В связи с этим, актуальной задачей современной космологии является изучение и сравнение с предсказаниями статистических характеристик пространственного распределения галактик в имеющихся реальных каталогах, содержащих сотни тысяч объектов. В частности, актуальным является вопрос об оценке масштаба неоднородности и фрактальной размерности крупномасштабного распределения галактик [10,

И, 13].

Цель работы. Разработать пакет прикладных программ, позволяющий

• как загружать готовые (полученные сторонними средствами) множества точек (в частности, каталоги галактик), так и средства для исследования базовых стандартных фрактальных распределений разной размерности (для сравнения поведения свойств с реальными распределениями и для проверки методов исследования);

• проводить автоматизированную массовую обработку различных выборок (например, сетку выборок разной глубины или исследование выборок реального множества с разным значением ограничения по параметру) — то есть требуется возможность пакетной обработки выборок;

• эффективно исследовать большие множества (в пределах ~ Ю9); повторно использовать ранее полученные результаты вычисления, как при возникновении одинакового этапа при исследовании похожих задачах, так и при

выполнении вычислений, с измененными параметрами (когда изменение параметров приводит к расхождению вычислений лишь на каком-то этапе расчета).

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

Также была поставлена задача применения разработанного пакета:

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

• сравнивая результаты вычисления корреляционных функций для искусственных распределений с корреляционными функциями для реальных каталогов галактик, сделать выводы о фрактальной размерности и масштабе однородности крупномасштабной структуры Вселенной (КСВ).

Объектом исследования работы являются фрактальные свойства больших пространственных множеств точек, снабженных дополнительными численными характеристиками, числом элементов в пределах 10°. Результаты, выносимые на защиту.

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

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

• Реализованы и включены в язык посредством плагинов алгоритмы загрузки конечных множеств нагруженных точек (таких как каталоги галактик), генерации базовых конечных фрактальных множеств, анализа основных фрактальных характеристик, создания графиков.

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

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

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

• Исследование радиальных распределений галактик на фрактальных множествах различной размерности показало, что не параметры аппроксимации эмпирической функцией, а уровень относительных флуктуаций зависит от фрактальной размерности. Уровень флуктуаций в распределениях галактик согласуется с оценкой границ размерности в 2.2-2.4.

• Анализ данных каталогов галактик показал оценку фрактальной размерности КСВ в 2.25 ±0.2 на масштабах от 5 до 100 Мпк3. Эксперимент показал, что в настоящее время корреляционным методом на больших масштабах сделать надежный вывод о величине размерности не представляется возможным. Исследование первого корня редуцированной корреляционной функции показало нижнюю границу оценки масштаба выхода на однородность в 200-300 Мпк.

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

http ://swpproject.sourceforge.net и использован для исследования фрактальных свойств природных множеств изолированных точек, в частности, в космологии. Полученные ограничения на применимость корреляционных методов, используемых для исследования фрактальных свойств КСВ, должны учитываться при дальнейших исследованиях.

31 пк и з • 1016 м.

Реализация. Пакет прикладных программ представлен в виде интерпретатора языка сценариев и документации. Пакет написан на С++ и является кроссплатформеннным (для Linux и Windows).

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

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

С использованием данного пакета, путем численного эксперимента и анализа каталогов галактик автор показал возможность использования ПК для анализа распределений конечных (в пределах 10°) фрактальных свойств и что

• по корреляционным функциям можно надежно определять фрактальную размерность только до масштабов на 1-1.5 порядка меньших наибольшего масштаба, до которого оценка корреляционной функции может быть вычислена;

• первый корень неполной корреляционной функции не является прямым критерием значения масштаба выхода на однородность;

• в радиальных распределениях галактик в выборках, ограниченных по предельной видимой звездной величине, от фрактальной размерности зависит уровень относительных флуктуаций: чем меньше размерность, тем уровень флуктуаций выше;

• по данным каталога SDSS фрактальная размерность КСВ оценивается в 2.25 ± 0.2 на масштабах от 5 до как минимум 100 Мпк. Корреляционными методами на больших масштабах определить фрактальную размерность невозможно из-за систематических ошибок данного метода; нижняя граница оценки масштаба выхода на однородность по первому корню корреляционной функции составляет 200-300 Мпк.

Апробация. Результаты работы докладывались на

• Второй Пулковской молодежной конференции в ГАО РАН в 2009 году;

• Конференции (школе-семинаре) по физике и астрономии для молодых ученых Санкт-Петербурга и северо-запада в СПбГПУ в 2009 году;

• Всероссийской Астрономической Конференции ВАК-2010 в Специальной Астрофизической Обсерватории РАН в 2010 году;

• Конференции "Технологии Microsoft в теории и практике программирования" в СПбГПУ в 2011 году (доклад занял третье место);

• Международной конференции молодых ученых в Киеве Young Scientists Conference в 2011 году;

• Семинаре кафедры астрофизики математико-механического факультета СПбГУ в 2011 году.

• Семинаре кафедры информатики математико-механического факультета СПбГУ в 2011 году.

Публикации. Основные результаты, полученные при выполнении диссертационной работы опубликованы в 6 работах автора. Работа [1] опубликована в издании по перечню ВАК 2011 г. для специальности 05.13.11, работа [2] по перечню ВАК 2011 г. для специальности 01.03.02.

Структура и объем работы. Диссертационная работа объемом 105 страниц состоит из введения, 5 глав, 1 приложения и списка литературы, включающего 55 наименований. Работа содержит 26 иллюстраций и 9 таблиц.

Разработанное автором программное обеспечение имеет объем около 22000 строк кода.

Содержание работы

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

В главе 1 рассмотрены исходные положения поставленной задачи, приводится идея фрактальной модели и описание базовых отличий фрактальности от однородности, в частности, применительно к крупномасштабной структуре Вселенной (КСВ). При фрактальном подходе каждая галактика рассматривается как одна — изолированная — точка. В основу исследования КСВ легли каталоги галактик, содержащие данные о положениях и красных смещениях объектов. Подобные каталоги как правило доступны в сети интернет

в виде текстовых файлов (используется псевдоформат CSV, от англ. Coma-Separated Values — значения, разделенные запятой) — от пакета требуется возможность их загрузки. Подчеркивается важность выделения подвыборок по разнообразным характеристикам точек. Обосновывается необходимость создания пакета программ, позволяющего анализировать конечные множества изолированных точек, снабженных дополнительными характеристиками (весами), набор которых может выбирать пользователь.

В главе 2 описаны базовые принципы, которые легли в основу языка сценариев SWP.

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

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

В языке сценариев помимо идентификаторов, числовых и строковых типов данных, операций присваивания := и арифметических, имеются специфические типы: "промежуток" (задает промежуток вещественных чисел, например [0:1) — для создания выборок и границ), "точки" (наборы поименованных полей типа real), "множества" (конечные массивы точек)4 и др. Например, вызов "point (х = 1.0, у = 2.5)" создает точку с двумя полями х и у, записывая в них значения 1.0 и 2.5 соответственно. Еще один важный тип данных — "свойство точки", это функция точки, возвращающая число типа real. Например, вызов pp_norm (х, у) создает свойство точки, вычисляющую Евклидову норму точки, координаты которой записаны в полях х и у (в R2). Вызов "р := point (х, у, г = pp_norm (х, у));" записывает в переменную р точку, с постоянными полями х и у, и вычисляемым полем г (значение поля г будет вычисляться как упомянутая выше функция точки от р). В язык включен механизм защиты от бесконечной рекурсии при создании точек с вычисляемыми через себя полями.

4В дальнейшем под множеством точек понимается конечное множество точек.

Многие функции в качестве параметра принимают так называемый "список аргументов" — список пар5 "строка (имя параметра) = значение". Это удобный способ указывать аргументы в произвольном порядке и пропускать необязательные.

"Граница" также является типом данных. Например, вызов

b := brd_sphere (apply = (x, у),

range =(1.0:1.5),

center = point (x=0.0, y=0.0));

создает границу, внутренность которой есть кольцо с центром в точке с координатами (0,0) (аргумент center). То, что координаты хранятся в полях х и у задается аргументом apply, радиусы кольца есть 1.0 и 1.5 — точка принадлежит кольцу тогда и только тогда, когда радиус точки принадлежит промежутку, указанному в качестве аргумента range.

Рассмотрим пример создания однородного распределения (производится функцией set_gen_uniform) из 10000 точек (аргумент number) внутри выше упомянутого кольца (аргумент border). Аргумент apply задает список полей-координат (две координаты, значит множество будет создаваться в R2), аргумент generator указывает используемый датчик случайных чисел (последовательность #1), а аргумент size задает размер изначального разброса точек (до фильтрации по границе, должен покрыть кольцо); поскольку аргумент point не задан, то множество будет состоять из точек с двумя полями point (х, у):

s := set_gen_uniform ("number" = 10000, "apply" = (x, у), "border" = b, "generator" = rnd_mt(l), "size" = 1.5);

Тип данных "множество точек" используется шире, чем конечное множество точек в пространстве. Механизм доступа к "весам" точки по имени поля позволяет создавать в виде множества, например, табулированные функции — так представляется результат вычисляемых по точкам корреляционных функций. Автор заложил возможность использования произвольной размерности пространства: пользователь сам сообщает, какие поля содержат координаты точки и сколько их.

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

5Типы данных "список" и "пара" создаются соответственно операциями "," и "=".

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

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

В главе 3 описываются базовые фрактальные распределения и вспомогательные средства, реализованные в 3\\Ф.

Помимо генерации однородных распределений точек, реализован алгоритм создания фрактальных множеств точек с предопределенной размерностью Б — в качестве такового было выбраны последовательные приближения к случайному Канторову множеству (пыль Кантора), обобщенному на случай К". Описание данных алгоритмов имеются в диссертации.

ВаЖной задачей при создании пакета был учет пространственных границ множества. Такие операции, как, например, построение функции условной плотности требуют знания расстояния до границы от каждой точки. При проведении пространственного преобразования граница должна меняться соответственно. Каждое множество снабжается границей, определяющей часть пространства, в котором лежит множество. Граница множества есть совокупность элементарных границ, выделяющих часть пространства7. Точка лежит в границах множества, если она принадлежит части пространства, выделенной каждой из элементарных границ, расстояние от точки до границы есть минимум среди расстояний до каждой из них. При проведении простран-

6ЬЦр:/^пир1о1.тГо

7Таких как, например, сфера— частью пространства, в котором лежит множество, по выбору пользователя может являться "внутренность" или "внешность" сферы.

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

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

Кроме прямоугольного параллелепипеда, требуемого для создания однородного распределения и пыли Кантора, автором реализованы элементарные границы, встречающиеся в космологических задачах: сфера или сферическая оболочка (в К"), ограничение по угловым сферический координатам а и 5 в К3 (без ограничения 0 ^ п ^ 2п, -71-/2 ^ 6 < тг/2), ограничение по полярному углу (К2). Реализованные преобразования параллельного переноса и гомотетии корректно преобразуют сферические и прямоугольные границы. Ограничение по радиусу может быть задано непосредственно или как ограничение от иного поля, функция которого есть радиус — например, по красному смещению.

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

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

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

-5 -10 -15 -20 -25 -30 -35

0 100 200 300 400 500 600 700 800 900 1000

Рис. 1. Диаграмма расстояние (абсцисса) абсолютная звездная величина (ордината) галактик каталога SDSS. Каждой галактике соответствует точка. Черным цветом показаны точки, попавшие в полную по объему выборку до расстояния 400 Мпк. Предельная абсолютная-звездная величина выбрана программой, по автоматически построенной огибающей.

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

Для исследования фрактальных множеств изолированных точек используются корреляционные функции, характеризующие свойства скучивания точек — зависимость функции количества точек на данном расстоянии от расстояния (масштаба). Следуя [10], различают полную и редуцированную кор-

реляционные функции, оба варианта реализованы в пакете. Полная корреляционная функция есть характеристика плотности множества на данном масштабе, в то время как редуцированная — отклонения плотности на данном масштабе от средней плотности во всем множестве. Примером полной корреляционной функции является условная плотность Г (точнее — концентрация, так как речь идет о конечных множествах изолированных точек). Условная концентрация Г(г) есть средняя концентрация точек в шарах радиуса г, центры которых располагаются в точках множества, и которые целиком лежат в пространственных границах множества. Формально условную концентрацию можно рассчитать для rmin < г < Лт„.х, где rmin — расстояние между двумя ближайшими точками множества, a Rma.х — радиус наибольшего "пригодного" шара. Для фрактальных и однородных (D = п) множеств Г(г) = ArD~n.

Редуцированная корреляционная функция £ рассчитывается при помощи генерации однородного множества сравнения в тех же границах, что и исследуемое множество и через количества пар точек множества и точек множества сравнения, находящихся на расстоянии г, реализованы три способа оценки.

Для однородного множества £(г) = 0, для фрактального £(r) = ArD~n. Вычисление корреляционной функции возможно для г от rmin до расстояния между самыми далекими точками множества гтах.

В главе описан предложенный автором алгоритм, автоматизирующий вычисление угла наклона функции: ожидается, что корреляционная функция и условная плотность удовлетворяют условию f(r) ос rD~n, что соответствует прямой линии в логарифмических координатах (здесь п — размерность пространства, a D — оценка фрактальной размерности). Численный эксперимент показал, что корреляционные функции не удовлетворяют этому соотношению на всем участке, где они могут быть вычислены, что ставит задачу нахождения участков, где функция является прямолинейной, по наклону которых можно найти фрактальную размерность. Пакет автоматически находит участки прямолинейности табулированной функции, чтобы не подбирать их вручную. Участок табулированной функции /, заданной на точках х0, х\, ..., хп, считается прямолинейным, если

где I — искомая аппроксимирующая линейная функция, построенная на от-

резке [х0,х„] методом наименьших квадратов, — выбираемый "критерий прямолинейности". Формула предложена автором. Для рассматриваемых случаев (условной плотности и корреляционной функции) этот критерий показывает себя достаточно независимым от количества точек во множестве и количества точек табулирования функции. На рис. 2 показан пример корреляционной функции, аппроксимирующей прямой и найденных корней.

log г

Рис. 2. Редуцированная корреляционная функция, график в логарифмических координатах (взят десятичный логарифм от £(r) + 1) пыли Кантора множества размерности '2.7, выборка в сферической границе. Пунктирной линией показана аппроксимирующая прямая, точечной — границы в которых произведена аппроксимация (автоматический выбор наиболее длинного прямолинейного участка). Левые корни на участке, где функция подвержена большим случайным флуктуациям, исключены, так как в скрипте было запрошено искать корни только правее начала прямолинейного участка, и брать первый из них.

В главе 5 проводится анализ особенности астрономических наблюдательных данных, с помощью которых производится исследование КСВ.

Для исследования геометрических свойств требуется знание пространственных координат точек, поэтому необходима возможность перевода каталожных данных — сферические координаты и красное смещение (КС) галактики8 — в пространственные координаты.

Неизбежным фактором в астрономии является наблюдательная селекция — ограничение на видимую яркость объекта. Более того, обычно каталоги

8При исследовании КСВ через красное смещение галактики вычисляется расстояние до нее.

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

Также этой в главе излагаются результаты анализа численного эксперимента, выполненного автором с помощью SWP. Приведены ограничения на применимость корреляционных методов при вычислении масштаба однородности и фрактальной размерности. Указаны следствия этих ограничений применительно к космологии и результаты оценки фрактальной размерности и нижней границы масштаба однородности КСВ, выполнение с учетом этих ограничений. Была проанализирована сетка выборок однородных и фрактальных распределений различной размерности распределения галактик. Были взяты подвыборки разной глубины как во всей сфере, так и с ограничением по телесному углу. Также были взяты имитации полной по объему выборки до разных красных смещений.

Анализ корреляционных функций для сетки выборок показал, что условная концентрация позволяет определить фрактальную размерность с точностью до 0.1, но только на масштабах не превышающих 10-30% от радиуса наибольшего шара, целиком лежащего в пространственных пределах выборки. Значение первого корня редуцированной двухточечной корреляционной функции в ограниченных в пространстве выборках из фрактальных множеств растет при увеличении размеров выборки, следовательно, эта величина не может служить прямым указанием на масштаб однородности, а только на его нижнюю оценку. Зависимость первого корня корреляционной функции от глубины подвыборки для множеств разной размерности и каталога SDSS показана на рис. 3.

Также этой в главе описан метод исследования радиальных распределений галактик. Идея метода состоит в аппроксимации радиального распределения — зависимости количества галактик в сферической оболочке заданной малой толщины от расстояния до нее — строящегося в выборках, ограниченных по предельной видимой звездной величине эмпирической формулой, часто используемой в космологии: N{r) = A (r/r^)" ехр (- (г/гк)7).

! 1 т- 1— 1 щ-

С ♦

.Г' '

«V*.

г

• . ш

Ж

Б = 2 . 0 •

0=2.7- ---"

1 0=2.3- I I 1 -«--- 1

50 100 150 200 250 300 350 400 > Мрс

Рис. 3. Зависимость величины первого корпя корреляционной функции от глубины выборки. Слева: чисто фрактальные множества разных размерностей (показаны разными символами). Справа: полные по объему выборки каталога ЗПЗЯ разной глубины, над точками подписано число галактик, попавших в выборку, на правой оси отложены предельные абсолютные звездные величины выборок.

Автором реализован и включен в пакет алгоритм нахождения минимума на сетке, с итерациями по уменьшению шага сетки. Эксперимент показал, что параметры аппроксимации определяются ненадежно, и для разных комбинаций параметров форма кривой может быть похожа. Однако, интерес представляют относительные флуктуации ДЛГ(г) = (Л^0(г) - NCL(r))/Nu(r), где А'0 — наблюдаемое радиальное распределение, — аппроксимирующая функция. Автор графически сравнивал уровень флуктуаций с величиной а = 1 ¡у[ТГа — чем меньше фрактальная размерность, тем уровень флуктуаций больше. Иллюстрирующие примеры радиальных распределений имеются в диссертации.

Исследование редуцированной корреляционной функции для каталога галактик ЭБЭЗ дает нижнюю границу на величину масштаба однородности в 300 Мпк. В пределах этого масштаба фрактальная размерность оценивается в 2.1-2.4. Это согласуется с уровнем относительных флуктуаций в радиальных распределений галактик.

В приложении приводятся тексты некоторых сценариев, использованных для выполнения диссертационной работы.

Сцисок опубликованных работ по теме диссертации

|1| Лоаянин Н. Ю. Статистически« свойства пространственного распределения галактик // Бюлл. Спец. астрофиз. Обсерв. 2009. Т. 64, Вып. 3. С. '223-235.

|2| Ловягип H. 10. Пакет прикладных программ для анализа фрактальных стюйт . множеств нагруженных точек. // Комп. инстр. в образ. 2011. Т. 5, С. 19-26.

|3| Лоаягин Н. Ю. Моделирование фрактальных распределений галактик // Известия ГАО в Пулкове. 2009. Т. 219, Вып. 3. С. 37-52

|4| Ловягип Н. Ю. Моделирование и выявление фрактальных структур в пространственном распределении галактик // Копф. (тик.-сем.) по физике и астрономии для молодых ученых Спб. и северо-запада. Тез. докл. С., 2009.

|5| Ловягин Н. 10. Программная система корреляционного анализа фрактальных структур в распределении галактик // Технологии Microsoft в теории и практике программирования. Материалы межвузовского конкурса-конференции студентов, аспирантов и молодых ученых Северо-Запада. Санкт-Петербург. 2011.

|6| Lnvyagin N. Project of program package for exploring of cosmologieal fractals Advances in Astronomy arid Physics, Kyiv, 2011 V. 2, I. 1. Pp. 63-66.

Цитированная литература

|7] Манделъброгп Б. Фрактальная геометрия природы. М.: Институт компьютерных исследований, 2002. 656 с.

|8] Addison P. S. Fractals and chaos: an illustrated course. Bristol, Philadelphia: Institute of Physics Publishing, 1997. 256 p.

|9| Falconer K. Fractal geometry, New York: John Wiley & Sons, 1990. 155 p.

[ 101 Gnbrie.li A., Sylos Labini F., Joyce M., Pie.trone.ro L Statistical physics for cosmic structures. Berlin — Heidelberg — New York - Barcelona — Hong Kong — London - Milan - Paris - Tokyo: Springer, 2004. 440 p.

|11] Martinez V. J., Saar E. Statistics of the Galaxy Distribution. Boca Ration — London - New York - Washington, D. C.: CHAPMAN & HALL/CRC, 2002. 432 p.

|12| Sprintjel. V., et al. Simulations of the formation, evolution and clustering of galaxies and quasars // Nature. 2005. V. 435, I. 7042, Pp. 629-636.

]13] Sylos Labini F. Inhomogeneities in the universe // Classical and Quantum Gravity. 2011. V. 28, I. 16, Pp. 164003.

Подписано к печати 11.04.12. Формат 60х 84 . Бумага офсетная. Гарнитура Тайме. Печать цифровая. Печ. л. 1,0. Тираж 100 экз. Закат 5429.

Отпечатано в Отделе оперативной полиграфии химического факультета СПбГУ 198504, Санкт-Петербург. Старый Петергоф, Университетский пр., 26 Тел.: (812) 428-4043, 428-6919

61 12-1/869

Санкт-Петербургский государственный университет

На правах рукописи

Ловягин Никита Юрьевич

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

05.13.11 — Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей 01.03.02 — Астрофизика и звездная астрономия

ДИССЕРТАЦИЯ на соискание ученой степени кандидата физико-математических наук

Санкт-Петербург, 2012

Оглавление

Введение 4

1. Постановка задачи 20

1.1. Однородность и фрактальность................ 20

1.2. Астрономические наблюдательные данные.......... 22

1.2.1. Краткие сведения об используемых астрономических величинах..................................................22

1.2.2. Особенности представления каталогов галактик ... 25

1.3. Требования к создаваемому программному обеспечению . . 26

2. Язык сценариев 27

2.1. Структура программы в языке..................................28

2.2. Операции и вызов по параметру................................30

2.3. Организация хранения данных..................................32

2.4. Границы и преобразования множества........................36

2.5. Конвертирование множеств......................................37

2.6. Вывод результатов ....................................38

2.7. Плагины ..........................................................41

2.8. Структура пакета программ..................41

3. Генерируемые множества и вспомогательные методы 46

3.1. Однородное распределение...................46

3.2. Пыль Кантора....................................................47

3.3. Нахождение центра..............................................50

3.4. Пространственные границы ....................................51

3.5. Карты и полярные диаграммы..................................54

3.6. Огибающие и полные по объему выборки ....................57

4. Корреляционные функции 59

4.1. Теория корреляционных функций..............................59

4.2. Оценки условной концентрации................................61

4.3. Оценки редуцированной корреляционной функции..........62

4.4. Алгоритм вычисления корреляционных функций............63

4.5. Нахождение угла наклона и корня функции..................66

5. Результаты исследований 70

5.1. Первый корень редуцированной корреляционной функции . ТО

5.2. Условная плотность..............................................73

5.3. Радиальные распределения галактик..........................79

Заключение 92

Список литературы 94

А. Примененные сценарии 99

А.1. Исследование условной концентрации..........................99

А.2. Исследование радиальных распределений..........103

Введение

Общая характеристика работы

Актуальность работы

В настоящее время развитие естественных наук невозможно без применения вычислительной техники, в связи с чем требуется разработка программного обеспечения, содержащего реализации современных математических методов. Фрактальная геометрия нашла широкое применение во многих приложениях, в различных областях знания [17, 11, 24, 14] — в физике, биологии, экономике и др. Фрактальные методы анализа данных требуют больших объемов вычислений и использования специфических математических понятий. Особенность фрактальных методов такова, что многие задачи могут быть разбиты на классы подобных подзадач, для решения которых требуется одинаковая структура математического обеспечения. В связи с этим для решения ряда задач, возникающих в различных областях науки, требуется создание специфического программного обеспечения для численного анализа фрактальности множеств исследуемых объектов.

В настоящее время существует множество программ [12], таких как Ргас1>0-11ата [50] или Спой:ас14с1 [51], по генерации фрактальных множеств, рассчитанных главным образом на визуализацию или моделирование фрактальных изображений, а исследователи, применяющие численные методы фрактальной геометрии в конкретных науках, не публикуют и не выкладывают на сайтах создаваемые ими программы. Также, из-за крайне большого объема вычислений, уделяется мало внимания ЗБ фрактальным структурам — в большинстве случаев исследователи не имеют доступа к кластерам и суперкомпьютерам, поэтому важно со-

здание соответствующих прикладных программ именно для ПК.

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

Хотя представляемый пакет и берет свое начало в космологии, где методы фрактальной геометрии используются для описания свойств крупномасштабной структуры Вселенной [30], его применение возможно и к другим подобным конечным множествам — как в астрофизике (например, грануляция на Солнце), так и в других областях знаний (множества молекул в газе, бактерий, людей, предприятий и т.п.). Программный пакет Б\¥Р представляет собой интерпретатор разработанного языка сценариев. При создании пакета автором решался ряд задач программирования на ПК, связанных с большим количеством точек (в пределах 109) исследуемого множества в многомерном пространстве.

В рамках современной космологической модели (АСБМ) однородность распределения материи, постулируемая в модели Фридмана, обеспечивается однородностью скрытого небарионного вещества и темной энергии. При этом переход к обычному видимому веществу (галактикам) требует дополнительных гипотез о возможной связи скрытого вещества с видимым веществом, что создает трудности в предсказании крупномасштабного распределения непосредственно наблюдаемых галактик [38]. В связи с этим, актуальной задачей современной космологии является изучение и сравнение с предсказаниями статистических характеристик пространственного распределения галактик в имеющихся реальных каталогах, содержащих сотни тысяч объектов. В частности, актуальным является вопрос об оценке масштаба неоднородности и фрактальной размерности крупномасштабного распределения галактик [25, 30, 34, 35, 39, 40, 43, 42, 44, 45].

Цель работы

Разработать пакет прикладных программ, позволяющий

• как загружать готовые (полученные сторонними средствами) множества точек (в частности, каталоги галактик), так и средства для исследования базовых стандартных фрактальных распределений разной размерности (для сравнения свойств с реальными распределениями и для проверки методов исследования);

• проводить автоматизированную массовую обработку различных выборок (например, сетку выборок разной глубины или исследование выборок множества с разным значением ограничения по параметру) — то есть требуется возможность пакетной обработки выборок;

• эффективно исследовать большие множества (в пределах ~ Ю9); повторно использовать ранее полученные результаты вычисления, как при возникновении одинакового этапа- при исследовании похожих задачах, так и при выполнении вычислений, с измененными параметрами (когда изменение параметров приводит к расхождению вычислений лишь на каком-то этапе расчета).

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

Также была поставлена задача применения разработанного пакета:

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

• сравнивая результаты вычисления корреляционных функций для искусственных распределений с корреляционными функциями для реальных каталогов галактик, сделать выводы о фрактальной размерности и масштабе однородности крупномасштабной структуры Вселенной (КСВ).

Объект исследования

Объектом исследования работы являются фрактальные свойства больших пространственных множеств точек, снабженных дополнительными численными характеристиками, числом элементов в пределах 109.

Результаты, выносимые на защиту

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

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

• Реализованы и включены в язык посредством плагинов алгоритмы загрузки конечных множеств нагруженных точек (таких как каталоги галактик), генерации базовых конечных фрактальных множеств, анализа основных фрактальных характеристик, создания графиков.

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

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

Корреляционная функция не показывает систематических эффектов, связанных с несферичностыо выборки и взятием полных по объему выборок.

• Исследование радиальных распределений галактик на фрактальных множествах различной размерности показало, что не параметры аппроксимации эмпирической функцией, а уровень относительных флуктуаций зависит от фрактальной размерности. Уровень флуктуаций в распределениях галактик согласуется с оценкой границ размерности в 2.2-2.4.

• Анализ данных каталогов галактик показал оценку фрактальной размерности КСВ в 2.25 ± 0.2 на масштабах от 5 до 100 Мпк1. Эксперимент показал, что в настоящее время корреляционным методом на больших масштабах сделать надежный вывод о величине размерности не представляется возможным. Исследование первого корня редуцированной корреляционной функции показало нижнюю границу оценки масштаба выхода на однородность в 200-300 Мпк.

Научная новизна

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

Практическая ценность

Представляемый программный продукт выложен в сети интернет по адресу

http ://swpproject.sourceforge.net

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

Реализация

Пакет прикладных программ представлен в виде интерпретатора языка сценариев и документации. Пакет написан на С++ и является кросс-платформеннным (для Linux и Windows).

Достоверность

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

Основные выводы

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

С использованием данного пакета, путем численного эксперимента и анализа каталогов галактик автор показал возможность использования ПК для анализа распределений конечных (в пределах 109) фрактальных свойств и что

• по корреляционным функциям можно надежно определять фрактальную размерность только до масштабов на 0.5-1 порядка меньших наибольшего масштаба, до которого оценка корреляционной функции может быть вычислена;

• первый корень неполной корреляционной функции не является прямым критерием значения масштаба выхода на однородность;

• в радиальных распределениях галактик в выборках, ограниченных по предельной видимой звездной величине, от фрактальной размерности зависит уровень относительных флуктуаций: чем меньше размерность, тем уровень флуктуаций выше;

• по данным каталога SDSS фрактальная размерность КСВ оценивается в 2.25 ± 0.2 на масштабах от 5 до как минимум 100 Мпк. Корреляционными методами на больших масштабах определить фрактальную размерность невозможно из-за систематических ошибок данного метода; нижняя граница оценки масштаба выхода на однородность по первому корню корреляционной функции составляет 200-300 Мпк.

Апробация

Результаты работы докладывались на

• Второй Пулковской молодежной конференции в ГАО РАН в 2009 году;

• Конференции (школе-семинаре) по физике и астрономии для молодых ученых Санкт-Петербурга и северо-запада в СПбГПУ в 2009 году;

• Всероссийской Астрономической Конференции ВАК-2010 в Специальной Астрофизической Обсерватории РАН в 2010 году;

• Конференции "Технологии Microsoft в теории и практике программирования" в СПбГПУ в 2011 году (доклад занял третье место);

• Международной конференции молодых ученых в Киеве Young Scientists Conference в 2011 году;

• Семинаре кафедры астрофизики математико-механического факультета СПбГУ в 2011 году.

• Семинаре кафедры информатики математико-механического факультета СПбГУ в 2011 году.

Публикации

Основные результаты, полученные при выполнении диссертационной работы опубликованы в 6 работах автора. Работа [8] опубликована в издании по перечню ВАК 2011 г. для специальности 05.13.11, работа [10] по перечню ВАК 2011 г. для специальности 01.03.02.

Структура и объем работы

Диссертационная работа объемом 105 страниц состоит из введения, 5 глав, 1 приложения и списка литературы, включающего 55 наименований. Работа содержит 26 иллюстраций и 9 таблиц.

Разработанное автором программное обеспечение имеет объем около 22000 строк кода.

Содержание работы

В главе 1 рассмотрены исходные положения поставленной задачи, приводится идея фрактальной модели и описание базовых отличий фрак-тальности от однородности, в частности, применительно к крупномасштабной структуре Вселенной (КСВ). При фрактальном подходе каждая галактика рассматривается как одна — изолированная — точка. В основу исследования КСВ легли каталоги галактик, содержащие данные о положениях и красных смещениях объектов. Подобные каталоги как правило доступны в сети интернет в виде текстовых файлов (используется псевдоформат CSV, от англ. Coma-Separated Values — значения, разделенные запятой) — от пакета требуется возможность их загрузки. Подчеркивается важность выделения подвыборок по разнообразным характеристикам точек. Обосновывается необходимость пакета программ, позволяющего анализировать конечные множества изолированных точек, снабженных дополнительными характеристиками (весами), набор которых может выбирать пользователь.

В главе 2 описаны базовые принципы, которые легли в основу языка сценариев SWP.

Исходя из требований автоматизации обработки выборок, а также из-за многоэтапности процесса анализа каждой выборки — сформиро-

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

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

В языке сценариев помимо идентификаторов, числовых и строковых типов данных, операций присваивания := и арифметических, имеются специфические типы: "промежуток" (задает промежуток вещественных чисел, например [0:1) — для создания выборок и границ), "точки" (наборы поименованных полей типа real), "множества," (конечные массивы точек)2 и др. Например, вызов "point(х = 1.0, у = 2.5)" создает точ