Исследование свойств диагональных латинских квадратов в проектах добровольных распределенных вычислений и не только...
В код нового генератора ДЛК в окрестностях обобщенных симметрий для различных парастрофических срезов внесены косметические изменения, в проект добавлена новая версия расчетного модуля 3.2.5 и около 40 тыс. тестовых WU'шек эксперимента e749 с теми же параметрами, что и ранее. Считаем...
Новая версия генератора ДЛК в окрестностях обобщенных симметрий для различных парастрофических срезов дает первые неплохие результаты: уже известные находки в окрестности (1,31)-симметрии в первом срезе удалось перенайти по новой, в окрестности несуществующей (3,22)-симметрии в том же срезе находок нет, что полностью согласуется с ожиданиями. В проект добавлена новая версия расчетного модуля 3.2.6, в которой реализовано еще одно косметическое улучшение в коде, которое способно повысить темп получения ОДЛК на выходе. Считаем текущую партию из 40 тыс. WU'шек эксперимента exp749v3, анализируем результаты и можно приступать к началу разведки в парастрофических срезах 2—6, куда мы ранее напрямую не заглядывали (такие находки есть среди списка КФ ОДЛК, их источником являются квадраты с плоскостной симметрией, у которых кроме нее имеют место еще и такие симметрии, получаемые через парастрофические преобразования, однако до этого они получались как побочный продукт, теперь же в текущем эксперименте будет производиться их целенаправленный поиск).
Результаты тестирования нового генератора ДЛК в окрестностях обобщенных симметрий (exp749) в различных парастрофических срезах.
Парастрофический срез 1 [Px Py Pv], (3,22)-симметрия, удаление M=70
ONCE (A):1 - 262, where:
2 CFs - 262
Парастрофический срез 1 [Px Py Pv], (3,22)-симметрия, удаление M=80
ONCE (A):1 - 2, where:
2 CFs - 2
Парастрофический срез 1 [Px Py Pv], (1,31)-симметрия, удаление M=70
ONCE (A):1 - 2508, where:
2 CFs - 2508
LINE3 (B):1 - 887, where:
2 CFs - 847
3 CFs - 40
LINE3 (B):2 - 867, 3:1, where:
2 CFs - 847
3 CFs - 20
LOOP4 (E):2 - 93, where:
3 CFs - 93
1TO4 (G):1 - 90, where:
3 CFs - 90
1TO4 (G):4 - 45, where:
3 CFs - 45
1TO8 (I):1 - 4, where:
5 CFs - 4
1TO8 (I):8 - 1, where:
5 CFs - 1
RHOMBUS4 (K):2 - 18, where:
4 CFs - 2
5 CFs - 16
RHOMBUS4 (K):4 - 6, where:
4 CFs - 2
5 CFs - 4
Парастрофический срез 1 [Px Py Pv], (1,31)-симметрия, удаление M=80
ONCE (A):1 - 284, where:
2 CFs - 284
LINE3 (B):1 - 16, where:
2 CFs - 12
3 CFs - 4
LINE3 (B):2 - 14, 20:1, where:
2 CFs - 12
3 CFs - 2
1TO4 (G):1 - 8, where:
3 CFs - 8
1TO4 (G):4 - 4, where:
3 CFs - 4
RHOMBUS4 (K):2 - 2, where:
4 CFs - 2
RHOMBUS4 (K):4 - 2, where:
4 CFs - 2
Хорошо видно, что для несуществующей симметрии (3,22) окрестность бедная, о чем мы знали и до этого с использованием генератора без парастрофий, новый генератор дал идентичные результаты. Для существующей симметрии (1,31) окрестность богатая на редкие находки, что опять таки подтверждено с использованием нового генератора. Модификация генератора, которая тестировалась на WU'шках exp749v2 -> exp749v3, приблизительно на треть повышает выход КФ ОДЛК при сопоставимых затратах вычислительного времени. Таким образом, все готово к запуску нового масштабного вычислительного эксперимента в дополнение к выполняемым в настоящее время...
В проект добавлена первая боевая партия из 163 тыс. WU'шек wu_e749_*_slice3_* для поиска КФ ОДЛК в окрестностях обобщенных симметрий в парастрофическом срезе № 3 [Py Px Pv]. Параметры те же, что и раньше: кворум — 1, дедлайн — 7 дней, время счета — не более 20 минут.
Первые результаты исследования окрестностей обобщенных симметрий в парастрофических срезах (см. https://vk.com/wall162891802_1263). Кроме однушек и двушек пока ничего нет, но это ведь только самое начало... Генератор работает стабильно, достаточно эффективно, находки есть, исследуем срез... 
Результаты поиска КФ ОДЛК в проекте Gerasim@Home за месяц:
ONCE (A):1 - 605456, where:
1 CFs - 33160
2 CFs - 572296
LINE3 (B):1 - 68975, where:
2 CFs - 18735
3 CFs - 50240 (+2922)
LINE3 (B):2 - 43855, 14:1, where:
2 CFs - 18735
3 CFs - 25120 (+1461)
LINE4 (C):1 - 124, where:
2 CFs - 4
4 CFs - 120 (+6)
LINE4 (C):2 - 124, where:
2 CFs - 4
4 CFs - 120 (+6)
LINE5 (D):1 - 17, where:
3 CFs - 17
LINE5 (D):2 - 34, where:
3 CFs - 34
LOOP4 (E):2 - 2244, where:
1 CFs - 2
2 CFs - 138
3 CFs - 1464
4 CFs - 640 (+4)
1TO3 (F):1 - 360, where:
4 CFs - 360 (+12)
1TO3 (F):3 - 120, where:
4 CFs - 120 (+4)
1TO4 (G):1 - 1290, where:
3 CFs - 882
5 CFs - 408
1TO4 (G):4 - 543, where:
3 CFs - 441
5 CFs - 102
1TO5 (k):1 - 10, where:
6 CFs - 10
1TO5 (k):5 - 2, where:
6 CFs - 2
1TO6 (H):1 - 42, where:
4 CFs - 24
7 CFs - 18
1TO6 (H):6 - 11, where:
4 CFs - 8
7 CFs - 3
1TO7 (h):1 - 7, where:
8 CFs - 7
1TO7 (h):7 - 1, where:
8 CFs - 1
1TO8 (I):1 - 48, where:
5 CFs - 32
9 CFs - 16
1TO8 (I):8 - 10, where:
5 CFs - 8
9 CFs - 2
RHOMBUS3 (J):2 - 9, where:
5 CFs - 9
RHOMBUS3 (J):3 - 6, where:
5 CFs - 6
RHOMBUS4 (K):2 - 73, where:
3 CFs - 2
4 CFs - 23
5 CFs - 32
6 CFs - 16
RHOMBUS4 (K):4 - 34, where:
3 CFs - 1
4 CFs - 17
5 CFs - 8
6 CFs - 8
FISH (N):1 - 7, where:
4 CFs - 1
6 CFs - 6
FISH (N):2 - 11, where:
4 CFs - 2
6 CFs - 9
FISH (N):4 - 4, where:
4 CFs - 1
6 CFs - 3
TREE1 (V):1 - 2, where:
4 CFs - 2
TREE1 (V):2 - 1, where:
4 CFs - 1
TREE1 (V):3 - 1, where:
4 CFs - 1
CROSS (X):1 - 16, where:
6 CFs - 16
CROSS (X):2 - 4, where:
6 CFs - 4
CROSS (X):4 - 4, where:
6 CFs - 4
DAEDALUS10 (i):1 - 6, where:
12 CFs - 6
DAEDALUS10 (i):2 - 4, where:
12 CFs - 4
DAEDALUS10 (i):4 - 1, where:
12 CFs - 1
DAEDALUS10 (i):10 - 1, where:
12 CFs - 1
FLYER (j):1 - 2, where:
8 CFs - 2
FLYER (j):2 - 3, where:
8 CFs - 3
FLYER (j):4 - 3, where:
8 CFs - 3
VENUS (l):1 - 1, where:
5 CFs - 1
VENUS (l):2 - 3, where:
5 CFs - 3
VENUS (l):4 - 1, where:
5 CFs - 1
DAEDALUS8 (m):1 - 2, where:
6 CFs - 2
DAEDALUS8 (m):2 - 2, where:
6 CFs - 2
DAEDALUS8 (m):4 - 1, where:
6 CFs - 1
DAEDALUS8 (m):8 - 1, where:
6 CFs - 1
RHOMBUS5 (n):2 - 4, where:
5 CFs - 4
RHOMBUS5 (n):5 - 1, where:
5 CFs - 1
1TO10 (o):1 - 5, where:
6 CFs - 5
1TO10 (o):10 - 1, where:
6 CFs - 1
ROBOT (p):1 - 4, where:
5 CFs - 4
ROBOT (p):2 - 4, where:
5 CFs - 4
ROBOT (p):4 - 2, where:
5 CFs - 2
STINGRAY (q):1 - 1, where:
5 CFs - 1
STINGRAY (q):2 - 3, where:
5 CFs - 3
STINGRAY (q):3 - 1, where:
5 CFs - 1
Эксперимент по исследованию свойств окрестностей обобщенных симметрий:
* парастрофический срез 1 [Px Py Pv]: пройдено 502 (+45) окрестностей из 903 (55,6%, +5,0%);
* парастрофический срез 3 [Py Px Pv]: запущен соответствующий эксперимент, пройдено 8 окрестностей из 1764 (0,5%).
О числе линеек СН ДЛК порядка N
В статье https://cs.uwaterloo.ca/journals/JIS/VOL23/Zaikin/zaikin3.pdf было приведено подробное описание того, как можно использовать X-образные диагональные заполнения элементов ДЛК для ускорения алгоритмов подсчета числа ДЛК заданного порядка N (для N=9 приблизительно в 1000 раз по сравнению с высокооптимизированной версий на базе вариации заполнения ячеек ДЛК, программной реализации с использованием вложенных циклов и битовой арифметики). При этом число классов эквивалентности (оно же — число т.н. линеек сильно нормализованных ДЛК, сокр. СН ДЛК) в статье приведено только для размерности N=8. Что нам мешает посчитать соответствующее число классов эквивалентности для других порядков N, сформировать числовой ряд и добавить его в OEIS? Ничего! На самом деле этот ряд был посчитан достаточно давно, около 3 лет назад, лежал, ждал своего часа и вот наконец дождался...
1, 0, 0, 2, 2, 3, 3, 20, 20, 67
Статья по ссылке не открывается, поправьте, пожалуйста.
Генератор КФ ДЛК на базе ESODLS схем
При перечислении ДЛК важную роль играют различные изоморфизмы между квадратами, позволяющие разбить квадраты на классы изоморфизма (эквивалентности). Это, в свою очередь, позволяет снизить сложность соответствующих переборных алгоритмов на несколько порядков. На сегодняшний день мы при работе с ДЛК время от времени используем следующие классы:
* класс из N!-1 ненормализованных квадратов и 1 нормализованного (наиболее часто употребляемые способы нормализации: по первой строке и по главной диагонали);
* главный класс, мощность которого определяется числом комбинаций M-преобразований с одной стороны и числом M-симметрий у ДЛК в его составе с другой (она находится между https://oeis.org/A299783 и https://oeis.org/A299784).
Если построение нормализованных ДЛК особой сложности не представляет и выполняется тривиально в независимости от выбранного способа нормализации, то построение КФ (напомню, между КФ и главными классами взаимно-однозначное соответствие) — задача нетривиальная. Разработанный генератор КФ базируется на идеях, высказанных довольно давно whitefox'ом, но при этом его программная реализация, базирующаяся на ESODLS схемах, отличается.
Прежде всего, необходимо вспомнить, что у нас есть X-образные заполнения диагоналей. Первую диагональ будем заполнять значениями подряд, вторую — полным перебором всеми возможными способами, в результате чего получится множество X-образных заполнений диагоналей, каждое из которых можно полным перебором дозаполнить до полных ДЛК — так мы получим генератор нормализованных по главной диагонали ДЛК. Этот прием (первоочередное заполнение диагоналей) в свое время существенно поднял темп перебора ДЛК в разработанных нами генераторах, однако в рамках построения генератора КФ данное заполнение само по себе не интересно...
Интересно другое: между различными X-образными заполнениями существует изоморфизм, выражающийся в том, что для разных (но изоморфных!) диагональных заполнений число дозаполнений до ДЛК совпадает. Эта особенность была использована при проверке числа ДЛК порядка 9 через классы изоморфизма X-образных заполнений, выполненная независимо друг от друга Степаном Кочемазовым и whitefox'ом, результаты которой отражены в статье https://cs.uwaterloo.ca/journals/JIS/VOL23/Zaikin/zaikin3.pdf. Учет данного изморфизма в свое время позволил сократить время перечисления ДЛК порядка 9 с 3 месяцев на грид/кластере до 79 часов на 8-ядерном CPU, т.е. примерно в 1000 раз.
Построение классов эквивалентности для X-образных заполнений производилось следующим образом: для каждого такого заполнения выполнялись все возможные комбинации M-преобразований, в результате которых фиксировалось лексикографически минимальное заполнение. Для N=10 таких классов C[1], C[2], ... (или т.н. линеек сильно нормализованных КФ, сокр. СКФ) получается m(10)=67, для N=9 — m(9)=20, для меньших размерностей количество указано здесь: https://vk.com/wall162891802_1280. Общее число ДЛК в таком случае можно посчитать через классы изоморфизма X-образных диагональных заполнений как
|C[1]|*f[1] + |C[2]|*f[2] + ... + |C[m]|*f[m]
(соответствующая формула есть в опубликованной совместной статье), где
M[i]=|C[i]| — мощность соответствующего класса X-образных диагональных заполнений (т.н. кратность линейки),
f[i] — число ДЛК, получаемое заполнением любого из X-образных диагональных заполнений в i-й линейке полным перебором.
Для подсчета ДЛК данный подход весьма хорош. Однако для других задач (например, для поиска ДЛК с заданными свойствами, неразличимыми в рамках главного класса) он конечно лучше, чем просто перебор всех возможных нормализованных ДЛК, но и в то же время не спасает от повторов, т.к. в каждой линейке ДЛК с одними и теми же свойствами и одной и той же КФ будет обработан несколько раз подряд (с оговоркой на то, что для некоторых размерностей N существуют линейки максимально возможной кратности, в которых содержатся только КФы). Чтобы этого избежать, необходимо гарантированно обрабатывать по одному квадрату из каждого главного класса, т.е. сделать генератор КФ ДЛК.
Простейшей реализацией такого генератора может быть следующая: для всех линеек необходимо сформировать все дозаполнения до ДЛК, проверить каждое на то, является ли полученный квадрат КФ или нет, и отдать наружу только КФы. Однако темп КФ на выходе такого генератора будет невысок (несколько сотен — тысяч КФ/с), он будет лимитироваться не скоростными характеристиками генератора (сотни тысяч — миллионы ДЛК/с), а проверкой на КФ.
С использованием ESODLS схем темп КФ на выходе генератора можно повысить (на данный момент примерно в 5-10 раз). Несложно заметить, что применение ESODLS схем (число которых, напомню, совпадает с числом комбинаций M-преобразований и максимальной мощностью главного класса Cmax(N)) к выбранному X-образному заполнению с последующей нормализацией по главной диагонали может приводить к двум исходам:
(1) полученное X-образное заполнение будет совпадать с исходным;
(2) будет получено другое X-образное заполнение из того же класса эквивалентности, изоморфное исходному.
Пример 1: лексикографически минимальное X-образное заполнение линейки 2 ДЛК порядка N=8
0 . . . . . . 1
. 1 . . . . 0 .
. . 2 . . 3 . .
. . . 3 2 . . .
. . . 5 4 . . .
. . 6 . . 5 . .
. 7 . . . . 6 .
4 . . . . . . 7
путем примерения ESODLS CMS 8 трансформируется в
0 . . . . . . 1
. 2 . . . . 3 .
. . 3 . . 2 . .
. . . 1 0 . . .
. . . 7 6 . . .
. . 5 . . 4 . .
. 6 . . . . 5 .
4 . . . . . . 7
а после нормализации по главной диагонали — в
0 . . . . . . 3
. 1 . . . . 2 .
. . 2 . . 1 . .
. . . 3 0 . . .
. . . 7 4 . . .
. . 6 . . 5 . .
. 4 . . . . 6 .
5 . . . . . . 7
(другое X-образное заполнение из того же класса эквивалентности для линейки 2).
Пример 2: то же самое исходное X-образное заполнение
0 . . . . . . 1
. 1 . . . . 0 .
. . 2 . . 3 . .
. . . 3 2 . . .
. . . 5 4 . . .
. . 6 . . 5 . .
. 7 . . . . 6 .
4 . . . . . . 7
путем применения ESODLS CMS 40 трансформируется в
2 . . . . . . 3
. 3 . . . . 2 .
. . 0 . . 1 . .
. . . 1 0 . . .
. . . 7 6 . . .
. . 4 . . 7 . .
. 5 . . . . 4 .
6 . . . . . . 5
которое после нормализации по главной диагонали дает исходное X-образное заполнение
0 . . . . . . 1
. 1 . . . . 0 .
. . 2 . . 3 . .
. . . 3 2 . . .
. . . 5 4 . . .
. . 6 . . 5 . .
. 7 . . . . 6 .
4 . . . . . . 7
А раз так, то несложно показать, что для каждого из лексикографически минимальных представителей классов эквивалентности X-образных заполнений можно отобрать такие ESODLS схемы, применение которых приводит к исходу (1) и СКФ находится среди результатов их применения, причем чем выше кратность линейки M, тем число таких схем, равное Cmax/M, меньше. Соответственно при проверке ДЛК на КФность число выполняемых действий (сравниваемых на минимальность квадратов) сокращается с Cmax до Cmax/M - 1 (-1 потому, что применять тривиальную ESODLS CMS не имеет смысла, X-образное заполнение она не изменяет, отображая каждый элемент сам в себя), т.е. почти в M раз.
Например, для порядка N=8 максимально возможная мощность главного класса Cmax=1536, линейка 6 c лексикографически минимальным представителем
0 . . . . . . 1
. 1 . . . . 0 .
. . 2 . . 3 . .
. . . 3 5 . . .
. . . 2 4 . . .
. . 6 . . 5 . .
. 7 . . . . 6 .
4 . . . . . . 7
имеет кратность M=384, что позволяет выбрать Cmax/M = 1536/384 = 4 ESODLS схемы с номерами 0 (тривиальная), 90, 481 и 571, применение которых с последующей нормализацией гарантированно даст СКФ. Например, для квадрата
0 4 3 5 2 6 7 1
2 1 4 6 3 7 0 5
5 0 2 7 1 3 4 6
7 6 0 3 5 1 2 4
6 5 7 2 4 0 1 3
1 2 6 4 7 5 3 0
3 7 5 1 0 4 6 2
4 3 1 0 6 2 5 7
полученного в результате дозаполнения приведенного выше X-образного заполнения, применение указанных ESODLS схем даст следующее множество квадратов:
ESODLS CMS 90:
0 2 3 7 6 4 5 1
7 1 5 4 3 2 0 6
5 6 2 1 0 3 7 4
6 4 1 3 5 7 2 0
3 0 7 2 4 6 1 5
1 3 6 0 7 5 4 2
2 7 4 5 1 0 6 3
4 5 0 6 2 1 3 7
(СКФ)
ESODLS CMS 481:
0 2 7 4 3 6 5 1
3 1 5 6 2 7 0 4
5 0 2 1 7 3 4 6
7 6 4 3 5 0 1 2
6 3 0 2 4 1 7 5
1 4 6 7 0 5 2 3
2 7 3 5 1 4 6 0
4 5 1 0 6 2 3 7
ESODLS CMS 571:
0 6 5 7 2 4 3 1
2 1 3 4 7 6 0 5
1 5 2 0 6 3 7 4
6 4 7 3 5 1 2 0
5 3 0 2 4 7 1 6
7 2 6 1 0 5 4 3
3 7 4 5 1 0 6 2
4 0 1 6 3 2 5 7
содержащее СКФ.
Замечание. Применять указанные ESODLS схемы к квадратам той же линейки, но с другим составом диагоналей, нельзя: СКФ среди них не будет! Для таких квадратов сперва необходимо при помощи соответствующей ESODLS схемы привести квадрат к лексикографически минимальным диагоналям, а уже потом делать проверку на СКФ через отобранные ESODLS схемы. Данная особенность не встречается в генераторе КФ, однако может быть полезна при быстром построении СКФ по заданному ДЛК с произвольными диагоналями.
Указанные выше идеи были реализованы в коде, результаты его тестирования приведены ниже.
N=4
SCF line 1/2: 1 SCFs (0,0 ms, 61275,1 SCF/s)
SCF line 2/2: 0 SCFs (0,0 ms, 0,0 SCF/s)
Total DLS CFs = 1
=======================================================
N=5
SCF line 1/2: 1 SCFs (0,1 ms, 19818,1 SCF/s)
SCF line 2/2: 1 SCFs (0,1 ms, 19968,1 SCF/s)
Total DLS CFs = 2
=======================================================
N=6
SCF line 1/3: 2 SCFs (0,2 ms, 10086,9 SCF/s)
SCF line 2/3: 0 SCFs (0,0 ms, 0,0 SCF/s)
SCF line 3/3: 0 SCFs (0,0 ms, 0,0 SCF/s)
Total DLS CFs = 2
=======================================================
N=7
SCF line 1/3: 181 SCFs (56,7 ms, 3194,7 SCF/s)
SCF line 2/3: 530 SCFs (33,7 ms, 15733,9 SCF/s)
SCF line 3/3: 261 SCFs (93,9 ms, 2779,3 SCF/s)
Total DLS CFs = 972 (время работы — 0,5 c)
=======================================================
N=8
SCF line 1/20: 8148 SCFs (180177,0 ms, 45,2 SCF/s)
SCF line 2/20: 137801 SCFs (25985,4 ms, 5303,0 SCF/s)
SCF line 3/20: 135595 SCFs (73335,1 ms, 1849,0 SCF/s)
SCF line 4/20: 213166 SCFs (39104,8 ms, 5451,1 SCF/s)
SCF line 5/20: 10092 SCFs (78867,3 ms, 128,0 SCF/s)
SCF line 6/20: 270633 SCFs (19806,0 ms, 13664,2 SCF/s)
SCF line 7/20: 837748 SCFs (22605,8 ms, 37058,9 SCF/s)
SCF line 8/20: 405668 SCFs (26280,7 ms, 15435,9 SCF/s)
SCF line 9/20: 214433 SCFs (39575,8 ms, 5418,3 SCF/s)
SCF line 10/20: 193044 SCFs (35384,7 ms, 5455,6 SCF/s)
SCF line 11/20: 419434 SCFs (28089,9 ms, 14931,8 SCF/s)
SCF line 12/20: 437267 SCFs (29126,7 ms, 15012,6 SCF/s)
SCF line 13/20: 421525 SCFs (27504,3 ms, 15325,8 SCF/s)
SCF line 14/20: 51530 SCFs (98569,2 ms, 522,8 SCF/s)
SCF line 15/20: 414374 SCFs (26876,2 ms, 15417,9 SCF/s)
SCF line 16/20: 412695 SCFs (28551,4 ms, 14454,5 SCF/s)
SCF line 17/20: 135729 SCFs (25865,7 ms, 5247,5 SCF/s)
SCF line 18/20: 46301 SCFs (92697,2 ms, 499,5 SCF/s)
SCF line 19/20: 103873 SCFs (58465,7 ms, 1776,6 SCF/s)
SCF line 20/20: 4040 SCFs (103688,4 ms, 39,0 SCF/s)
Total DLS CFs = 4873096 (время работы — 17,5 минут, ранее (см. http://evatutin.narod.ru/evatutin_co_dls_cfs_cnt.pdf) на это ушло 2 суток расчетов на грид, выигрыш в скорости обработки около 41000 раз).
Замечание. Код генератора на данный момент сильно не оптимизирован, можно сделать и быстрее...
Таким образом, сделано две важные вещи. Первая: окончательно понято, как делать генераторы СКФ на базе X-образных заполнений с использованием ESODLS схем (некоторые думают, что я единственный, кто с легкостью понимает и воспроизводит теоретические построения whitefox'а — это не так :). Вторая: получен рабочий код генератора КФ ДЛК произвольного порядка N, который можно использовать в дальнейших экспериментах на грид. Даже без оптимизации он весьма эффективен по сравнению с кодом на базе перечисления всех нормализованных ДЛК.