Форум

Пожалуйста или Регистрация для создания записей и тем.

Исследование свойств диагональных латинских квадратов в проектах добровольных распределенных вычислений и не только...

НазадСтраница 29 из 190Далее

Последовательности

расширены путем добавления членов a(11)-a(15) в соответствии с https://vk.com/wall162891802_1106

Я получаю задания spstarter 3.22   c приблизительным оставшимся временем "2d 22:43:52" но выполняются они менее чем за час.

 

Выше (см. https://vk.com/wall162891802_1229) было введено понятие обобщенной M-симметрии — симметрии (автоморфизма), уменьшающей мощность главного класса ДЛК. Наличие данных симметрий очень просто и эффективно можно проверять путем применения к заданному ДЛК ESODLS CMS схем (см. https://vk.com/wall162891802_1188). А раз так, интересно посмотреть, что у нас с квадратами из списка КФ ОДЛК, включающего на данный момент в своем составе почти 10 млн. КФ, построение которого активно продолжается в проекте Gerasim@Home (http://gerasim.boinc.ru). Анализ всех КФ занял несколько суток на Core i7 4770 в 5 потоков, по его итогам можно сделать следующие выводы.

1. Среди КФ ОДЛК порядка N=10, найденных на данный момент в проекте, существует лишь два типа квадратов: без M-симметрий и с одной M-симметрией. КФ с бОльшим числом M-симметрий среди находок проекта не обнаружено. Для других размерностей это не так (например, вот тут https://vk.com/wall162891802_1229 приведен ДЛК порядка N=5, которому соответствуют сразу 7 M-симметрий). Для общего определения обобщенных симметрий (автоморфизмов) whitefox'ом ранее было показано, что среди находок от плоскостной симметрии (напомню, полным перебором выбрана полностью) существуют квадраты с множеством обобщенных симметрий, но M-симметрия в их составе только одна.

2. ДЛК порядка N=10, обладающие одной M-симметрией, имеют мощность главного класса равную 7680 (в два раза меньше максимально возможной для данного порядка N). В качестве примера можно привести любой квадрат с плоскостной симметрией, например:

0 1 2 3 4 5 6 7 8 9
1 2 0 4 3 6 5 9 7 8
2 0 3 5 8 1 4 6 9 7
4 6 9 7 1 8 2 0 3 5
9 7 8 6 5 4 3 1 2 0
3 4 7 8 0 9 1 2 5 6
6 9 4 1 7 2 8 5 0 3
7 8 5 0 6 3 9 4 1 2
5 3 1 9 2 7 0 8 6 4
8 5 6 2 9 0 7 3 4 1

Это позволяет наложить ограничения

A299783(10) <= 7680
A299785(10) <= 7680 * 10! = 27869184000

на 10-е члены рядов, описывающих минимально возможную мощность главных классов ДЛК.
Дважды симметричные ДЛК https://oeis.org/A287650 (которые, напомню, не существуют для размерности N=10) по определению должны обладать как минимум двумя M-симметриями, соответствующими отражениям квадрата по горизонтали и вертикали.

3. Для всех ESODLS CMS, с помощью которых задаются найденные M-симметрии, структура мультимножества длин циклов одна и та же: {2:50}. Другим ESODLS CMS с другими структурами циклов находки не соответствуют. То ли их нет в принципе, то ли мы их еще не нашли... Что-то подобное кажется когда-то давно на старом форуме публиковал whitefox про эквивалентность плоскостной и центральной симметрий, но проверить это не представляется возможным ввиду отсутствия как whitefox'а, так и старого форума. Видимо к данному вопросу удалось подойти с другой стороны: с использованием ESODLS CMS.

Открытый вопрос: существует ли ДЛК порядка 10 с числом M-симметрий более одной и, соответственно, мощностью главного класса менее 7680?

Для исследования наличия M-симметрий у ОДЛК порядка 9 возьмем известные нам списки КФ ОДЛК, полученные от центральной симметрии и строчно перестановочные ОДЛК из проекта RakeSearch.

1. Центральная симметрия и ОДЛК в составе соответствующих комбинаторных структур.

0 1 2 3 4 5 6 7 8
2 4 3 0 7 6 8 1 5
6 2 8 5 3 4 7 0 1
4 6 7 1 8 2 3 5 0
1 5 4 7 6 0 2 8 3
7 8 1 4 5 3 0 6 2
3 7 0 2 1 8 5 4 6
8 3 5 6 0 7 1 2 4
5 0 6 8 2 1 4 3 7

Комбинаторная структура: 113616N675264M177C
Число ОДЛК: 360
Число M-симметрий: 31 (больше на данный момент не найдено)
1. Automorphic schema 0 (тривиальная)
2. Automorphic schema 91
3. Automorphic schema 109
4. Automorphic schema 118
5. Automorphic schema 254
6. Automorphic schema 261
7. Automorphic schema 331
8. Automorphic schema 336
9. Automorphic schema 398
10. Automorphic schema 405
11. Automorphic schema 483
12. Automorphic schema 568
13. Automorphic schema 616
14. Automorphic schema 627
15. Automorphic schema 733
16. Automorphic schema 742
17. Automorphic schema 829
18. Automorphic schema 838
19. Automorphic schema 904
20. Automorphic schema 915
21. Automorphic schema 963
22. Automorphic schema 1048
23. Automorphic schema 1070
24. Automorphic schema 1077
25. Automorphic schema 1195
26. Automorphic schema 1200
27. Automorphic schema 1310
28. Automorphic schema 1317
29. Automorphic schema 1357
30. Automorphic schema 1366
31. Automorphic schema 1440
32. Automorphic schema 1531
Мощность главного класса: 48 (меньше на данный момент не найдено)
Входит в состав 81 клики из 3 и 6 нормализованных ВОДЛК, например:

Clique 1 (3 items):
DLS 1: 012345678243076815628534701467182350154760283781453062370218546835607124506821437
DLS 2: 012345678138750426875162340621874035547613802264087153406531287350428761783206514
DLS 3: 012345678856401237463027185384250761631872540507618324125786403748563012270134856

CF 1: 012345678243076815628534701467182350154760283781453062370218546835607124506821437
CF 2: 012345678120468735406153287351874062647512803534087126875621340268730451783206514

и

Clique 21 (6 items):
DLS 1: 012345678243076815628534701467182350154760283781453062370218546835607124506821437
DLS 2: 012345678856704231307681524721836405643218750465072183584120367178563042230457816
DLS 3: 012345678370218546781453062835607124506821437628534701243076815467182350154760283
DLS 4: 012345678187650324534026187270564813821437506356781240465802731703218465648173052
DLS 5: 012345678635182407476810253583271046768054312104627835857463120240736581321508764
DLS 6: 012345678764821053845762310358410762280673145537108426106537284621054837473286501

CF 1: 012345678243076815628534701467182350154760283781453062370218546835607124506821437
CF 2: 012345678124678305431806527678524013805431762346187250587062431763250184250713846

Существуют и другие квадраты в данном списке с числом M-симметрий, равным 31.

Структуры мультимножеств длин циклов для ESODLS CMS схем, образующие M-симметрии, существенно богаче размерности 10:
* Schema 3 - 25 times - {1:1, 4:20}
* Schema 40 - 62 times - {1:1, 2:40}
* Schema 101 - 1 times - {1:9, 2:36}
* Schema 108 - 2 times - {1:1, 8:10}

2. Строчно перестановочные ОДЛК из проекта RakeSearch.

Также встречаются ОДЛК с числом M-симметрий 31 и мощностью главного класса 48, квадратов с большим числом M-симметрий и с меньшей мощностью главного класса не найдено. Новых структур мультимножеств длин циклов для ESODLS CMS схем не выявлено.

Найденные результаты позволяют наложить следующие ограничения на 9-е члены числовых рядов

A299783(9) <= 48
A299785(9) <= 48 * 9! = 17418240

определяющих минимальную мощность соответствующих главных классов ДЛК.

Цитата: kotenok2000 от 09.06.2020, 12:14

Я получаю задания spstarter 3.22   c приблизительным оставшимся временем "2d 22:43:52" но выполняются они менее чем за час.

 

Возможно, что в их атрибутах прописана завышенная оценка объёма вычислений. Но это лучше, чем заниженная. :)

В проекте найдено 10 млн. канонических форм (КФ) ортогональных диагональных латинских квадратов (ОДЛК) порядка 10. На это в общей сложности потребовалось 1186 дней. Спасибо всем кранчерам за поддержку, считаем дальше!

ale4316 отреагировал на эту запись.
ale4316

По итогам короткой серии экспериментов, связанных попыткой разработки нового простого преобразования с заменой K трансверсалей в ОДЛК (см. https://vk.com/wall162891802_1227), можно подвести первые итоги:

* замена 2 трансверсалей — новых КФ ОДЛК нет вообще;
* замена 3 трансверсалей — +9949 новых КФ ОДЛК (9946 КФ однушек и 3 КФ двушек), "цена" (затраты вычислительного времени) получения новых КФ таким образом — 16082 с/КФ;
* замена 4 трансверсалей — +2260 новых КФ ОДЛК (все однушки), "цена" получения новых КФ таким образом — 4424 с/КФ;
* замена 5 трансверсалей — +2078 новых КФ ОДЛК (2072 КФ однушек и 6 КФ двушек), "цена" получения новых КФ таким образом — 4812 с/КФ.

Перечисленным выше находки не ограничиваются, приведены лишь новые КФ. Кроме них было найдено множество повторных, уже найденных ранее путем применения других простых преобразований. Таким образом, из проведенной серии экспериментов можно сделать вывод, что простое преобразование замены K трансверсалей принципиально не лучше разработанных ранее, а значит его практическое использование не является целесообразным. Те же самые новые КФ ОДЛК можно получить и другими способами по схеме генератор->канонизатор с меньшими затратами вычислительного времени.

Похоже на то, что сервер немножечко упал...

Zabaikalec2010 отреагировал на эту запись.
Zabaikalec2010
Цитата: AenBleidd от 19.06.2020, 12:50

Похоже на то, что сервер немножечко упал...

Вроде SerVal оперативно вернул все на на место... :)

Окрестности обобщенных симметрий в парастрофических срезах

Как уже было неоднократно отмечено ранее, ДЛК считается обобщенно симметричным, если для всех его ячеек выполняются следующие соотношения:

A[x][y]=v, A[x’][y’]=v’

x’=Px(x),
y’=Py(y), (1)
v’=Pv(v),

где [x][y] и [x'][y'] — выбранная пара ячеек, v и v' — стоящие в них значения, а Px, Py и Pv — перестановки, определяющие симметрию (или, что в данном случае то же самое — автоморфизм). Важной является не сама перестановка, а ее мультимножество длин циклов. Для размерности N=10 существует 42 различных типа перестановок, соответствующих различным мультимножествам, что соответствует плоскости из 42*(42+1)/2=903 обобщенных симметрий. Частично обобщенно симметричным ДЛК называется такой ДЛК, у которого M ячеек подчиняется соотношениям (1), а остальные ячейки заполнены полным перебором до получения соответствующих корректных ДЛК. Частично обобщенно симметричные ДЛК образуют окрестность соответствующей симметрии с удалением M. Не для всех 903 обобщенных симметрий существуют соответствующие им ДЛК, однако окрестности существуют у всех. Интересные находки (редкие комбинаторные структуры, псевдотройки с высокой ХО) по большей части были найдены либо для обобщенно симметричных ДЛК, либо в окрестностях обобщенных симметрий. В настоящее время в проекте идет активное исследование окрестностей обобщенных симметрий с удалениями M in {80, 70, 60, 50}, на данный момент пройдено 487 окрестностей, осталось пройти еще 416, на что потребуется не менее года при текущей реальной производительности проекта. Исследование свойств ОДЛК в окрестностях продолжается, но первые выводы можно сделать уже сейчас.

1. Если обобщенная симметрия существует, то на небольшом удалении от нее находится много интересных комбинаторных структур (как минимум, двушек, но не только). Так, без теоретических выкладок (тут у нас спец whitefox :), можно легко выявить существующие обобщенные симметрии ((1,31), (4,31) и др.). Например, в окрестности (1,31)-симметрии на удалении M=80 было найдено 2386 двушек, в окрестности (4,31)-симметрии — 2995 двушек, а в окрестности несуществующей симметрии (3,22) — ни одной двушки (иногда бывает 1—2).

2. Если обобщенная симметрия существует, то и на бОльших удалениях M in {70, 60, 50} также находится множество интересных находок и данные окрестности представляют интерес. При M<50 свойства симметрии у соответствующих ДЛК практически пропадают, соответствующую "дальнюю" окрестность исследовать не интересно, результаты не отличаются от просто случайного перебора ДЛК.

3. Для несуществующей обобщенной симметрии находки в основном обеспечиваются окрестностями с M=50 и M=60 (на них же тратится основная часть вычислительного времени), для удалений M=70 и M=80 находок как правило мало. Для существующей симметрии все в точности наоборот.

4. Редко встречаются интересные находки и в окрестностях несуществующих симметрий (как в известном анекдоте: так (вроде бы) не бывает: симметрии нет, а окрестность есть :), оказывается — бывает, правда не очень часто) поэтому их тоже интересно исследовать. Например, в окрестности (24,24)-симметрии совсем недавно были найдены 2 звезды 1:3, 2 линии-4 и 4-КФный цикл-4, а окрестность (14,39)-симметрии подарила нам еще одну четверку, которых не было очень давно. Большинство окрестностей несуществующих симметрий пустые (содержат однушки и двушки как и при обычном случайном поиске) и не представляют особого интереса.

С подачи whitefox'а определение обобщенных симметрий можно распространить на другие парастрофические срезы. Напомню, что парастрофические преобразования (или просто парастрофии) — это перестановки в тройке [x, y, v]. Например, перестановка [x, y, v] -> [y, x, v] эквивалентна транспонированию квадрата, когда строки (х) и столбцы (y) меняются местами. Для множества из 3 объектов можно построить 3!=6 перестановок, т.е. получить 6 парастрофических преобразований. На данный момент они уже используются нами (и довольно давно) в канонизаторе, а вот при описании окрестностей обобщенных симметрий мы их до этого не использовали. Восполним этот пробел! Итак, будем говорить, что кроме текущего парастрофического среза [Px, Py, Pv] существует еще 3!-1=5 срезов, в которых обобщенная симметрия может быть описана похожим образом как

A[x][y]=v, A[x’][y’]=v’

x’=P1(x),
y’=P2(y), (2)
v’=P2(v)

с тем отличием, что в текущем эксперименте [P1, P2, P3] = [Px, Py, Pv], а в других срезах будет использована другая перестановка перестановок (о как завернулось!), описывающих симметрию. Для определенности:

1 срез — [P1, P2, P3] = [Px, Py, Pv]
2 срез — [P1, P2, P3] = [Px, Pv, Py]
3 срез — [P1, P2, P3] = [Py, Px, Pv]
4 срез — [P1, P2, P3] = [Py, Pv, Px]
5 срез — [P1, P2, P3] = [Pv, Px, Py]
6 срез — [P1, P2, P3] = [Pv, Py, Px]

В соответствии с новым определением можно сделать соответствующие новые генераторы ДЛК, что и было сделано. Теперь можно смотреть не только в первый парастрофический срез обобщенных симметрий и их окрестностей, но и еще в 5. С одной стороны это хорошо, но... До ухода на карантин whitefox публиковал где-то информацию о том, что такие симметрии подчинены уже известным нам (если есть обычная, обобщенная в первом срезе, значит может быть и такая, новая, через парастрофии в других срезах), а значит для самих симметрий новых находок быть не должно. Проверим... Однако что касается окрестностей симметрий, то тут без эксперимента что-то определенное сказать сложно, поэтому будем исследовать! На полное исследование всех 903 обобщенных симметрий и их окрестностей на удалениях M in {50, 60, 70, 80} в одном парастрофическом срезе необходимо 2-3 года расчетов на гриде, а у нас 5,5 неисследованных срезов... Поэтому на первом этапе длительностью в несколько месяцев проведем разведку окрестностей обобщенных симметрий в парастрофических срезах на удалениях M in {70, 80}, это относительно быстро. Найдем интересные окрестности, их внимательно изучим. А потом, если в этом останется необходимость, возможность и желание, организуем долгое многолетнее исследование окрестностей на бОльших удалениях M in {50, 60}.

В проект добавлена новая версия расчетного модуля 3.2.4 и первые 40 тыс. пробных WU'шек. Их цель — пощупать уже известные нам окрестности симметрий (1,31) — существует — и (3,22) — не существует — в первом парастрофическом срезе с использованием другой математики и другого генератора ДЛК (в него внесены косметические изменения, связанные с формированием ненормализованных ЛК, в то время как текущий эксперимент сперва планировался для нормализованных ДЛК, потом был адаптирован под нормализованные ЛК и канонизатор, а теперь вот генератор сделан денормализованным, так его проще закодить по ряду причин). Если все будет нормально (а по первым прикидкам за пол дня расчетов так оно и есть), то следом будет добавлено большое количество WU'шек для последовательного исследования 5 новых парастрофических срезов. Параметры WU'шек те же самые, что и раньше, считаем...

hoarfrost и ale4316 отреагировали на эту запись.
hoarfrostale4316
НазадСтраница 29 из 190Далее
BOINC.RU