Второй Международный научно-практический семинар Высокопроизводительные Параллельные Вычисления на Кластерных Системах Параллельный алгоритм построения остова многогранного конуса Золотых Н.Ю. Земскова Е.Л. Агафонов Е.А ННГУ им. Лобачевского, Н.Новгород 2002 г.

Параллельный алгоритм построения остова многогранного конуса Определения Многогранный конус: C(A) = {x F n : Ax 0}, A F mxn Коническая оболочка: Cone{r 1,…,r s } = {α 1 r 1 +…+ α s r s : α 1 0,…,α s 0}, r 1, r 2, … r s – векторы из F n r 1, r 2, … r s - остов конуса, если: C(A) = Cone{r 1,…,r s } минимальная по включению

Параллельный алгоритм построения остова многогранного конуса Теорема Минковского Коническая оболочка Многогранный конус Для любого многогранного конуса найдется порождающая его система векторов и, наоборот, коническая оболочка конечной системы векторов является многогранным конусом

Параллельный алгоритм построения остова многогранного конуса АлгоритмМоцкина-Бургера Коническая оболочка Многогранный конус Алгоритм Моцкина-Бургера Алгоритм работает одинаково в обе стороны в силу теоремы Вейля: C(A) = Cone (b 1,b 2,…b s ) C(B T ) = Cone (a 1 T,a 2 T,…,a t T ), где b 1,b 2,…b s – система столбцов матрицы B, a 1,a 2,…,a t - система строк матрицы А

Параллельный алгоритм построения остова многогранного конуса Шаг алгоритма Алгоритм итеративный Предварительный шаг алгоритма: выделение в матрице А ранговой подсистемы и нахождение начального остова алгоритмом Гаусса Общий шаг алгоритма: добавление нового ограничения к построенному остову

Параллельный алгоритм построения остова многогранного конуса Параллельный вариант Главный процессор(0) Добавление новых вершин процессор #1 Нахождение ребер и вычисление новых вершин процессор #2 Нахождение ребер и вычисление новых вершин Процессор #p-1 Нахождение ребер и вычисление новых вершин Процессор #p Нахождение ребер и вычисление новых вершин …… На каждом итерационном шаге каждому процессору необходимо знать остов, полученный на предыдущем шаге

Параллельный алгоритм построения остова многогранного конуса Тестовая задача Получение условий совместности 3-х индексной транспортной задачи: Число неизвестных: m n l Число уравнений: m n + m l + n l Число неравенств: m n l

Параллельный алгоритм построения остова многогранного конуса Тестовая задача Условие совместности задачи {Ax=b, x0}, где A F mxn, x F n, b F m {Ax=b, x0} имеетрешение b Cone(a 1,…,a n ) A=(a 1,…,a n )

Параллельный алгоритм построения остова многогранного конуса Результаты 4x3x3: 9 равенств, 717 неравенств для коэффициентов a ij, b jk, c ki (1995г.) 4x4x3: 10 равенств и 4948 неравенств для коэффициентов a ij, b jk, c ki 4x4x4: 11 равенств и неравенств для коэффициентов a ij, b jk, c ki

Параллельный алгоритм построения остова многогранного конуса Результаты(4x4x3) Время работы PT 135 c. 240 c. 323 c. 416 c. 513 c. 612 c. 710 c. 89 c. P – число процессоров T – время работы программы S(p) – ускорения на P процессорах E(p) – эффективность на P процессорах

Параллельный алгоритм построения остова многогранного конуса Результаты(4x4x4) Время работы программы: P=1 – 10ч 43 мин. P=6 – 2ч. 4 мин. Ускорение 5.25 Эффективность 0,878

Параллельный алгоритм построения остова многогранного конуса Контакты Золотых Н.Ю. (доцент кафедры МЛиВА, ВМК ННГУ) Web: