Слайд 2
План изложения
Общее введение.
Введение. Роль кубических структур в математических
моделях.
Часть 1. Определение кубантов. Операция умножения. Моноид.
Часть 2.
Метрика Хаусдорфа-Хэмминга на кубантах в In.
Часть 3. Метрика Евклида-Хаусдорфа в Rnс.
Часть 4.Элементы кубического синтеза.
Часть 5.Элементы динамики на кубических структурах.
Часть 6.Машинное представление данных и операций.
Часть 7.Полиморфное кодирование и алгебраизация супервычислений.
Часть 8. Инструментальная система на суперкомпьютере.
Литература.
Приложение 1.Непересекающиеся к-пути.
Приложение 2. Примеры графического представления.
Приложение 3. 3-пути через случайную окрестность.
Слайд 3
Общее введение
Интеллектуальные информационные технологии подразумевают не только работы
по компьютерной интерпретации механизмов мозга человека, но и использование
лингвистических( в т.ч. и математических) методов для более адекватного представления (кодирования в машинные формы) и дальнейших конструктивных компьютерных действий над элементами ( и структурами из них) самой общей природы с целью их более глубокого познания.
Возможность сочетания в единой форме машинного представления различных (даже разнородных) свойств элементов некоторого множества и единообразных операций над такими представлениями открывает дорогу для установления новых закономерностей и как результат этого способствует решению прикладных проблем. Такой подход в праве характеризовать как одну из ветвей интеллектуальных информационных технологий.
Представления многомерных метрических и топологических пространств, являются основой для различных моделей их структуризации и эффективного отображения этих моделей в существующие или принципиально реализуемые компьютерные системы.
Слайд 4
В самом общем виде основа содержательной части -
конкретный пример построения конструктивного мира кубических структур на основе
нетрадиционного кодирования, обладающего полиморфными свойствами. Это кодирование позволяет ввести операции, совмещающие вычисление величин, характеризующих метрические, топологические, комбинаторные и алгебраические свойства элементов и структур из этого конструктивного мира.
Основные операции сводятся к поразрядным операциям, которые обладают максимальной совмещенностью – потенциальной реализацией выполнения за один машинный такт обработки практически неограниченных по числу n разрядов слов, где n-размерность рассматриваемого пространства. Эти операции эмулированы на современных компьютерах и могут быть эффективно аппаратно реализованы в компьютерах следующих поколений.
Постановка задач анализа и синтеза объектов из этого конструктивного мира и алгоритмы решения этих задач опираются на предложенные представления и введенные операции.
Слайд 5
В рамках предыдущих тезисов и следует рассматривать ниже
изложенное содержание результатов под общим названием «Алгебраическое представление кубических
структур и супервычисления», которое является составной частью проекта, поддержанного грантом РФФИ (09-07-12135-офи-м).
С другой стороны эта тематика является дальнейшим развитием инструментальной системы под общим названием «Топологический процессор», развиваемой в НИВЦ МГУ с 2005 года с целью более полного математического и программного обеспечения суперкомпьютерных систем ( в частности суперкомпьютера МГУ «Чебышев») при решении комбинаторных геометрико-топологических задач.
Образовательная сторона исследований направлена на выработку наиболее компактных и доходчивых представлений многомерных структур (чаще всего в виде группоидов) и действий на них, интерпретированных традиционными и нетрадиционными машинными операциями, широко используя совмещение и параллелизм.С целью подготовки специалистов такого профиля создан и продолжает расширяться спецкурс для студентов факультета ВМ и К МГУ «Введение в компьютерные методы комбинаторно-топологических построений».
Слайд 6
Роль кубических структур в геометрико-топологической основе математических моделей
Глобальная
модель циркуляции (МТИ)-погодный и климатический прогноз. Конформная кубоидная сфера.
?
Геометрическая основа науки о двоичном кодировании -n-мерный единичный куб. (R.Hamming)[8]
Слайд 7
Изометрические вложения
в кубические структуры
Эффективное отображение на кубические
структуры.
Вложения плоских мозаик в реберный остов Zn.
Работы- Деза, Долбилина,
Штанько, Штогрина.[2,3,4]
Слайд 8
Комбинаторные многогранники,
кольцо граней Стенли-Райснера
Для простого многогранника Р
c гранями F1,…Fm и коммутативного кольца К с единицей
кольцо граней Стенли-Райснера- факторкольцо К(Р)=К[v1,…vm]/ℑp, где ℑр-идеал, порожденный мономами vi1,vi2,…vis, что Fi1∩…∩Fis=Ø в Р, i1<…Для P=I3: К[P]=K[v1,…v6]/(v1v4,v2v5,v3v6);
Комбинаторные многогранники и уравнения мат. физики. (В.М.Бухштабер) [ 5 ]
n-куб-комбинаторный многогранник
Слайд 9
Триангуляции на кубических структурах
и их динамика
6 типов
примитивной триангуляции I3.
Марковские цепи в реберной динамике примитивных триангуляций
в R3 и R4. Эргодические свойства.
Распределение допустимых триангуляций в статистике Бозе- Эйнштейна. [18 ]
Слайд 10
Возрастание роли в супервычислениях топологии+многомерности+
комбинаторики +динамики
Эффективные методы представления
семейств объектов для классификации, нумерации и комбинаторных схем перечисления.
Учет
наиболее общих свойств и инвариантов для многомерных построений (симметрия и группы движений, случайные процессы и эргодические свойства).
Кубические структуры - достаточно универсальны для всестороннего компьютерного анализа и создания на этой базе компьютерных методов синтеза. [1-7]
Слайд 11
Принятые обозначения
Rn-n-мерное евклидово пространство.
e1,e2,…en -ортонормированный базис.
Zn-подпространство целых точек
в Rn.
In-n-мерный единичный куб
F(k)-k-мерная грань в In (0-грани-вершины,1-грани-ребра, 2-грани-квадраты
и т.д.)
Fn-множество всех граней In.(k=0,1,…n).
{0,1,2}-троичный алфавит. Dn3- множество всех троичных кодов.
{Ø,0,1,2}-четверичный алфавит. Dn4 – множество всех четверичных кодов.
Sn- симметрическая группа подстановок.
Слайд 12
Часть 1.Пирамида Паскаля и биекция
Fn ↔ Dn3
Пирамида
Паскаля- 3d аналог треугольника Паскаля.
Рекурсивная процедура вычисления триномиальных коэфициентов.
Число
в вершине-число крачайших путей в трехмерной решетке из (000) в данную вершину.
Кодировка путевых перемещений :0-перемещение по х,1-по y, 2-по z.
fk=Cnk2n-k; [19]
Слайд 13
Биекция:мн-во всех n-разрядных троичных кодов??мн-во всех граней n-куба.
Е=e1,e2,…en;?Rn;
D=d1,d2,…dn; di∈{0,1,2};
F(k,p)=Пei + Tej;
i:di=2;(k) j:dj=0,1;(n-k)
Так 021221 – е2 х е4 х е5 (трехмерная грань), транслированная в вершину 001001 в шестимерном кубе I6.
Кубант (кубический квант) – n-разрядный троичный код, однозначно определяющий размерность и положение грани в n-мерном единичном кубе In. [21]
Слайд 14
Троичное кодирование граней I3.
Вершины (0-грани): 001,010,… 111;
Ребра (1-грани):
002,012,…211;
Грани (2-грани): 022,122,…221;
Весь I3 : 222;
Слайд 15
Виды графических интерпретаций
для многомерных случаев
Общие целевые функции
графики- наглядность для плоских проекций, отражение фундаментальных свойств-симметрии. Пример-кубант
112220.
Слайд 16
Бинарная операция умножения
D1=d11,d12,…d1n;
D2=d21,d22,…d2n;
Поразрядная операция умножения задается
следующей таблицей?
В префиксной записи:
П(022121,121012)= Ø21Ø11;(псевдокубант)
П(022121,220112)= 020111;(кубант).
Слайд 17
Расширение алфавита и доопределение операции умножения.
Расширенный алфавит {Ø,0,1,2}.
Операция
умножения (поразрядная) на расширенном алфавите задается следующей таблицей
?
По определению операция –коммутативна, ассоциативна и дистрибутивна.
Слайд 18
Свойства произведения кубантов.
ω(D)-число разрядов с символом Ø.
ω(П(D1,D2)=0? П(D1,D2)
= D3-кубант-пересечение.
ω(П(D1,D2)≠0? ω= Lmin(D1,D2);
П(121012,022121)=Ø21Ø11; П(220112,022121)=020111;
Слайд 19
Доказательство свойства
ω(П(D1,D2))=Lmin (D1,D2).
Пусть В1 и В2 два
различных n-разрядных двоичных слова (алфавит {0;1}), число попарно несовпадающих
разрядов m. Тогда длина минимального пути по ребрам In между вершинами с координатами В1 и В2 равна m.(Хэммингово расстояние).
Заменим в словах В1 и В2 один из совпадающих попарно n-m разрядов на противоположный. Тогда ρ(В1*,В2*)=m.
Заменим этот разряд в В1* и В2* на 2. Образовались 2 кубанта D1 и D2 (соответствующие ребрам),такие что В1,В1*∈D1 , В2,В2*∈D2 и ω(П(B1,B2))=ω(П(В1*,В2*))=Lmin(B1,B2)=m;
С одной стороны Lmin (D1,D2) должно быть ≤ m, т.к. к числу точек каждого множества добавились новые.
Но поскольку добавились только внутренние точки ребер, то минимальный путь до таких точек по ребрам н-куба будет m+Δ≥m. Из этого противоречия следует ω(П(D1,D2))=m=Lmin(D1,D2). И так для любого числа совпадающих попарно разрядов В1 и В2, а следовательно и для любой пары кубантов, т.к. любой кубант можно образовать из двоичного слова заменой ряда разрядов на 2.
Слайд 20
Dn4-моноид относительно умножения.
Все n-разрядные четверичные слова с алфавитом
{Ø,0,1,2} - (кубанты и псевдокубанты) образуют полугруппу относительно введенного
умножения.
Умножение обладает свойством идемпотентности П(D,D)=D; (Маслов [15])
Единица в этой полугруппе – слово 22…2 (соответствует In).
Т.о. Dn4-моноид.
Слайд 21
Подмножество кубантов? матрица парных произведений (смежностей)
D1,D2,…Ds?Mρρ; mij=П(Di,Dj); i,j=1,2…n;
D1=112202;
D2=121122; D3=122211; D4=120122; D5=002212;
112202 111102 1112Ø1 110102 ØØ22Ø2
121122 121111 12Ø122 Ø01112
122211 120111 Ø02211
Mρρ= 120122 Ø00112
симметрия 002212
D1,D2,D3,D4-образуют цикл (общие ребра);D5 отстоит на Lmin=1 от D2,D3,D4 и на Lmin=3 от D1;
Mpp-обобщение матрицы смежностей для графов.
Слайд 22
Часть 2.Хаусдорфова метрика на кубантах. Обобщение метрики Хэмминга.
ρHH(D1,D2)=
max {maxLmin (D1?D2), maxLmin(D2?D1)};
D1=022211; D2=112222;
Lmin(D1?D2) ?112222
002211
П=ØØ2211
max Lmin(D1?D2)=2;
Lmin(D2?D1)? 022211
112200
П=Ø122ØØ
max Lmin(D1?D2)=3;
ρHH(D1,D2)=max{2,3}=3;
Слайд 23
Хаусдорфова метрика на кубантах. Операция Н-сжатия.
Н-сжатие Di относитльно
Dj ?(Di*/Dj) - для вычисления самого длинного из кратчайших
путей от Di до Dj
Max{ωП(Di*/Dj,Dj),ωП(Dj*/Di,Di} = ρHH(Di,Dj);
Слайд 24
Полная матрица НН-метрики для кубантов I3.
Размерно-лексикографическое упорядочение троичных
кодов:
000,001,010,011, …
111, 002,012,020,021, … 211, 022,122,202,212, … 221, 222;
Черный-ρНН=3,
Тем.серый-ρНН=2,
Свет.серый-ρНН=1,
Белый-ρНН=0.
Слайд 25
Структура НН-метрики для In.
Н(k,m)-минор матрицы парных НН-расстояний, содержит
все расстояния между k- и m-размерными кубантами.
r =[r1,r2]-диапазон значений
НН-расстояний.r1,r2-целые;r1≤r2.
Слайд 26
Распределение НН-расстояний
между кубантами для I2-I10.
Таблица M(r,n)-число пар
кубантов в In с rHH=r;
M(0,n)=3n;
M(n,n)=4n-2n-1;
Гистограмма по вертикали- в логарифм.
масштабе.
Горизонталь-почти симметрия.
Слайд 27
Расширение матрицы парных произведений кубантов.
Дополнение злементов матрицы парных
произведений значениями HH-расстояний (/ρнн) между кубантами.
В расширенном виде матрица
содержит полную топологическую и HН-метрическую картину множества кубантов ( в т.ч. HН-диаметр множества, исходные данные для построения HН-кратчайшего связывающего дерева и т.д.)
Ранее приведенный пример Mρρ с расширением приведен ниже.
D1=112202; D2=121122; D3=122211; D4=120122; D5=002212;
112202/0 111102/2 1112Ø1/2 110102/2 ØØ22Ø2/3
121122/0 121111/2 12Ø122/1 Ø01112/3
122211/0 120111/2 Ø02211/2
симметрия 120122/0 Ø00112/3
002212/0
Слайд 28
Часть 3.Подмножества кубантов в In.
Булеан n-кубантов-множество всех двоичных
m-разрядных кодов при m=3n;
Каждому кубанту соответствует номер в размерно-
лексикографически упорядоченной последовательности троичных n-разрядных кодов, этот номер равен номеру разряда в булеане, если данный кубант входит в рассматриваемое подмножество.
Каждое подмножество кубантов?двоичное слово в булеане.
000,001,010,…022,122,220,221,222.
1 2 3 23 24 25 26 27
002,122? 000100000000000000000000100;
001,022? 000100000000000000000000000;-поглощение кубанта 001 кубантом 022.
После поглощений число различных подмножеств
< 2m;m=3n;
Для n=2;? m=9;|B|=512; |B*|=47; число всех пар подмножеств:
2209<262144
Слайд 29
Особенности хаусдорфовой метрики на подмножествах кубантов.
Необходимость перехода к
евклидовой метрике.?
Добавление к вершинам (целым точкам) «полуцелых» точек для
каждой грани (кубанта).
2 1 0 ?1/2 1 0; ?
Слайд 30
Соотношения между ρНН и ρЕН в In.
Кубанты:D1=220000; D2=112200;D3=111122;
D4=000022;D5=002211; D6=221111;D7=022120;
ρHH(Di,D7)=3; ρEH(Di,D7)=√3; i=1-6;
Подмножества:
K1={D1,D2,…D6}; K2={D7};
ρEH(K1,K2)= √7/2;
Мах равноудаленная точка
имеет нецелочисленные координаты, т.е. нецелая.
Слайд 31
Вычисление равноудаленных точек
в комплексах из кубантов разной
размерности .
Мах равноудаленная точка – в множестве пересечений прямых,
ортогональных к кубантам другого комплекса в общей для комплексов выпуклой оболочке. Точка и инцидентное ребро считаются ортогональными.
Для I2 –построение отрезков прямых и окружностей с доп.условиями (см. пример).
К1={22};K2={12;00;01};
Окружность касается ребра CD(кубант 12) и проходит через точки А(кубант 00) и В(кубант 01)
Из приведенного построения ρЕН(К1,К2)=5/8;
Для I3 окружности заменяются сферами.
Слайд 32
К вычислению полной матрицы ρЕН всех пар комплексов
In
Среди множества всех подмножеств кубантов возможны «поглощения»: так код
в булеане (для I3) 00…100000001?00…100000000,т.к. кубант 002 содержит вершину 000.
Возможность сокращения общего числа (2^3n ) комплексов за счет «поглощения» кубантов меньшей размерности не приводит к принципиальному результату. Так для I3 общее число комплексов 2^27(точнее 2^26+1) за счет поглощения сводится к ~2^25.
Оценка возможности полных вычислений для I3? 2^52~4*10^15. Задача для суперкомпьютера.
Слайд 33
Два метода вычисления ρЕН для двух множеств целых
точек в R3c.
Волновой алгоритм на {Z3,V3},где V3-множество простых (примитивных)
ребер, не содержащих внутренних целых точек.(Отображения целочисленных множеств и евклидовы приближения. 2007). Учет невыпуклости пространства, приближение к Е-метрике (длина ломаной на простых ребрах)- приближенное значение хаусдорфова расстояния.
Алгебраический метод на основе свойств моноида. Точная Е-метрика, пространство-выпуклое.(2009).
Слайд 34
Сравнение двух методов для мн-ств Zn.
Волна от мн-ва
1 до последней (по шагам) точки мн-ва 2 –р(2,1)=max
min (2?1), от мн-ва 2 до п.т. мн-ва 1- р(1,2)=max min(1?2), рЕН(1,2)=mах{p(2,1);p(1,2)}.
В примере с волной (окр.=2) рЕН~7,3006;(окр.=3)~7,2110;
точ. pEH(1,2)=2√13~7,2110;
Слайд 35
Часть 4.О подходе к задачам синтеза
на кубантах
Формирование
в Rnc (c множеством вершин в Zn) конечного множества
S комплексов кубантов K1,K2,…Km с заданными топологическими и метрическими условиями, а также на мощности множества S и комплексов кубантов.
Формирование - представление, вычисление, преобразование, верификация.
Слайд 36
О расширении некоторых понятий.
Выпуклая оболочка комплекса внутри In-кубант
минимальной размерности,в который вложим комплекс. (рис.1.Выпуклая оболочка комплекса {000000,011111}=I5)
Связность-расширение
понятия связности кубантов(k-связность)-общность граней не меньшей размерности чем k.(рис.2.2-связность)
Путь-расширение понятия пути.Путь по ребрам-1-путь, путь по двумерным граням-2-путь и т.д. Минимальные k-пути.
(рис.2.)- 3-путь
Слайд 37
Примеры k-связности и k-пути.
2-связность комплекса кубантов.
3-путь минимальной длины
из А в В внутри комплекса . Длина пути
-16.
Слайд 38
Гамильтоновы циклы(HC(n)) на In как циклы 1-кубантов.
Представления гамильтонова
цикла:
Вершинное
Реберное
000
001 002
011 021
010 012
110 210
111 112
101 121
100 102
000 200
002
В случае реберного представления гамильтонова цикла выполняются:
П(Di,Di+1)=vi;(vi-вершина n-куба)
ω(П(Di,Di+2))=1;
Слайд 39
Рекурсивная процедура генерации НС(n)?HC(n+1).
Склейка двух НС(n)? HC(n+1);
Склейка попарно
двух ортогональных ? два ортогональных в следующей размерности.
При n>3
In cодержит по крайней мере два орт. НС.
Гипотеза: I2n (n>1) содержит n орт.НС
Слайд 40
Циклические пути с неповторяющимися кубантами.
Обобщение гамильтонова цикла-цикл по
всем k-кубантам на k+1-кубантах.
Динамическая интерпретация пути- «шаги землемера» в
смежную грань. В «распоре»-ребро,квадрат, куб и т.д.(кубанты).
Слайд 41
Пример топологического «строительства»
Кубическая бутылка Клейна из панелей-комплексов гиперграней.
Нумерация
всех комплексов гиперграней и правил их сборки.
Отображение в памяти
компьютера.
Слайд 42
Комплексы из гиперграней I3
10 типов не гомеоморфных комплексов
из гиперграней.
64 типа различных по положению в I3 (различны
коды кубантов).
Слайд 44
Вычисление (построение) комплекса гиперграней в In
Исходные данные: размер,структура,
метрика.
Выходные : Комплекс(ы) кубантов или пустое мн-во.
Алгоритм вычисления с
помощью таблицы возможностей.
Пример из I4: размер-4, цикл, число минимальных путей, отличных от 0 равно 2 ? {0222;2202;1222;2212;}
Слайд 45
Часть 5.Элементы динамики в кубических структурах
Огромное число вариантов
изменения структуры кубических комплексов(с сохранением k-связности между всеми подкомплексами
или без, с сохранением общего числа кубантов или без и т.д.).
Аналоги гомотопных преобразований. Изотропность и анизотропность преобразований.( Минск2007 )
Случайные преобразования-появление и исчезновение k-граней(кубантов) в n-мерных кубических комплексах.(Динамическая маркировка).
Слайд 46
Маркировка кубантов
Маркировки целыми числами соответствуют конечным множествам определенных
качеств в т.ч. наличию или отсутствию кубанта в комплексе
в рассматриваемый момент, определенной раскраске в конечное число цветов, отражающих определенные свойства в зависимости от конечного множества состояний некоторого параллельного процесса или некоторых процессов.
Маркировки вещественными числами отражают непосредственно численные результаты расчетов, связанных с рассматриваемой структурой и приписываемых данному элементу структуры (кубанту).
Слайд 47
Пример маркировки.
Случайный процесс в дискретном времени бросания множества
целых точек, образования в каждый момент на этом множестве
выпуклых оболочек (операция над кубантами) и развития общей перколяционной ситуации.
Маркировки каждого 2-кубанта-момент рождения (1,2,…∈Z+), длина ребер дерева Штейнера (L∈R+) для локального связного множества.
Слайд 48
Кодирование n-октантов, как расширение понятия кубанта
Семиричный алфавит
{Ø,Ø*,0,1,-1,2,-2} и множество n-октантов с одной общей целой
точкой.(«-» вынесен как надстрочный символ).
Табличное задание бинарной операции умножения кубантов в Оn. Коммутативна, но не ассоциативна.
Моноид на семиричном алфавите ? сохранение метрических и топологических свойств представления кубантов.
Слайд 49
Октантная окрестность On целой точки
и комплекс кубантов
на ней
Все n-октанты, имеющие общую вершину (целую точку) образуют
n-октантную окрестность этой точки.
Любой комплекс октантов на окрестности – по к.м. 0-связный.
Комплекс (рис)-1-связный.
22*1*,202*,02*2,2*02,2*2*0,2*02,022, 202,212 (2-2-1=22*1*)
Последовательный обход через 3-октанты(22*2*,222*,2*22*,2*2*2*,2*2*2, 2*22,22*2,222)-3-путь в «разрешенном комплексом коридоре».
Слайд 50
Матрица парных произведений
кубантов в On
Множество кубантов в
O4: {21*22;122*2*;2*212; 1*2*2*2*}; и матрица парных произведений (принятые обозначения
-1=1*;-2=2*):
21*22 122*2* 2*212 1*2*2*2*
21*22 1Ø00 0 Ø12 Ø 1*0 0
122*2* Ø2Ø0 Ø*0 2*2*
2*212 1* 0 Ø 0
1*2*2*2*
Минимальные пути: Ø?1;Ø*?2;
Множество-несвязное.
Слайд 51
3-пути в октантных коридорах
Полупрозрачные 2-грани открыты для прохода.
Вариант
древовидной структуры возможных 3-путей(3d).
Изменения в октантных окрестностях в дискретном
времени. (3d+1)
Слайд 52
Один из вариантов топологической интерпретации алгебры Фробениуса октантными
структурами
Методы алгебраической топологии в теоретической физике – наиболее активная
область исследований. [9,13-15]
Топологическое представление алгебры Фробениуса (АФ) наиболее полно дано А.Лаудой.[10]
Общепринятые операторы АФ и октантные структуры. (рис)
Слайд 53
Кодирование операторов
через октантные структуры
Оператор? комплекс кубантов в
Оn(х1,…хn);
Ситуация на стыках вычисляется как произведение.
Рис. пример кодирования в
О3.
Слайд 54
Марковские процессы-перестройки кубантов и состояния Оn
В R3
общее число состояний О3 равно 236 , где 36-число
2-граней в О3.
Появление и исчезновение 2-грани – детерминированное или(и) случайное событие.
Зависимость структуры ( радиус связности, род границы и др.) «большого» комплекса от процесса перестроек.
Эргодичность процесса? обобщенная картина динамики.
Слайд 55
4d схема топологических коридоров
в дискретном времени.
Ось дискретного
времени.
Два различных 3-пути (коридора) за 4 дискретных момента времени.
Условия
допустимости (открытости соответствующих граней) для коридора не отображены.
Слайд 56
Генерация комплексов в Rnc.
Склейка (join) комплексов из On(x,y,z).
Самоподобие
и появление новых свойств пространства.
Пример R3c? формирование самоподобной картины
со свойством перколяции.
Расчеты результирующей топологической картины и определение общих свойств связности ? операции над кубантами в октантах.
Слайд 57
Часть 6. Общие положения машинного представления и структуры
данных
Разработать и эффективно реализовать на суперкомпьютерах массивно-параллельной архитектуры (наиболее
доступных отечественному пользователю) инструментальную систему обработки кубических структур на базе предложенной алгебры кубантов и октантов.
В понятие эффективности здесь входят следующие составлящие – размерность пространства и число гиперкубических комплексов, сокращение времени решения задач за счет совмещения действий в одной операции и максимального распараллеливания обработки между многими процессорами суперкомпьютера.
Слайд 58
Машинное представление кубантов
Машинное представление четверичного алфавита:
Ø?0;0?1;1?2;2?3
При двоичном представлении
этого алфавита операция умножения кубантов совпадает с поразрядной(битовой) операцией
логического умножения 2n-разрядных двоичных слов.
Машинное табличное представление умножения.
⊗ 0 1 2 3
0 0 0 0 0
1 0 1 0 1
2 0 0 2 2
3 0 1 2 3
Слайд 59
Машинное представление кубантов в On
Машинное представление семиричного алфавита:
Ø?0;Ø*?1;0?2;
1?3;2?4; -1?5; -2?6;
Машинное табличное представление операции
умножения
х 0 1 2 3 4 5 6
0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0
2 0 0 2 0 2 0 2
3 0 0 0 3 3 1 2
4 0 0 2 3 4 0 2
5 0 0 0 1 0 5 5
6 0 0 2 2 2 5 6
Слайд 60
Основные структуры данных.
Текстовый вид входных и выходных данных:
{[
] ( )( )…( )[ ]( )( )…}…{…}?
{ }-комплекс
из n-кубов;
[ ]-координаты n-куба в составе комплекса;
( )-кубант в составе n-куба;Алфавит {Z,0,1,2}
Основные структуры данных- набор классов.
Класс «Куб» (координаты и набор кубантов) –реализация одномерный массив.
Класс «Комплекс»(кубы в комплексе)-одномерный массив
Реализация средствами библиотеки STL C++;
Для кластерной реализации-представление кубанта как самостоятельного элемента: [идентификатор комплекса] [координаты n-куба] [кубант].
Слайд 61
Основные функции
Уровень кубантов (для двух кубантов): умножение и
Н-сжатие.
Уровень комплекса кубантов в n-кубе: вычисление матрицы парных произведений
кубантов и следствий из нее-топологическая и НН-метрическая структура комплекса.
Уровень комплекса из n-кубов: вычисление ЕН-расстояний между комплексами в Rn.
Геометрические операции с n-мерными векторами-библиотеки Intel MKL,BLAS.
Слайд 62
Часть 7. Полиморфное кодирование и алгебраизация супервычислений.
Супервычисления –
это не только рациональные методы использования предельной по своей
производительности аппаратуры и системного программного обеспечения суперкомпьютеров, но и лингвистическое (в том числе и математическое) представление данных и операций над этими данными, позволяющие создать алгоритмы нового уровня параллелизма и совмещения операций.
Ниже рассматриваются аспекты предложенных методов с точки зрения их возможного влияния на архитектурные решения суперкомпьютеров и дальнейшего развития направления условно называемого «полиморфное кодирование и алгебраизация супервычислений».
Слайд 63
Некоторые обобщения
Кубант обладает полиморфными свойствами:
Четверичное n-разрядное слово.
Представляет геометрический
объект (n-мерный куб и его грани). Допускает рассмотрение как
точка гиперметрического пространства с Хаусдорфовой метрикой (обобщение метрики Хэмминга для двоичных кодов).
Представляет элемент топологических комплексов.
Вместе с расширением (псевдокубанты) образует алгебраическую структуру (полугруппу с единицей-моноид) относительно введенной операции умножения.
Разряды слова с символом 2 можно рассматривать как обощение q-битов (значения 0 и 1 и все действительные числа отрезка 0,1) и в целом кодирование как полуквантовое.[12]
В машинном представлении кубант 2n-разрядное двоичное число, к которому применим весь арсенал машинных операций.
В целом эффективная масштабируемость ( в размерности n пространства).
Слайд 64
Вычислительные особенности
Выполнение основной операции (умножения) сводится к поразрядной
операции логического умножения над 2n-разрядных двоичных кодов практически неограниченной
длины-поразрядное перемножение стрингов потенциально может быть реализовано за один машинный такт. Совмещенное вычисление данных о связности и длине кратчайшего пути между кубантами.
Вычисление матрицы парных произведений (обобщение матрицы смежностей) для комплекса из m кубантов имеет сложность m2.
Вычисление Хаусдорфова расстояния между n-мерными кубантами вместо задачи экспоненциальной сложности 2n сводится к задаче сложности n.
Слайд 65
Вычислительные особенности
для суперкомпьютеров кластерного типа
Линейный характер увеличения
длины слова кубанта от размерности пространства n и поразрядные
операции над кубантами позволяют задать вопрос об оценке предельных возможностей современных кластерных суперкомпьютеров в задачах подобного класса и на ближайшую перспективу при условии сохранения общих тенденций развития их архитектур.
В качестве самого упрощенного (начального) подхода рассмотрим первый этап в задаче анализа структуры M комплексов (каждый по m кубантов) в n-мерном пространстве – вычисление матриц парных произведений.
Слайд 66
Для оценок общих ресурсов по оперативной памяти и
производительности необходимо учесть, что каждый кубант сопровождает значительный объем
данных во много раз превосходящий представление его геометрико-топологической структуры. Обработка этих данных на данном этапе не рассматривается, но в оценке объема оперативной памяти они участвуют. Будем считать, что их объем 2nv, где n- размерность пространства, а v-некоторая постоянная.
Тогда грубая оценка оперативной памяти для хранения исходных данных в байтах Mm(2n/8)2nv (при v=100 байт ΣV0=100Mm(n/4)2n ;а выходных данных (матриц) ΣV1=Mm2(n/4);
Оценка общего числа операций для одноразового вычисления всех M матриц парных произведений для комплексов из m кубантов Q= Mm2(n/4).При n=10; M=10^3;m=10^3;
Q~10^10;(в настоящее время производительность нескольких процессоров)
Sv0~10^5 10^3 10^3=10^11 <1Терабайт (в настоящее время память 500 микропроцессоров).
При n=20 и тех же M,m :Q~10^11; SV0~1 Петабайт (память 0,5 миллиона современных микропроцессоров).
Т.о. следует ожидать, что проблемы оперативной памяти в этой области будут возрастать быстрее чем суммарного быстродействия.
Если рассматривать только данные по структуре(SV1), то возможна обработка до n=100;M=10^3;m=10^4. Тогда Q~10^15-10^16; SV1~0,1Петабайт – диапазон петафлопсной системы.
Слайд 67
Часть 8. Инструментальный комплекс
«Топологический процессор»
Основная цель -
разработать математическое и программное обеспечение для инструментальной системы, реализующей
операции анализа и синтеза на многомерных кубических структурах, максимально используя методы совмещения и распараллеливания вычислений на архитектурах современных и перспективных суперкомпьютеров.
Работы ведутся в НИВЦ МГУ с 2005 года. Программное обеспечение на С++.Графика openGL,VRML.
Начало реализации на системе «Чебышев». («Волна» на решетке 1010 )-2008г
Основные публикации по теме за прошлые годы:
Рябов Г.Г.Метрические и топологические волны на решетках.//Изд. НИВЦ МГУ.2005
-------- Алгоритмические основы топологического процессора.// Труды МСО-2005.МГУ.
Рябов Г.Г.,Серов В.А. Отображения целочисленных множеств и евклидовы приближения.//Выч. методы и программирование.2007
Ryabov G.,Serov V. Simplicial-lattice model and metric-topological constructions.// Proc. IX PRIP-conference.Minsk.2007
Рябов Г.Г.,Серов В.А. Компьютерные комбинаторно-топологические построения и их преобразования.//Информационные технологии и выч. системы.РАН.2008
Слайд 68
Схема работ по инструментальному комплексу «Топологический процессор».
Слайд 69
Текущие технические задачи
Разработка набора макроопераций на основе алгебры
кубантов для инструментальной системы «Топологический процессор», являющейся инструментом фундаментальных
исследований в части построения примеров и контрпримеров с определенными свойствами.
Программная реализация и верификация набора макроопераций «Алгебра кубантов» для суперкомпьютера МГУ «Чебышев».
Полное документирование математического и программного обеспечения «Алгебры кубантов».
Подготовка и выпуск методического пособия по «Алгебре кубантов».
Слайд 70
Текущие теоретические задачи
Разработка вариантов организации структуры оперативной памяти
кластерного суперкомпьютера для эффективной реализации алгоритмов на базе алгебры
кубантов.
Исследования видов полиморфного кодирования для симплициальных структур и совмещенных кубико-симплициальных структур.
Разработка эффективных (с точки зрения машинной реализации) октантных структур и операций над ними для кодовой интерпретации алгебр Фробениуса.
Слайд 71
Литература.
1.Новиков С.П. Топология. Москва-Ижевск.РХД.2002.
2.Долбилин Н.П.,Штанько М.А.,Штогрин М.И. Кубические
многообразия в решетках.// Изв.РАН.Сер. матем.1994.58.вып.2.93-107
3.Деза М.,Штогрин М. Вложение графов
в гиперкубы и кубические решетки.// Успехи матем. наук.1997.52.№6.155-156.
4.Деза М.,Штогрин М. Мозаики и их изометрические вложения.// Изв. РАН.Сер. матем.2002.66.№3.3-22.
5.Бухштабер В.М. Кольцо простых многогранников и дифференциальные уравнения.// Трды матем. Ин-та РАН.2008.263.18-43.
6.Кузнецов С.Д.,Кудрявцев Ю.А. Математическая модель OLAP-кубов. //Программирование.2009.№5
7.Pedersen T.B. Multidimensional databases.// Industrial Information Technology.Handbook. 2005.
8.Hamming R.W. Error detecting and error correcting codes.// Bell system Tech.Journal. 1950.29(2) 147-160
9.Baez J.,Lauda A. A Prehistory of n-categorical Physics.// arXiv: 0908.2469.v1 [hep-th] 18 Aug 2009.
10.Lauda A. Frobenius algebras and planar open string topological field theories.// arXiv: math(0508.349 v1) [math QA] 18 Aug 2005.
11.Stanley R. Combinatoric and Commutative Algebra.// Birkhauser.1996
12.Manin Yu.I. Classical computing, quantum computing and Shor’s factoring algorithm. // arXiv: quant-ph/9905008 v1. 2 March 1999.
Слайд 72
13.Ambjorn J.,Jurkevicz J.,Loll R. The Universe from Scratch.
// arXiv: hep-th/0509010 v3. 14 Oct 2006.
14.Coecke B.,
Quantum picturalism.// arXiv:0908.1787v1[quant-ph] 13 Aug 2009.
15.Литвинов Г.Л.,Маслов В.П.,Шпиз Г.Б. Идемпотентный функциональный анализ. Алгебраический подход. Математ.заметки. 69:5(2001),758-797
16.Ryabov G.,Serov V., Simplicial-lattice model and metric-topological constructions.// Proc. of IX Conf. on Pattern Recognition and Inf. Processing. V2. Minsk.2007.135-140
17.Рябов Г.Г. О путевом кодировании k-граней в n-кубе. //Вычислительные методы и программирование. 2008.9.N1.20-22
18.------- Марковские процессы в динамике примитивной триангуляции в пространствах R3 и R4.//Вычислительные методы и программирование. 2009. 10.N1,5-12
19.------- О четверичном кодировании кубических структур.// Вычислительные методы и программирование. 2009.10.N2,154-161
20.------- Хаусдорфова метрика на гранях n-куба. //Фундаментальная и прикладная математика.2009.(в печати).
21.-------Алгебраическое представление кубических структур и супервычисления.//Сб.Программные системы и инструменты. ВМиК МГУ.2009.№10,12-26
Слайд 73
Приложение 1.Генерация комплексов кубантов внутри In(On).
1.Общие условия(ОУ) на
множество комплексов.
2.Условия внутри комплексов.(УВК)
3.Условия между комплексами.(УМК)
4.Диагностика совместимости условий.(ДСУ)
Рассмотрение на
примере построения(вычисления) максимального числа непересекающихся минимальных (по длине) k-путей из одной вершины в другую n-мерного куба с максимальным разнесением их друг от друга.
Слайд 74
Неформальная постановка задачи
Проложить максимальной число к-мерных непересекающихся тоннелей
минимальной длины между двумя заданными вершинами n-куба на максимальном
расстоянии друг от друга.(Кроме пересечения этих путей в начальной и конечной вершинах).
Слайд 75
Формальная постановка для I9.
Общие условия: размерность n=9;заданы вершины
D1=(00…0) и D2=(11…1); определить три k-пути (три множества кубантов)
K1{А1,A2…Am};K2{В1,B2,…Bm};K3{С1,C2,…Cm} размерности k=3 в I9 таких, что m-min и выполняются
УВК: dimП(Аi,Ai+1)=2; dimП(Bi,Bi+1)=2; dimП(Ci,Ci+1)=2; для i=1 ÷ m-1;
П(A1,D1)=D1;П(B1,D1)=D1;П(С1,D1)=D1;
П(Am,D2)=D2; П(Bm,D2)=D2; П(Cm,D2)=D2;
УМК:П(Ai,Bi)=Ø;П(Ai,Ci)=Ø;П(Bi,Ci)=Ø; i=1÷m;
ρHH(Ai,Bi)=ρHH(Ai,Ci)=ρHH(Bi,Ci)=max;i=1÷m;
Кратчайший путь по ребрам(1-путь) между D1 и D2 равен 9, по квадратным граням (2-путь) – 8, по кубическим граням (3-путь)-7. Отсюда m=7;
Общий вид Ai и Ai+1? 002121210 002121120?П=002121110? dim П=2;
Слайд 76
К решению задачи
Кубантный тензор-размер 9х7х3, где 9-размерность куба,
7-длина кратчайшего пути, 3-число путей.
Простейший вид матрицы 9x7
(кубанты располагаются столбцом в лексикографическом порядке слов), выполняются УВК:
K1
000000222
000002221
000022211
000222111
002221111
022211111
222111111
Слайд 77
К решению задачи
Куб как объект с осевой (00…0,11…1)
симметрией?организация по той же схеме матриц К2 и К3
приводит к :
К1 К2 К3
000000222 000222000 222000000
000002221 002221000 221000002
000022211 022211000 211000022
000222111 222111000 111000222
002221111 221111002 111002221
022211111 211111022 111022211
222111111 111111222 111222111
Выполняются все условия поставленной задачи при любой одновременной перестановке столбцов в К1,К2,К3 (коммутативность умножения), кроме максимальной удаленности друг от друга.
Слайд 78
Хаусдорфова метрика
в рассматриваемой задаче.
Операция Н-сжатия не коммутативна
и перестановки столбцов в к-тензоре могут менять рНН между
кубантами в путях.
На рис.слева показаны значения ρНН для вышеприведенного решения. Они максимальны для 9! перестановок столбцов.
Слайд 79
Приложение 2. О некоторых графических отображениях кубических структур
Основные
цели графического отображения в рамках рассматриваемых методов:
Визуальная ориентация пользователя
в многомерных структурах.
Для различных задач – различные методы.
Выход в открытые графические системы (VRML) с полным набором их средств визуализации.
Рис. традиционный метод отображения для I6 (c кластеризацией вершин по 8).
Слайд 80
Реперно-ориентированные отображения
Более привычное для глаза восприятие граней в
n-мерном кубе (меньший разброс в метрике ребер).
Вариация репера? вариация
отображения.
Рис. плоский репер и отображение вершин и ребер 9-мерного куба.
Слайд 81
Кубанты и комплексы кубантов
3d-репер, цветовая идентификация, выход
в VRML-оперативный инструментарий для отображения кубантов и комплексов из
них.
Рис.Отображения I6 и решения задачи о 3-путях (приложение 1).
Слайд 82
Приложение 3. 3-пути сквозь случайную О3 .
Постановка задачи.
Задан октант, в нем 2-грани двух типов ( кодировка:
0-закрыты,1-открыты – рис.серый цвет).
Вычислить кратчайший(ие) 3-пути между входами (-1,.,.) и выходами (1,.,.)-число и их длину, проходя через открытые 2-грани.
Слайд 83
К постановке задачи.
36-и разрядный двоичный код отражает какие
грани открыты (1) и закрыты (0) для 3-путей.
На множестве
всех возможных разбиений всех 2-граней О3 построить распределение кратчайших 3-путей по числу и длине.
Для каждого кода вычислить топологический тип.
Слайд 84
Допустимые кратчайшие 3-пути и их длины
Для дальнейшего изучения
марковских процессов в динамике случайного поведения 2-граней необхдима матрица
переходных вероятностей между допустимыми состояниями.(20х20)
Слайд 85
Допустимые топологические типы
Соотношение числа входов и выходов.
Структуры кратчайших
связ. деревьев.
Число изолированных деревьев.
Характеристика каждого дерева.
Дальнейшие расчеты на «Чебышеве».
![Основные структуры данных.Текстовый вид входных и выходных данных:{[ ] ( )( )…(](/img/tmb/12/1108742/76f66935714286c15a4c2bd2c324ae6d-720x.jpg "Полиморфное кодирование кубических структур, операции над кубантами, моноид, хаусдорфова метрика и совмещенные машинные операции в супервычислениях")
