Параллельный алгоритм построения остова многогранного конуса презентация

построения остова
многогранного конуса

Золотых Н.Ю. Земскова Е.Л. Агафонов Е.А
ННГУ им. Лобачевского, Н.Новгород

2002 г.

: Ax ≥ 0}, A ∈ Fmxn
Коническая оболочка:
Cone{r1,…,rs} = {α1r1+…+ αsrs: α1≥0,…,αs≥0},
r1, r2, … rs – векторы из Fn
r1, r2, … rs - остов конуса, если:
C(A) = Cone{r1,…,rs}
минимальная по включению

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

в обе стороны в силу теоремы Вейля:
C(A) = Cone (b1,b2,…bs) ⇔ C(BT) = Cone (a1T,a2T,…,atT),
где b1,b2,…bs – система столбцов матрицы B,
a1,a2,…,at - система строк матрицы А

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

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

транспортной задачи:

Число неизвестных: m⋅n⋅l
Число уравнений:
m⋅n + m⋅l + n⋅l
Число неравенств:
m⋅n⋅l

где A ∈ Fmxn, x ∈ Fn, b ∈ Fm

{Ax=b, x≥0}
имеет
решение

b ∈ Cone(a1,…,an)
A=(a1,…,an)

⇔

aij, bjk, cki (1995г.)
4x4x3:
10 равенств и 4948 неравенств для коэффициентов aij, bjk, cki
4x4x4:
11 равенств и 113740 неравенств для коэффициентов aij, bjk, cki

работы программы
S(p) – ускорения на P процессорах
E(p) – эффективность на P процессорах

мин.
P=6 – 2ч. 4 мин.

Ускорение ≈ 5.25
Эффективность ≈ 0,878

ННГУ)
e-mail: zny@uic.nnov.ru
Web: http://www.uic.nnov.ru/~zny