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

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

005045036

ЕРШОВА Арина Владимировна

ИТЕРАЦИОННЫЕ МЕТОДЫ И АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧИ СИЛЬНОЙ ОТДЕЛИМОСТИ

05.13.17 — теоретические основы информатики

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

2 4 МАЙ 2012

Челябинск — 2012

005045036

Работа выполнена на кафедре дифференциальных уравнений и динамических систем ФГБОУ ВПО «Южно-Уральский государственный университет» (национальный исследовательский университет)

Научный руководитель: СОКОЛИНСКАЯ Ирина Михайловна

кандидат физ.-мат. наук, доцент

доцент кафедры дифференциальных уравнений и динамических систем, ФГБОУ ВПО «Южно-Уральский государственный университет» (национальный исследовательский университет)

Официальные оппоненты: УХОБОТОВ Виктор Иванович

доктор физ.-мат. наук, профессор

зав.кафедрой теории управления и оптимизации, ФГБОУ ВПО «Челябинский государственный университет»

ОЛЕНЕВ Николай Николаевич кандидат физ.-мат. наук, доцент

старший научный сотрудник отдела «Математическое моделирование экономических систем», ФГБУН Вычислительный центр им. А.А. Дородницына Российской академии наук (ВЦ РАН)

Ведущая организации: Федеральное государственное бюджетное учреждение

науки Институт математики и механики Уральского отделения Российской академии наук (ИММ УрО РАН) (г. Екатеринбург)

Защита состоится 15 июня 2012 г. в 12:00 часов на заседании диссертационного совета Д 212.298.18 при ФГБОУ ВПО «Южно-Уральский государственный университет» (национальный исследовательский университет) по адресу: 454080, г. Челябинск, пр. Ленина, 76, ауд. 1001.

С диссертацией можно ознакомиться в библиотеке Южно-Уральского государственного университета.

Автореферат разослан " -/¿7 " ^¿Сие-_2012 г.

Ученый секретарь диссертационного совета

М.Л. Цымблер

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

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

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

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

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

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

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

1. Описать общий подход к решению задачи сильной отделимости двух выпуклых многогранников на основе последовательных проектирований.

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

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

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

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

Научная новизна работы заключается в следующем:

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

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

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

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

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

- на Международной конференции «Алгоритмический анализ неустойчивых задач» (1-6 сентября 2008 г., г. Екатеринбург);

- на Международной научной конференции «Параллельные вычислительные технологии (ПаВТ'2010)» (29 марта - 2 апреля 2010 г., г. Уфа);

- на XVIII Международной конференции «Математика. Экономика. Образование» (25 мая - 1 июня 2010 г., г. Новороссийск);

- на Международной научной конференции «Научный сервис в сети Интернет: суперкомпьютерные центры и задачи» (20-25 сентября 2010 г., г. Новороссийск);

- на XIV Всероссийской конференции "Математическое программирование и приложения" (28 февраля - 4 марта 2011 г., г. Екатеринбург);

- на Международной научной конференции «Научный сервис в сети Интернет: эк-зафлопсное будущее» (19-24 сентября 2011 г., г. Новороссийск);

- на Международной научной конференции «Параллельные вычислительные технологии (ПаВТ'2012)» (26-30 марта 2012 г., г. Новосибирск).

Публикации. По теме диссертации опубликовано 10 печатных работ, причем работы [1—4] опубликованы в журналах, включенные ВАК в перечень журналов, в которых должны быть опубликованы основные результаты диссертаций на соискание ученой степени доктора и кандидата наук. Получено 3 свидетельства Роспатента об официальной регистрации программ для ЭВМ. В совместных работах научному руководителю И.М. Соколинской принадлежит постановка задачи, A.B. Ершовой принадлежат все полученные результаты.

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения и библиографии. Объем диссертации составляет 97 страниц, объем библиографии — 92 наименования.

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

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

В первой главе, «Распознавание образов и фейеровские отображения», дается классификация основных задач распознавания, к которым относится задача сильной отделимости. Приводятся базовые теоремы, касающиеся задачи отделимости непересекающихся многогранников. Рассматриваются основные положения теории фейеровских отображений и процессов, являющихся обобщением операции проектирования.

Определение 1. Пусть pe^R" —>R"|. Отображение <р называется М-фейеровским, если

9>{У)~У> VУеМ> Щх)-.И|<!1*-:>'1> VУеМ> VxeM.

Последовательность {j;t j cS", {xt}niM = 0 называется М-фейеровской, если Jjr*+i-j'l<ljtt->'l. Vk.VyeM.

Тип 1 (однозначное фейеровское отображение). Пусть в R" задана конечная система линейных неравенств

Ах<Ь: l](x)=(arx)-bJ<Q, / = 1,...,т, (1)

где üjjt 0 для любого /.Определим /J(jc) = max{/y(jr),o|,/ = 1,...,/я. Тогда фейеровское отображение первого типа имеет вид:

» /;(д:)

Р)

hl f

для любой системы положительных коэффициентов \af >0|. _/' = l,...,m, таких, что = 1 и коэффициентов релаксации 0 < < 2.

У=1

Тип 2 (многозначное фейеровское отображение) Сконструируем фейеровское отображение второго типа следующим образом:

шах IJ (дг)

(J,| Р СЗ)

IKII

где j\ — любой из индексов, на котором достигается max/J (х), 0 < X < 2 — коэффициент релаксации.

В завершение главы 1 дается аналитический обзор известных методов решения задачи сильной отделимости.

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

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

М = {х | Ах<,Ь}±0\

И = {х\Вх£с1}ф&, (4)

Мп N = 0.

Задача сильной отделимости - это задача нахождения слоя наибольшей толщины (тг-слоя), разделяющего М и N. Сильная отделимость, по существу, эквивалентна задаче отыскания расстояния между М и 7/ в смысле метрики

р(Л'/,^) = 1гап{||л-->'| \х<=М,уеИ). (5)

Если х <еМ и являются а^-точками задачи (5), то есть р(М=\х-у\,

то слоем наибольшей толщины, разделяющим множества М и И, является Р~{х\хеР1г^Р1}, где и Р2 - полупространства, задаваемые линейными

неравенствами

(х-х,х-у) :£0 и (у-у,х-у)>0.

Таким образом, в краткой форме задачу сильной отделимости можно записать так: {?,ЯеАг§тт{|л:->'[ | х е М, .у е. (6)

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

Пусть задано однозначное отображение <р е ■ Под степенью <р'(х) отображения <р{х) будем понимать его последовательное применение я раз, то есть

<р'(х) = <р...<р( л).

1

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

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

Нт <р'(х0) = х.

Это означает, что для любого вещественного б> 0 существует целое неотрицательное число £ такое, что для всех $ >£ имеем Цх, —х\<е.

Определение 2. Пусть задано однозначное непрерывное отображение q> е FM. Под (р -проектированием (псевдопроектированием) точки jtgK' на множество М будем понимать отображение : R" ->А/, задаваемое соотношением

Tu М = üm /р'(х).

j-Mi

Точку будем называть псевдопроекцией точки х на множество М.

Пусть в контексте задачи сильной отделимости (6) заданы два однозначных непрерывных фейеровских отображения: <реFM, (C6F„. Используя операции ip- и ^-проектирования, можно построить следующий алгоритм g, решающий задачу сильной отделимости с использованием фейеровских отображений. Пусть задано произвольное начальное приближение vc0 бК". Зафиксируем положительное вещественное число е. Алгоритм у состоит из следующих шагов:

ШагО. А:= 0. Шаг I. xt+i:=KM(wk).

Шаг2- Л-41 ("О-

Шаг 3. wM := *Ук.

Шаг4. +

Шаг 5. Если min (|xt+1 -х„ ||} > г, перейти на шаг 1.

Шаг 6. Стоп.

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

Ах<Ь. (7)

Пусть у = [А,Ь] - информационный вектор, задающий все параметры системы (7),

уе R'™+"\ Обозначим через Му многогранник решений системы (7), определяемой информационным вектором у. Имеем Му с R". Справедлива следующая лемма.

Лемма 1. Пусть у еМ""+'" — информационный вектор, задающий устойчиво совместную систему неравенств

Ах<Ь .

Тогда существует некоторая окрестность V точки у, такая, что любая точка у е F также определяет устойчиво совместную систему неравенств

Ах<Ъ,

где у =

Определение 3. Пусть задано отображение ->R" двух аргументов

yeR"""' и jceR": Обозначим через <ру отображете из R" в I', которое получается из <р, путем фиксации аргумента у. Отображение (р является устойчиво фейеровским относительно точки ycW"'*"\ если <ру е . и существует окрестность V а R'"""" точки у такая, что для любого у е V имеем (р-у £ ¥м .

Теорема 1. Пусть отображение р:Г4"хГ ->К" двух аргументов уеК'""™ и ДеГ является непрерьганым поли у. Пусть система Ах<.Ь , определяемая информационным вектором у, является устойчиво совместной и <Ру б Тогда отображение <р является устойчиво фейеровским относительно точки у Доказательство теоре-

мы 1 опирается на лемму 1.

Алгоритм У оказывается эффективным для задач небольшой размерности. Однако

для больших задач («>500) время работы данного алгоритма может составлять сотни часов. В связи с этим в диссертационной работе был разработан новый масштабируемый алгоритм 6 построения псевдопроекции точки на многогранник с использованием фейеровских отображений, который допускает эффективное распараллеливание на большом количестве процессоров в системах с распределенной памятью. В основе масштабируемого алгоритма построения псевдопроекции на мпогогранник лежит метод разбиения пространства на подпространства. Для каждого подпространства организуется независимый фейеровский процесс. Через каждые 5 шагов результаты, полученные на подпространствах, соединяются в один вектор, который и является очередным приближением. Если расстояние между соседними приближениями меньше заданного положительного числа в, то полученный вектор принимается в качестве псевдопроекции. В противном случае вычисления продолжаются.

Для произвольного линейного подпространства РсК" через обозначим

ортогональную проекцию хеШ" на линейное подпространство Р. Везде далее линейное подпространство будем называть просто подпространством. Через р(Р,х) := тт||р-л|

будем обозначать расстояние от точки х до подпространства Р. Пусть линейное многообразие Ь получается из Р сдвигом на некоторый вектор =: 1Ь = Р+г. Через хь(х) обозначим ортогональную проекцию хеГ на линейное многообразие Ь:

Алгоритм 6. Пусть задано однозначное непрерывное М-фейсровское отображение <ре{К" ->К"}, Л/-выпукло и замкнуто. Зададим разбиение пространства К" в прямую сумму ортогональных подпространств: К" =Р,Ф...©РГ, П®, при Для каждого подпространства Р, (/ = 1,...,г) построим линейное многообразие Ь, следующим образом. Пусть х' е Агягшпр(Р,х). Положим 7 Здесь Р,1

обозначает ортогональное дополнение к подпространству Р,.. Построим линейное многообразие Ц путем сдвига подпространства на вектор 7:

Ь,=Р,+?'. (8)

Для каждого / е {!.....г) определим отображение <р, е {К" -> 1Ь,.}:

яМ^^И'цМ))- (9)

Зафиксируем некоторое натуральное число л и положительное вещественное число е. Положим ха = 0 б К".

Алгоритм & состоит из следующих шагов:

ШагО. £:=0.

Шаг 1.

Шаг2. +1.

Шаг 3. Если &с/м(хм)>е, перейти на шаг 1.

Шаг 4. Стоп.

На шаге 3 алгоритма вычисляется функция невязки <1и, которая определяет степень близости точки к многограннику М.

М = Хтах {(а,>х) ~ ьг °}

Работа алгоритма 6 для размерности п = 2 и .г = 2 схематично изображена на Рис. 1. Натуральное число .г является важным параметром алгоритма 65, влияющем на его масштабируемость. Увеличение .г ведет к росту ресурса параллелизма, заложенного в алгоритме ©. Однако, при выборе слишком большого значения для параметра £ последовательность точек порождаемых алгоритмом & на шаге 1, может не попасть на многогранник. В этом случае выход из итерационного процесса произойдет из-за невыполнения условия входящего в критерий завершения. Если это произошло, необходимо уменьшить значение £ и повторить вычислительный процесс.

Для того чтобы алгоритм 6 был корректным, необходимо и достаточно, чтобы последовательность точек {дг*}, порождаемых алгоритмом & на шаге 1, сходилась. Следующая теорема показывает, что каждое отображение (р, е {Ь, строящееся в алгоритме 6, является фейеровским относительно множества ЦпМ.

Теорема 2. Пусть задано замкнутое множество Л/ с: К" и однозначное Л/-фейеровское отображение <р е {К" —» К"}. Пусть Р — некоторое собственное линейное подпространство в пространстве К", Т= Р1 — ортогональное дополнение к подпростран-

ству Р. Пусть х g Arg minр(Р, jr). Представим х в виде суммы ортогональных векторов

хеМ

из подпространств Р и Т: х =xr(x) + nr(x). Обозначим z = ят(х) е Т. Построим линейное многообразие L путем сдвига подпространства Р на вектор z : L = P+z. Определим отображение <р._ е (L -> IL} следующим образом:

ft-M^L^K (*)))■ (Ю)

Положим

A/l = iLniМ. (И)

Тогда отображение фь является A/L -фсйеровским.

Справедлива следующая лемма.

Лемма 2. Пусть {.г*} — последовательность точек, порождаемых алгоритмом 6 на шаге 1:

1=1

В условиях алгоритма © определим ML = JL,¡глМ (i = 1,..., г). Положим

4 = n-L, W- =<Р. (4) •

Тогда

(X ) = ■< VAeZa.

Корректность алгоритма © обеспечивается следующей теоремой сходимости.

Теорема 3. Пусть — последовательность точек, порождаемых алгоритмом © на шаге 1:

i -1

Тогда ->Зс g R".

Доказательство теоремы 3 опирается на теорему 2 и лемму 2.

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

Сконструируем А/-фейеровское отображение следующим образом. Представим систему линейных неравенств, задающих многогранник М, в следующем виде:

Ax<b: {aj,x)-b1 <0, j = \,...,m, где aj ^ 0 для любого j. Тогда отображение вида

» maxf(a„.x\—¿„Ol

Нх)=х~Иал l\ i у Ч (12)

будет однозначным непрерывным Л/-фейеровским отображением для любой системы положительных коэффициентов {а, > о}, у = 1,...,т, таких, что ^а. =1 и коэффициентов

1

релаксации 0 < < 2. Применим к (12) технику разбиения на подпространства. Пусть п -размерность пространства задачи (6). Пусть задано г е N: г < п. Для простоты мы будем считать, что г всегда кратно п: п = г-1. Пусть задан ортонормированный базис пространства К":

{^,...,0. (13)

Определим

для / = 1,...,г. Очевидно, что Р,±Ру при ; Ф], и Р,®...©^ =К". Пусть х' б Ащгатр(Р(,*). Положим Т = пгк (х') е Р1 (/ = ],..., г).

Для 1-1,...,г определим отображения г,. е{М" ->К'} следующим образом. Пусть хеМ", (х,,...,хя) —координаты вектора х в ортонормированном базисе (13). Тогда

Г|(*) = (*1ч<н„.—(14) Обозначим т,\ Р, - ограничение т, на подпространство 1Р; с К". Произвольный *еР, будет иметь в базисе (13) координаты д: = (0,...,0,х1+(,.1);.....*,+(М„,0,...,0). Сопоставляя это с (14), видим, что отображение т, является взаимно-однозначным и для него существует обратное отображение т~]. В контексте формул (8) и (12) определим <р: е{Е" ->!<,.} следующим образом:

w-Z

¡-I

шах {(г, (а,), г, (х)\ + la , Т ) - Ь■ о}

\а„

(15)

Выполнение условий алгоритма © обеспечивается следующей теоремой.

Теорема 4. Отображения <pt (/" = !,..., г), определяемые формулой (15), удовлетворяют тождеству (9).

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

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

- Программа Random генерации случайных многогранников;

- Программа Sequence, реализующая последовательный алгоритм;

- Программа, реализующая параллельный алгоритм Simple;

- Программа, реализующая параллельный алгоритм Block.

Исходные тексты программ свободно доступны в Интернет по адресу http://life.susu.ru/discr/.

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

Программа Sequence, реализует последовательную версию алгоритма 5. При этом для построения псевдопроекции точки на многогранник могут использоваться фейеров-ские отображения двух типов. 1-й тип вычисляется по формуле (2), 2-й тип — по формуле (3). Номер типа отображения является параметром программы, задаваемым при ее запуске.

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

Программа Block реализует параллельный алгоритм. Параллельная структура программы организована по иерархическому принципу. Во главе иерархии стоит процесс-«мастер», координирующий работу остальных процессов по выполнению алгоритма 5. Процессу «мастер» подчиняются два независимых процесса-«бригадира». Первый про-цесс-«бригадир» вычисляет функцию Pi_Phi_M. Второй процесс-«бригадир» вычисляет функцию Pi_Psi_N. Каждому процессу-«бригадиру» подчинено по г независимых про-цессов-«рабочих». «Бригадир» делит полученный от «мастера» вектор на подвекторы и передает их «рабочим». Каждый «рабочий» выполняет s фейеровских итераций в своем подпространстве и передает полученный подвектор «бригадиру», который объединяет подвекторы, пришедшие от различных «рабочих», в единый вектор. «Бригадир» проверяет критерий завершения итерационного процесса. Если он не выполнен, то «бригадир» снова делит вектор на подвекторы и передает их «рабочим». Если критерий завершения имеет место, то полученный вектор принимается в качестве приближения псевдопроекции на многогранник и передается «мастеру». «Мастер», получив обе псевдопроекции от «бригадиров», считает очередную среднюю точку и проверяет для нее критерий завершения. Если он не выполнен, то мастер передает среднюю точку каждому из «бригадиров» для продолжения вычислений.

Все указанные процессы оформляются как процессы MPI, которые могут запускаться на любом количестве процессоров (процессорных ядер), не превосходящем (2г + 3) . В предельном случае, когда каждое подпространство имеет размерность 1, имеем г = п. Т.е. максимальная масштабируемость алгоритма равняется (2и+3) процессоров, где п - размерность задачи.

Важным параметром реализации является количество независимых итераций J, выполняемых процессом-«рабочим». Увеличивая s, можно повышать вычислительную нагрузку на те процессоры, на которых выполняются процессы-«рабочие». Это позволяет оптимизировать затраты на пересылку сообщений между «рабочими» и «бригадирами».

На вычислительном кластере «СКИФ-Урал» были проведены вычислительные эксперименты на случайных задачах Random и модельных масштабируемых задачах Model-n (Рис. 2). Для модельных задач можно легко аналитически вычислить точное значение толщины максимального разделяющего слоя. Они хорошо подходят для проверки корректности алгоритма, исследования его масштабируемости, и дают хорошую возможность для подбора оптимальных значений параметров алгоритма.

Многогранник М Многогранник N

х,-2х2 <0

х,-2х„ <0 jr, + 2Х2 < 20000

х, + 2х„ < 20000 -х, <0 -х2 ¿0

х,-2лг, ¿20000

х,-2ха ¿20000 х, + 2хг ¿40000

J£,+2*„ ¿40000 -х, ¿-20000 -х, ¿0

-х„ ¿ 0

Итерации алгоритма ff для задачи Model-3.

Рис. 2. Модельная задача Model-n.

С помощью программы Sequence была исследована последовательная реализация алгоритма У для фейеровских отображений двух типов на модельных задачах Model-n (Рис. 3 и Рис. 4) и случайных задачах Random (Рис. 5, Рис. 6). Первый тип вычислялся по

$ормуле (2), второй — по формуле (3). Эксперименты показали, что тип используемого ейеровского отображения может существенно влиять на скорость работы алгоритма.

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

д. 150

I 50

10 20 30 40 50 60 70 3 Размерность задачи л

Рис. 3. Зависимость количества итераций от размерности п для Model-n.

14000

— 1 тип 2 ту л

Размесность задом п

Рис. 4. Зависимость времени решения задачи Model-n от размерности п.

Размерность задачи г

Рис. 5. Зависимость количества итераций от размерности и для Random

Размерность задачи л

Рис. 6. Зависимость времени решения задач Random от размерности п.

1 2 4 8 12 16 20 24 28 32 36 Количество ядер

Рас. 7. Ускорение алгоритма Simple для задачи Model-n.

64 123 192 256 320 384 443 512 576 640 Количество ядер

Рис. 8. Ускорение для задачи Model-n.

Также в вычислительных экспериментах был исследован параллельный алгоритм Block, разработанный в рамках настоящего диссертационного исследования. Были исследованы различные параметры алгоритма Block и даны рекомендации по выбору их значений. Проведено исследование ускорение параллельного алгоритма Block (Рис. 8). Ускорение вычислялось по формуле a = tp/l6i, где Гн — время, затраченное на решение задачи

Model-n на 64 процессорных ядрах, t — время, затраченное на решение этой же задачи на р процессорных ядрах. Эксперименты проводились для трех размерностей: п = 1024; /7 = 1536 и п = 2048, при фиксированном s = 10000 и г = р. Для каждой размерности варьировалось количество процессорных ядер, используемых для решения задачи. Во всех трех случаях наблюдалось ускорение, близкое к линейному, вплоть до 512 процессорных ядер. Далее рост ускорения замедлялся. Однако при больших размерностях «заго-ризонталивание» кривой ускорения происходило позже.

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

Основные результаты диссертационной работы

На защиту выносятся следующие новые научные результаты.

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

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

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

Публикации по теме диссертации

Статьи, опубликованные в журналах из списка ВАК

1. Ершова A.B. Алгоритм разделения двух выпуклых непересекающихся многогранников с использованием фейеровских отображений // Системы управления и информационные технологии. 2009. № 1(35). С. 53-56.

2. Ершова A.B., Соколинская И.М. Параллельный алгоритм решения задачи сильной отделимости на основе фейеровских отображений // Вычислительные методы и программирование. 2011. Т. 12, № 2. С. 178-189.

3. Ершова A.B., Соколинская И.М. О сходимости масштабируемого алгоритма построения псевдопроекции на выпуклое замкнутое множество // Вестник ЮУрГУ. Серия "Математическое моделирование и программирование". 2011. № 37(254) вып 10

С. 12-21.

4. Ершова A.B., Соколинская И.М. Исследование устойчивости параллельного алгоритма решения задачи сильной отделимости на базе фейеровских отображений // Вестник ЮУрГУ. Серия "Математическое моделирование и программирование". 2012 № 18 (277), вып.12. С. 5-12.

Другие публикации

5. Ершова A.B. Задача разделения двух выпуклых многогранников с использованием фейеровских отображений // Алгоритмический анализ неустойчивых задач: Тезисы докладов Международной конференции (1-6 сентября 2008 г., г. Екатеринбург). Екатеринбург: Изд-во Урал, ун-та, 2008. С. 274-275.

6. Ершова A.B. Метод решения задачи сильной отделимости для многопроцессорных систем с массовым параллелизмом // Параллельные вычислительные технологии (ПаВТ'2010): Труды международной научной конференции (29 марта - 2 апреля 2010 г., г. Уфа). Челябинск: Издательский центр ЮУрГУ, 2010. С. 660-661.

7. Ершова A.B. Алгоритм решения задачи сильной отделимости на базе фейеровских отображений // Тезисы докладов XVIII Международной конференции «Математика. Экономика. Образование» (25 мая — 1 июня 2010 г., г. Новороссийск). Ростов-на-Дону: Изд-во СКНЦ ВШ ЮФУ, 2010. С. 131-132.

8. Ершова A.B., Соколинская И.М. Параллельный алгоритм разделения двух выпуклых непересекающихся многогранников с использованием фейеровских отображений // Научный сервис в сети Интернет: суперкомпьютерные центры и задачи: Труды международной научной конференции (20-25 сентября 2010 г., г. Новороссийск). М.: Изд-во МГУ, 2010. С. 242-248.

9. Ершова A.B. Параллельный метод решения задачи сильной отделимости на базе фейеровских отображений // Информационный бюллетень Ассоциации математического программирования. №12. Научное издание. (28 февраля - 4 марта 2011 г., г. Екатеринбург) Екатеринбург: УрО РАН, 2011. С. 85-86.

10. Ершова A.B., Соколинская И.М. Масштабируемый параллельный алгоритм построения псевдопроекций в задачах сильной отделимости // Научный сервис в сети Интернет: экзафлопеное будущее: Труды международной научной конференции (19-24 сентября 2011 г., г. Новороссийск). М.: Изд-во МГУ, 2011. С. 132-138.

, i

\v

Свидетельства о регистрации программ

11. Ершова A.B. Свидетельство Роспатента об официальной регистрации программы дая ЭВМ "Последовательный алгоритм решения задачи разделения двух выпуклых непересекающихся многогранников на базе фейеровских отображений" № 2010616104 от

16.09.2010.

12. Ершова A.B. Свидетельство Роспатента об официальной регистрации программы для ЭВМ "Генерация двух выпуклых непересекающихся многогранников" № 2010616105 от 16.09.2010.

13. Ершова A.B. Свидетельство Роспатента об официальной регистрации программы для ЭВМ "Параллельный алгоритм решения задачи разделения двух выпуклых непересекающихся многогранников на базе фейеровских отображений" № 2011610980 от

26.01.2011.

Работа выполнялась при поддержке Российского фонда фундаментальных исследований (проекты 09-01-00546а и 12-01-00452а).

Подписано в печать 28 апреля 2012 г. Формат 60x84 1/16. Бумага офсетная. Печать офсетная. Усл. печ. л. 1,0. Уч.-изд. л. 1,2. Тираж 100 экз.

Типография «Фотохудожник» 454091, г. Челябинск, ул. Свободы, 155/1

Введение.

Глава 1. Распознавание образов и фейсровские отображения.

1.1. Задача распознавания образов.

1.1.1. Классификация основных задач распознавания.

1.1.2. Отделимость непересекающихся mhoi огранников.

1.2. Итерационные методы фсйеровского типа.

1.3. Обзор методов решения задачи сильной отделимости.

1.3.1. Метод на основе операции проектирования.

1.3.2. Метод опорных векторов.

1.3.3. Метод с использованием теоремы об альтернативах.

1.4. Выводы по главе 1.

Глава 2. Метод псевдопроекций.

2.1. Формализация задачи сильной отделимости.

2.2. Метод последовательного проектирования.

2.3. Метод на базе фейеровских процессов.

2.4. Устойчивость алгоритма $.

2.5. Масштабируемый алгоритм 6 построения псевдопроекции.

2.6. 1еорема сходимости.

2.7. Выводы по главе 2.

Глава 3. Параллельные алгоритмы решения задачи сильной отделимости.

3.1. Параллельная реализация алгоритма £.

3.2. Параллельный алгоритм Simple.

3.3. Параллельный алгоритм Block.

3.4. Выводы по главе 3.

Глава 4. Программный комплекс и вычислительные эксперименты.

4.1. Структура программного комплекса.

4.1.1. Программа генерации случайных многогранников.

4.1.2. Программа, реализующая последовательный алгоритм.

4.1.3. Программа, реализующая параллельный алгоритм Simple.

4.1.4. Программа, реализующая параллельный алгоритм Block.

4.2. Вычислительные эксперименты.

4.3. Масштабируемая модельная задача Model-n.

4.4. Исследование последовательного алгоритма.

4.5. Исследование параллельного алгоритма Simple.

4.6. Исследование алгоритма Block.

4.7. Выводы по главе 4.

Актуальность темы

Создание вычислительных машин и связанное с этим ускоренное развитие математических теорий, в том числе математической кибернетики и дискретной математики позволило ставить и решать на ЭВМ новые задачи, до недавнего времени находившиеся исключительно в компетенции человека. Одной из таких фундаментальных задач является рассматриваемая в настоящей работе задача распознавания образов [8, 16, 17, 62]. В общем виде эта задача может быть сформулирована следующим образом: необходимо отнести предъявленный объект, определяемый некоторой совокупностью своих признаков, к одному из нескольких непересекающихся классов-образов. В том или ином виде данная задача решается человеком практически во всех сферах его деятельности.

Первые математические работы по данной задаче и реализованные на их основе технические системы появились во второй половине XX века и с тех пор активно используются во многих областях науки и техники, таких как геология, медицина, военное дело, социально-политические исследования и многое другое [1,4, 19, 44, 45, 57, 64]. В работах но теории распознавания образов рассматриваются различные подходы к этой задаче. В частности, распознающие системы могут делиться по тому, доступны ли системе примеры объектов, принадлежащих к тому или иному классу (такие системы называются системами распознавания с обучением) [8, 54] или нет (системы распознавания без обучения) [29, 451. Другим критерием, по которому можно классифицировать такие системы, является принцип построения решающего правила [60]. Исторически одними из первых и интуитивно наиболее понятных распознающих систем являлись линейные распознающие системы [60]. В таких системах каждый объект представляется как точка в некотором многомерном пространстве, а решающее правило представлястся в виде совокупности поверхностей, отделяющих области этого пространства, соответствующие различным классам. Простейшим случаем такой разделяющей поверхности является гиперплоскость. Более строгим случаем разделения выпуклых объектов является разделение слоем. Как раз вопрос нахождения слоя наибольшей толщины, разделяющего два выпуклых непересекающихся объекта, рассматривает задача сильной отделимости.

Задача сильной отделимости имеет большое значение теоретического и прикладного характера в распознавании образов, включающем задачи дискриминации, классификации и др. Хорошо известен итерационный метод решения задачи сильной отделимости, использующий операцию проектирования. Однако на практике применение этого метода существенно ограничивается тем, что далеко не всегда удастся построить конструктивную формулу для вычисления проекции точки па выпуклое множество. Поэтому целесообразно заменить операцию проектирования последовательностью фейеровских отображений [27]. Указанный метод был описан в работе [25].

Алгоритмы разделения выпуклых многогранников на базе фейеровских отображений обладают тем преимуществом по сравнению с другими известными методами, что они применимы к нестационарным задачам, то есть к задачам, в которых исходные данные могут меняться в процессе решения задачи. Примерами таких нестационарных задач являются, например, задача о портфеле цепных бумаг, задача о спам-филырс и задачи классификации в метеорологии. При решении задачи о портфеле ценных бумаг [82] является важным вопрос о выборе ценной бумаги из их многообразия при формировании портфеля [83]. Проблему выбора можно решить, условно разделив все ценные бумаги на две части: перспективные и неперспективные. Каждая ценная бумага представляется в виде многомерной точки, координаты которой - это параметрическое описание конкретной бумаги [6, 85]. Количество параметров определяет размерность пространства решаемой задачи. Эксперт строит параметризованную модель [59], представляющую собой две системы неравенств. Часть коэффициентов в неравенствах являются параметрами, меняющимися во времени. В качестве примеров таких параметров можно указать средний оборот торгов, енрзд между ценами спроса и предложения и др. В результате мы приходим к нестационарной задаче сильной отделимости. Построив слой наибольшей толщины, разделяющий два многогранника, мы получаем инструмент, позволяющий автоматически разделять ценные бумаги на перспективные и неперспективные.

В задаче о спам-фильтре [78, 92] мы должны для каждого электронного письма определить, является данное письмо «спамом», или нет. Для этого также вводится система метрик и строится параметризованная модель [81, 90], в которой первая система неравенств задает множество точек-писем, определяемых как спам, вторая система - множество точек-писем, определяемых как не спам. Построив слой наибольшей толщины, разделяющий два многогранника, мы получаем инструмент, позволяющий автоматически разделять письма на «хорошие» и «плохие». Когда приходит новое письмо, вычисляются характеристики этого письма и получается точка в рассматриваемом пространстве. Если данная точка попадает в «плохое» полупространство, мы делаем предположение, что это спам; если в «хорошее» - не спам. Если точка попадает внутрь слоя, письмо доставляется пользователю с пометкой «возможно, снам».

Задачи классификации эволюционирующих систем характерны и для метеорологии. Приведем несколько примеров. Одной из таких задач является задача определения морфологии и генезиса облаков и разделения их на классы, например, кучевых и слоистообразных облаков [58, 79]. Для этого на основе критериальных порогов, таких как температура верхней границы, альбедо, пространственная однородность и др., строится параметризованная модель в виде двух систем линейных неравенств, описывающих облака различных классов. Находя слой наибольшей толщины между многогранниками, задаваемыми этими системами, мы можем в режиме реального времени определять тип облачности и вероятность выпадения осадков. В радиолокационной метеорологии [66, 87, 88] традиционным является вопрос о фазовом состоянии и форме облачных частиц - капли, ледяные кристаллы различных форм, смешанные формы, их агрегаты; и связанный с этим вопрос о типе и интенсивности выпадающих осадков - дождь, снег, мокрый снег, снежная крупа, ледяные иглы, град и др. Для решения задачи на основе данным об отражаемости, дифференциальной отражаемости, коэффициентов деполяризации и др. вводится система метрик и строится параметризованная модель, в которой одна система неравенств задает множество точек одного типа (например, дождь), а вторая система неравенств задает множество точек другого типа (например, снег). Построив слой наибольшей толщины, разделяющий два многогранника, мы получаем инструмент, позволяющий автоматически прогнозировать тип осадков. Задача о классификации мезомасштабных конвективных систем по интенсивности и степени организации рассмотрена в работах [1,2]. В отличие от предыдущих задач, имеющих дело с одним или несколькими элементами поля облачности и осадков размерами от нескольких сотен метров до 1 -2 км, здесь рассматривается структура поля радиолокационной отражаемости всей мезомасштаб-ной системы с размерами более 300 км. Алгоритм классификации мезомас-штабных систем [1] в своей основе подобен рассмотренным выше: в определенной стадии жизненного цикла системы выделяется наиболее интенсивные элементы, а затем по их характеру системы делятся на конвективные и слоистообразные, далее по структуре поля на линейные и нелинейные; конвективные в свою очередь подразделяются на умеренные и более мощные шторма. Для детализации набора опасных явлений, обусловленных эволюцией индивидуальной мезомасштабной системы (ливни, грозы, град, шквалы и смерчи), число неравенств может быть расширено за счет введения кинематических и эволюционных характеристик [2].

При решении практических задач распознавания образов часто встречаются задачи с большим количеством переменных и ограничений. Размер типичной средней задачи может составлять 20 ООО переменных и 5 ООО ограничений [74]. В отдельных случаях количество переменных может превышать 100 ООО, а количество ограничений - 20 ООО. Подобные задачи при решении требуют значительных вычислительных мощностей. В связи с этим возникает необходимость разработки параллельного алгоритма разделения выпуклых многогранников с помощью фейсровских отображений, допускающего эффективную реализацию па многопроцессорных системах с массовым параллелизмом.

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

Цель и задачи исследования

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

1. Описать общий подход к решению задачи сильной отделимости двух выпуклых многогранников на основе последовательных проектирований.

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

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

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

Методы исследования

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

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

Научная новизна работы заключается в следующем:

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

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

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

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

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

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

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

Диссертация состоит из введения, четырех глав, заключения и библиографии. Объем диссертации составляет 97 страниц, объем библиографии - 92 наименования.

Основные результаты диссертационной работы

На защиту выносятся следующие новые научные результаты:

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

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

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

Публикации по теме диссертации в журналах из списка ВАК

1. Ершова A.B. Алгоритм разделения двух выпуклых непересекающихся многогранников с использованием фейеровских отображений // Системы управления и информационные технологии. 2009. № 1(35). С. 53-56.

2. Ершова A.B., Соколинская И.М. Параллельный алгоритм решения задачи сильной отделимости на основе фейеровских отображений // Вычислительные методы и программирование. 2011. Т. 12, №2. С. 178-189.

3. Ершова A.B., Соколинская И.М. О сходимости масштабируемого алгоритма построения псевдопроекции на выпуклое замкнутое множество // Вестник ЮУрГУ. Серия «Математическое моделирование и программирование». 2011. № 37(254), вып. 10. С. 12-21.

4. Ершова A.B., Соколинская И.М. Исследование устойчивости параллельного алгоритма решения задачи сильной отделимости на базе фейеровских отображений // Вестник ЮУрГУ. Серия «Математическое моделирование и программирование». 2012. № 18(277), вып. 12. С. 5-12.

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

5. Ершова A.B., Соколинская И.М. Масштабируемый параллельный алгоритм построения псевдопроекций в задачах сильной отделимости // Научный сервис в сети Интернет: экзафлопсное будущее: Труды международной научной конференции (19-24 сентября 2011 г., г. Новороссийск). М.: Изд-во МГУ, 2011. С. 132-138.

6. Ершова A.B. Метод решения задачи сильной отделимости для многопроцессорных систем с массовым параллелизмом // Параллельные вычислительные технологии (ПаВТ'2010): Труды международной научной конференции (29 марта - 2 апреля 2010 г., г. Уфа). Челябинск: Издательский центр ЮУрГУ, 2010. С. 660-661.

7. Ершова A.B., Соколинская И.М. Параллельный алгоритм разделения двух выпуклых непересекающихся многогранников с использованием фейеровских отображений // Научный сервис в сети Интернет: суперкомпьютерные центры и задачи: Груды международной научной конференции (20-25 сентября 2010 г., г. Новороссийск). М.: Изд-во МГУ, 2010. С. 242-248.

Тезисы докладов конференций

8. Ершова A.B. Задача разделения двух выпуклых многогранников с использованием фейеровских отображений // Алгоритмический анализ неустойчивых задач: Тезисы докладов Международной конференции (1-6 сентября 2008 г., г. Екатеринбург). Екатеринбург: Изд-во Урал, унта, 2008. С. 274-275.

9. Ершова A.B. Алгоритм решения задачи сильной отделимости на базе фейеровских отображений // Тезисы докладов XVIII Международной конференции «Математика. Экономика. Образование» (25 мая - 1 июня 2010 г., г. Новороссийск). Ростов-на-Дону: Изд-во СКНЦ ВШ ЮФУ, 2010. С. 131-132.

10. Ершова A.B. Параллельный метод решения задачи сильной отделимости на базе фейеровских отображений // Информационный бюллетень Ассоциации математического программирования. №12. Научное издание. (28 февраля - 4 марта 2011 г., г. Екатеринбург) Екатеринбург: УрО РАН, 2011. С. 85-86.

Свидетельства о регистрации программ

11. Ершова A.B. Свидетельство Роспатента об официальной регистрации программы для ЭВМ "Последовательный алгоритм решения задачи разделения двух выпуклых непересекающихся многогранников на базе фейеровских отображений" № 2010616104 от 16.09.2010.

12. Ершова A.B. Свидетельство Роспатента об официальной регистрации программы для ЭВМ "Генерация двух выпуклых непересекающихся многогранников" № 2010616105 от 16.09.2010.

13. Ершова A.B. Свидетельство Роспатента об официальной регистрации программы для ЭВМ "Параллельный алгоритм решения задачи разделения двух выпуклых непересекающихся многогранников на базе фей-еровских отображений" № 2011610980 от 26.01.2011.

Апробация работы

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

- на Международной научной конференции «Параллельные вычислительные технологии (Г1аВТ'2012)» (26-30 марта 2012 г., г. Новосибирск);

- на Международной научной конференции «Научный сервис в сети Интернет: экзафлопсное будущее» (19-24 сентября 2011 г., г. Новороссийск);

- на XIV Всероссийской конференции "Математическое программирование и приложения" (28 февраля - 4 марта 2011 г., г. Екатеринбург);

- на Международной научной конференции «Параллельные вычислительные технологии (ПаВТ'2010)» (29 марта - 2 апреля 2010 г., г. Уфа);

- на XVIII Международной конференции «Математика. Экономика. Образование» (25 мая - 1 июня 2010 г., г. Новороссийск);

- на Международной научной конференции «Научный сервис в сети Интернет: суперкомпьютерные центры и задачи» (20-25 сентября 2010 г., г. Новороссийск);

- на Международной конференции «Алгоритмический анализ неустойчивых задач» (1-6 сентября 2008 г., г. Екатеринбург).

ЗАКЛЮЧЕНИЕ

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

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

1. Абдуллаев С.М., Желнгш A.A., Ленская ОАО. Жизненный цикл мезо-маештабных конвективных систем // Метеорология и гидрология. 2009. №5. С. 34-45.

2. Абдуллаев С.М., Желнин A.A., Ленская О.Ю. Организация мезомас-штабных конвективных систем в центральной России// Метеорология и гидрология. 2012. №1. С.20-32.

3. Алексеев М.А., Залкинд М.С., Кушнарев В.М. Решение человеком задачи выбора при вероятностном подкреплении двигательных реакций // Биологические аспекты кибернетики. М.: Изд-во АН СССР, 1962.1. С. 198-209.

4. Бархатов В.А. Распознавание образов класса, заданного параметрически // Дефектоскопия. 2009. № 2. С. 3-17.

5. Бердникова Е.А., Ерёмин И.И., Попов Л.Д. Распределенные фейеров-ские процессы для систем линейных неравенств и задач линейного программирования // Автоматика и телемеханика. 2004. № 2. С. 16-32.

6. Боровкова В.А. Рынок ценных бумаг. СПб.: Питер, 2005. 316 с.

7. Брэгман Л.М. Нахождение общей точки выпуклых множеств методом последовательного проектирования // ДА11 СССР. 1965. Т. 162, № 3. С. 487-490.

8. Вапник В.Н., Червонежнс А.Я. Теория распознавания образов. М.: Наука, 1974.416 с.

9. Васильев Ф.П., Иваницкий А.Ю. Линейное программирование. М.: Факториал, 2003. 352 с.

10. Васин В.В., Еремин И.И. Операторы и итерационные процессы фейе-ровского типа. Теория и приложения. Екатеринбург: УрО РАН, 2005. 210с.

11. Воеводин Вл.В., Капитонова А.П. Методы описания и классификации архитектур вычислительных систем. М: Изд-во МГУ, 1994. 103 с.

12. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. СПб: БХВ-Петербург, 2002. 600 с.

13. Воронцов КВ. Лекции по методу опорных векторов. ВЦ РАН, Москва. URL:http://www.ccas.ru/voron/download/SVM.pdf (дата обращения: 22.07.11).

14. Голиков А.И., Евтушенко Ю.Г. Теоремы об альтернативах и их применение в численных методах // Журн. вычисл. матем. и матем. физ. 2003. Т. 43, №3. С. 354-375.

15. Голиков А.И., Евтушенко Ю.Г., Кетабчи С. О семействах гиперплоскостей, разделяющих полиэдры // Журн. вычисл. матем. и матем. физ. 2005. Т. 45, №2. С. 238-253.

16. Горелик А.Л., Гуревич И.Б., Скрипкин В.А. Современное состояние проблемы распознавания: Некоторые аспекты. М.: Радио и связь, 1985. 161 с.

17. Горелик A.JI., Скрипкин В.А. Методы распознавания. М.: Высшая школа, 2004. 264 с.

18. Гурин Л.Г., Поляк Б.Т., Райк Э.В. Методы проекций для отыскания общей точки выпуклых множеств // Журн. вычисл. матем. и матем. физ. 1967. Т. 7, №6. С. 1212-1228.

19. Елкин Е.А., Елкина В.Н., Загоруйко Н.Г. О возможности применения методов распознавания в палеонтологии // Геология и геофизика. 1967. № 9. С. 75-78.

20. Еремин И.И. Обобщение релаксационного метода Моцкина-Агмона // Успехи мат. наук. 1965. Т. 20, вып. 2. С. 183-187.

21. Еремин И.И. О некоторых итерационных методах в выпуклом программировании // Экономика и мат. методы. 1966. Т. 2, № 6. С. 870-886.

22. Еремин И.И. О системах неравенств с выпуклыми функциями в левых частях // Изв. АН СССР. Сер. мат. 1966. Т. 30, вып. 2. С. 265-278.

23. Еремин И.И. Методы фейеровских приближений в выпуклом программировании // Мат. заметки. 1968. Т. 3, вып. 2. С. 217-234.

24. Еремин И.И. Теория линейной оптимизации. Екатеринбург: Изд-во «Екатеринбург», 1999. 312 с.

25. Еремин И.И. Фейеровские методы сильной отделимости выпуклых полиэдральных множеств // Известия вузов. Сер. Математика. 2006. № 12. С.33-43.

26. Еремин И.И. Фейеровские методы для задач выпуклой и линейной оптимизации. Челябинск: Издательский центр ЮУрГУ, 2009. 199 с.

27. Еремин И.И., Мазуров Вл.Д. Нестационарные процессы математического программирования. М.: Наука, 1979. 288 с.

28. Еремин И.И., Мазуров Вл.Д. Вопросы оптимизации и распознавания образов. Свердловск: Сред.-Урал. кн. изд-во, 1979. 63 с.

29. Еремин И.И., Мазуров Вл.Д., Скарин В.Д., Хачай МАО. Математические методы в экономике. Екатеринбург: У-Фактория, 2000. 280 с.

30. Еремин И.И., Попов Л.Д. Замкнутые фейеровские циклы для несовместных систем выпуклых неравенств // Известия высших учебных заведений. Математика. 2008. № 1. С. 11-19.

31. Ершова A.B. Алгоритм разделения двух выпуклых непересекающихся многогранников с использованием фейеровских отображений // Системы управления и информационные технологии. 2009. № 1(35). С. 53-56.

32. Ершова A.B., Соколинская И.М. Параллельный алгоритм решения задачи сильной отделимости на основе фейеровских отображений // Вычислительные методы и программирование. 2011. Т. 12, №2. С. 178-189.

33. Ершова A.B., Соколинская И.М. О сходимости масштабируемого алгоритма построения псевдопроекции на выпуклое замкнутое множество // Вестник ЮУрГУ. Серия "Математическое моделирование и программирование". 2011. № 37(254), вып. 10. С. 12-21.

34. Ершова A.B. Свидетельство Роспатента об официальной регистрации программы для ЭВМ "Последовательный алгоритм решения задачи разделения двух выпуклых непересекающихся многогранников на базе фейеровских отображений" № 2010616104 от 16.09.2010.

35. Ершова A.B. Свидетельство Роспатента об официальной регистрации программы для ЭВМ "Генерация двух выпуклых непересекающихся многогранников" № 2010616105 от 16.09.2010.

36. Ершова A.B. Свидетельство Роспатента об официальной регистрации программы для ЭВМ "Параллельный алгоритм решения задачи разделения двух выпуклых непересекающихся многогранников на базе фей-еровских отображений" № 2011610980 от 26.01.2011.

37. Журавлев Ю.И., Рязанов В.В., Сенько О.В. Распознавание. Математические методы. Программная система. Практические применения. М.: ФАЗИС, 2006. 176 с.

38. Загоруйко Н.Г. Методы распознавания и их применение. М.: Сов. радио, 1972. 206 с.

39. Корнеев В.В. Параллельные вычислительные системы. М: «Нолидж», 1999.320 с.

40. Мазуров Вл.Д. Комитеты систем неравенств и задача распознавания // Кибернетика. 1971. № 3. С. 140-146.

41. Мазуров Вл.Д. Дискриминангный анализ при математическом моделировании плохо формализуемых ситуаций // Нелинейная оптимизация и приложения в планировании. Свердловск: УНЦ АН СССР, 1973.1. С. 26-35.

42. Мазуров Вл.Д. Комитеты в нечетких задачах // Методы оптимизации и распознавания образов в задачах планирования. Свердловск: УНЦ АН СССР, 1980. С. 44-65.

43. Мазуров Вл.Д. Метод комитетов в задачах оптимизации и классификации. М.: Наука, 1990. 248 с.

44. Мерзляков Ю.И. Об одном релаксационном методе решения систем линейных неравенств // Журн. вычисл. матем. и матем. физ. 1962. Т. 2,3. С. 482-487.

45. Мерков А.Б. Распознавание образов. Введение в методы статистического обучения. М.: Изд-во Едигориал УРСС, 2011. 256 с.

46. Ншьсон И. Обучающиеся машины. М.: Мир, 1967. 180 с.

47. Оленев H.H. Основы параллельного программирования в системе MPI. M.: Изд-во ВЦ РАН, 2005. 90 с.

48. Розин Б.Б. Теория распознавания образов в экономических исследованиях. М.: Статистика, 1973. 224 с.

49. Рытое С.М. О методе фазового контраста в микроскопии // Успехи физических наук. 1950. Т. 41, № 4. С. 425.

50. Синъкевич A.A., Степаненко В.Д., Довгалюк Ю.А. 50 лет отделу физики облаков ГГО // Вопросы физики облаков: Сборник избранных статей. СПб: Астерион, 2008. 513 с.

51. Тертытный С.А. Рынок ценных бумаг и методы его анализа. СПб.: Питер, 2004. 161 с.

52. Ту Дж., Гонсалес Р. Принципы распознавания образов: Пер. с англ. Под ред. Ю.И. Журавлёва. М.: Мир, 1978. 411с.

53. Федотов И.Е. Некоторые приемы параллельного программирования / ГОУ ВПО «Московский государственный институт радиотехники, электроники и автоматики» М., 2008. 188 с.

54. Фукунага К. Введение в статистическую теорию распознавания образов. М.: Наука, 1979.368 с.

55. Черников С.Н. Линейные неравенства. М.: Изд-во "Паука", 1968. 488 с.

56. Чистович Л.А. Психоакустика и вопросы теории восприятия речи. Распознавание слуховых образов. Под ред. Загоруйко П.Г. и Волошина ГЛ. Новосибирск: Изд-во «Наука». 1966. С. 68-168.

57. Agmon S. The relaxation method for linear inequalities // Canad. J. Math. 1954. Vol.6, No. 3. P. 382-393.

58. Atlas D. Radar in Meteorology // Radar in meteorology: Bataan Memorial and 40-th Anniversary Radar Meteorology Conference. American Meteorogical Society. Boston. 1990. 806 p.

59. Burges C.A. Tutorial on Support Vector Machines for Pattern Recognition // Data Mining and Knowledge Discovery. 1998. Vol. 2, No. 2. P. 121-167.

60. Burges C.J.C. A Tutorial on Support Vector Machines for Pattern Recognition//Data Mining and Knowledge Discovery. 1998. Vol. 2, No. 2. P. 121167.

61. Boser В., Guyon I., Vapnik V. A training algorithm for optimal margin classifiers // In Proceedings of the 5th Annual ACM Workshop on on Computational Learning Theory. 1992. P. 144-152.

62. Cortes C., Vapnik V. Support Vector Networks // Machine Learning. 1995. Vol. 20, No. 3. P. 273-297.

63. Cristianini N., Shawe-Taylor J. An Introduction to Support Vector Machines (and other kernel-based learning methods) // Cambridge University Press. 2000.

64. Dongarra J.J., Otto S. IV., Snir M, Walker D. A message passing standard for MPP and workstations // Communications of the ACM. 1996. Vol. 39, No. 7. P. 84-90.

65. Flynn M.J., Rudd K. W. Parallel architectures // ACM Computing Surveys, 1996. Vol.28, No. l.P. 67-70.

66. Forrest J.J.H., Tomlin J.A. Implementing the simplex method for the optimization subroutine library // IBM Systems Journal. 1992. Vol. 31, No. 1. P. 11-25.

67. Gose T., Johnsonbaugh R., Jost S. Pattern Recognition and Image Analysis. Prentice Hall, 1996. 483 p.

68. Gropp W., Huss-Lederman S., Lumsdaine A., Lusk E., Nitzberg B., Saphir W., Snir M. MPI The Complete Reference: Volume 2, The MPI Extensions. MIT Press, 1998.

69. Guzella T.S., Caminhas W.M A review of machine learning approaches to Spam filtering // Expert Systems with Applications. 2009. Vol. 36, Iss. 7. P. 10206-10222.

70. Kidder S.Q, Vonder Haar T.H. Satellite meteorology. Academic Press. London. 1995. 466 p.

71. Lampert A., Dale R., Paris C. Segmenting Email Message Text into Zones // Proceedings of the 2009 Conference on Empirical Methods in Natural Language Processing: ACL and AFNLP, 2009. P. 919-928.

72. Markowitz H. Portfolio selection // Journal of Finance. 1952. Vol.7, No. 1. P. 77-91.

73. Merton R.C. Lifetime portfolio selection under uncertainty: The continuous-time case // Review of Economics and Statistics. 1969. Vol. 51. P. 247-257.

74. Motzkin T.S., Shoenberg I. The relaxation method for linear inequalities // Canad. J. Math. 1954. Vol. 6, No. 3. P. 393-404.

75. Nawrocki D. The characteristics of portfolios selected by n-degree lower partial moment // International Review of Financial Analysis. 1992. Vol. 1. P. 195-209.

76. Quinn M.J. Parallel Computing: Theory and Practice. McGraw-Hill Companies. 1993.446 p.

77. Ryzhkov A. V., Terry J.S., Donald W.B., Pamela LAI. Scoff E.G., Dusan S.Z. Polarimetric Rainfall Measurements and Hydrometeor Classification // American Meteorological Society. 2005. P. 809-824.

78. Ryzhkov A. V., Zmic D.S. Discrimination between rain and snow with a polarimetric radar// J. Appl. Meteor. 1998. No. 37. P. 1228-1240.

79. Snir M.,Ofto S., Huss-Lederman S., Walker D., Dongarra J. MPI The Complete Reference. Volume 1, The MPI Core. 2nd Ed. - MIT Press, 1999.

80. Tretyakov K. Machine Learning Techniques in Spam Filtering // Data Mining Problem-oriented Seminar, MTAT.03.177. 2004. P. 60-79.

81. Vapnik V., Lerner A.J. Generalized portrait method for pattern recognition // Automation and Remote Control. 1963. Vol. 24, No. 6. P. 774-780.

82. Zhang L, Zhu J., Yao T. An Evaluation of Statistical Spam Filtering Techniques // Transactions on Asian Language Information Processing. 2004. Vol. 3, No. 4. P. 243-269.