Другие журналы

научное издание МГТУ им. Н.Э. Баумана

НАУКА и ОБРАЗОВАНИЕ

Издатель ФГБОУ ВПО "МГТУ им. Н.Э. Баумана". Эл № ФС 77 - 48211.  ISSN 1994-0408

О параллельных алгоритмах геометрической интерпретации

#1 январь 2005

Е

Е. В. Гливенко, д-р техн. наук, проф., ГАНГ,

В. Л. Демьянов, аспирант МГТУ им. Н. Э. Баумана

 

О параллельных алгоритмах геометрической интерпретации

 

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

 

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

Суть метода геометрической интерпретации состоит в применении к чисто вычислительным задачам методов современной геометрии. В работе [5] эти методы применяются к задаче решения систем линейных алгебраических уравнений. Не исключается возможность применения геометрической интерпретации с целью создания вычислительных алгоритмов для решения и других за­дач, например решения систем нелинейных уравнений. Такой подход, оказывается, позволяет не только создавать методы, обладающие естественным параллелизмом, но и разрабатывать интерактивные процедуры для персональных компьютеров с использованием теории принятия решений. Это, в свою очередь, позволяет реализовывать приближенные методы, что оказывается важным при работе с неточными исходными данными.

Рассмотрим систему линейных алгебраических уравнений

Ax = b                                                                         (1)

В работе [5] предложена геометрическая интерпретация задачи решения такой системы. Эта интерпретация основана на использовании свойств степени симплициальных отображений [6], [7]. Система (1) представляется в виде

x = (A + E) xb                                                         (2)

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

y = (A + E) xb                                                         (3)

Такая запись представляет преобразование в n-мерном пространстве, неподвижная точка которого соответствует решению системы (1).

Поставим задачу о приближенном решении системы следующим образом. Пусть задан n-мерный шар в пространстве x-ов. Требуется ответить на вопрос содержится ли решение системы внутри заданного шара. Вместо шара можно рассматривать любое выпуклое множество, например n-мерный симплекс. Методы современной геометрии [5] позволяют свести поставленную задачу к вопросу о том, лежат ли в одном полупространстве n-мерного пространства векторы a1, а2, ..., an, an+1, исходящие из начала координат и по длине равные единице.

В данной работе предлагается методика получения ответа на этот вопрос. Обсудим эту методику, иллюстрируя ее на рисунках, относящихся к случаю n = 2. На рис. 1, а, б предложены варианты расположения векторов на плоскости (a1, a2, a3) и (b1, b2, b3). На рис. 1, а векторы лежат в одной полуплоскости (в одном полупространстве). Разделяющая прямая l делит плоскость на две полуплоскости таким образом, что векторы лежат в одной из них. На рис. 1, б векторы не лежат в одной полуплоскости.

Рис. 1

Рассматриваемые векторы задаются своими координатами  и , которые получаются из параметров системы (1) рядом простых выкладок [5].

В основе методики лежит так называемая "минимаксная таблица", которая строится следующим образом

 

a1

a2

a3

max

 

 

b1

b2

b3

max

x1

0

 

 

x1

0

-x1

0

0

 

 

-x1

0

0

x2

0

 

 

x2

0

0

-x2

0

0

 

 

-x2

0

min

 

 

min

Столбцы таблицы соответствуют векторам ai и bi (i = 1, 2, 3). Строки распределены следующим образом. Строка x1 соответствует вектору единичной длины, направленному вдоль положительного направления оси x1 т. е. вектору с координатами (1, 0). Строка — x1 соответствует вектору единичной длины, направленному вдоль отрицательного направления оси x1; т. е. вектору с координатами (-1, 0). Назначение строк x2 и -x2 определяется аналогично.

Минимаксная таблица заполняется следующим образом. В ячейку, находящуюся на пересечении столбца a1 и строки x1 записывается скалярное произведение вектора a1 на вектор, соответствующий x1. Но только в том случае, если это скалярное произведение больше нуля. Если скалярное произведение меньше либо равно нулю, в ячейку записывается ноль. Таким образом заполняются все остальные ячейки таблицы. Теперь вдоль каждой строки находим максимум и записываем их в столбец максимумов (max). Затем среди значений из столбца максимумов находим минимальное значение и записываем в нижнюю правую ячейку. Это и есть минимаксное значение таблицы. Случай, когда минимакс равен нулю, соответствует варианту, когда можно провести разделяющую прямую, которая будет совпадать с одной из координатных осей.

Следующий этап методики заключается в так называемом "размножении" векторов. Рассмотрим рис. 2, а, б, который получается из рис. 1, а, б добавлением векторов cij в случае, показанном на рис. 2, a, dij случае, приведенном на рис. 2, б. Эти векторы строят следующим образом:

                              (4)

Рис. 2.

Теперь рассмотрим три типа таблиц.

Первый тип — это таблицы, построенные по системам векторов ai(bi) (см. таблицу).

Второй тип — таблицы, построенные по векторам cij(dij).

Третий тип — таблицы, построенные по совокупностям ai и cij (bi и dij).

Для второго и третьего типов принцип построения таблиц тот же, что и для первого типа.

Был проведен вычислительный эксперимент. При различных n (n — размерность) задавались системы с помощью датчиков случайных чисел. Также случайным образом выбирались пары n-мерных правильных симплексов. Первый симплекс в этой паре содержал решение соответствующего уравнения (1), т. е. неподвижную точку преобразования (3). Второй симплекс выбирался так, чтобы неподвижная точка находилась за его пределами. Для каждого уравнения и соответствующего симплекса строились векторы ai и bi. Векторы ai соответствовали случаю, когда неподвижная точка — решение — лежит вне симплекса, а векторы bi — случаю, когда решение лежит внутри симплекса.

Построение векторов выполняется следующим образом. Подставляются координаты вершин симплекса в правую часть преобразования (3). Таким образом, каждая вершина симплекса переходит в некоторую другую точку. Далее рассматривается вектор, соединяющий исходную точку с ее образом. Этот вектор переносится в начало координат и нормируется. Таким образом получаем векторы ai и bi. Векторы cij и dij строим согласно описанной выше процедуре.

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

Наблюдалась следующая картина.

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

2. Минимаксные значения, вычисленные по таблицам второго типа, т. е. по векторам cij, были меньше, чем минимаксные значения, указанные в п. 1.

3. Минимаксные значения, вычисленные по таблицам второго и третьего типов для векторов cij, а также по совокупностям bi и dij, были больше, чем минимаксные значения для таблиц первого типа, т. е. для векторов bi.

Можно было бы попытаться на основании этих признаков классифицировать ситуации, т. е. выделить случай, когда решение лежит внутри симплекса. На самом деле это сделать нельзя. В нескольких примерах (при n ≥ 3) наблюдалось нарушение признака 2. Можно сказать, что эти случаи являются специальными. Так как их появление происходит очень редко (один случай на несколько десятков экспериментов). Замечено, что это нарушение может наблюдаться только в том случае, когда неподвижная точка лежит вблизи одной из граней симплекса и за его пределами (расстояние от неподвижной точки до ближайшей грани симплекса имеет порядок 10-3). Также замечено, что появление таких нарушений не зависит от длины ребра симплекса (т. е. от его размера). Более того, это явление наблюдается только для определенных систем (1). Условно можно назвать такие системы "аномальными". Системы, в которых не наблюдалось нарушение пункта 2, назовем "нормальными". Оказалось, что у "аномальных" систем очень маленькая нормированная величина detA (т. е. значение detA/||A||) по сравнению с "нормальными" системами. Это значит, что у "аномальных" систем более сильная степень линейной зависимости между строками матрицы А. Поэтому для "аномальных" систем векторы, полученные в результате преобразования (3), "стремятся" к переходу из n-мерного пространства в (n - 1)-мерное. При n = 2 эти векторы "почти коллинеарны", а при n = 3 векторы "почти компланарны". Подобный случай проиллюстрирован рис. 3 и 4. Векторы a1, a2, a3, a4 лежат в одном полупространстве. Показана разделяющая плоскость γ. Векторы ai расположены так, что соответствующие им векторы cij будут иметь проекции на оси координат больше, чем у ai. В результате минимакс, полученный из таблицы второго типа, может увеличиться по сравнению с минимаксом из таблицы первого типа.

Рис.3.

Рис.4.

 

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

На основании заполненной минимаксной таблицы строят две функции от n переменных по числу измерений. А именно: первая функция φ1 (xi) (i = 1, 2, ..., n) представляет собой максимальные значения из последнего столбца таблицы, соответствующие положительным строкам, т. е. +xi. Вторая функция φ2(xi) (i = 1, 2, ..., n) соответствует -xi (рис. 5).

Рис.5.

Результирующая функция φ3(xi) = |φ2(хi) – φ1(xi)| является индикатором. Строя функции φ3(xi) для описанных выше трех типов таблиц, мы наблюдаем, что они имеют существенные различия для решений уравнений, лежащих внутри симплекса, и соответственно за его пределами.

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

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

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

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

 

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

1. Карцев М. А. Выступление в 1982 г. на собрании, посвященном 15-летию НИИ вычислительных комплексов // Вопросы радиоэлектроники. — Серия ЭВТ. Вып. 2. 1993. С. 2—10.

2. Головкин Б. А. Эволюция параллельных архитектур и машины серии М // Вопросы радиоэлектроники. — Серия ЭВТ. Вып. 2. 1993. С. 18-28.

3. Гливенко Е. В. Параллельный процессор первичной обработки информации. М.: Радио и связь. 1992. 104 с.

4. Гливенко Е. В. Функциональная арифметика (машина М-10) и современные проблемы первичной обработки // Вопросы радиоэлектроники. — Серия ЭВТ. Вып. 2. 1993. С. 44-60.

5. Гливенко Е. В., Саблина С. М. Многопроцессорные системы и геометрическая интерпретация задач // Информационные технологии. 1996. № 3. С. 35—38.

6. Дубровин Б. А., Новиков С. П., Фоменко А. Т. Современная геометрия. М.: Наука. 1979. 760 с.

7. Александров П. С. Комбинаторная топология. М.-Л.: ОГИЗ. 1947. 660 с.

 

ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ, № 3, 1999

ВЫЧИСЛИТЕЛЬНЫЕ СИСТЕМЫ И СЕТИ

 

Ключевые слова: Параллельные вычисления, многомерная геометрия, решение СЛАУ, степени отображений симплекса, минимакс.

Поделиться:
 
ПОИСК
 
elibrary crossref ulrichsweb neicon rusycon
 
ЮБИЛЕИ
ФОТОРЕПОРТАЖИ
 
СОБЫТИЯ
 
НОВОСТНАЯ ЛЕНТА



Авторы
Пресс-релизы
Библиотека
Конференции
Выставки
О проекте
Rambler's Top100
Телефон: +7 (915) 336-07-65 (строго: среда; пятница c 11-00 до 17-00)
  RSS
© 2003-2021 «Наука и образование»
Перепечатка материалов журнала без согласования с редакцией запрещена
 Тел.: +7 (915) 336-07-65 (строго: среда; пятница c 11-00 до 17-00)