Форум

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

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

НазадСтраница 23 из 191Далее

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

Данное значение для ДЛК порядков 1 <= N <= 8 известно, см. https://oeis.org/A299784. Оно было получено нами ранее путем полного перебора всех ДЛК заданного порядка и определения для них максимальной мощности класса изоморфизма (см. статью E. Vatutin, A. Belyshev, S. Kochemazov, O. Zaikin, N. Nikitina, Enumeration of isotopy classes of diagonal Latin squares of small order using volunteer computing, Communications in Computer and Information Science. Vol. 965. Springer, 2018. pp. 578-586., https://doi.org/10.1007/978-3-030-05807-4_49). С другой стороны, отталкиваясь от максимального числа M-преобразований, используя которые можно получить всех представителей главного класса, известно ограничение сверху на мощность главного класса, определяемое по формуле

a(N) <= 2^m * m! * 4, m = floor(N/2), floor(.) — округление вниз, оно же усечение, оно же отбрасывание дробной части.

Соответственно, зная верхнюю оценку мощности главного класса, можно подобрать квадрат без обобщенных симметрий (автоморфизмов), для которого мощность главного класса будет равна верхней оценке (на самом деле это достаточно просто, т.к. отсутствием обобщенных симметрий (автоморфизмов) могут похвастаться абсолютное большинство ДЛК). При этом достаточно любого квадрата, полный перебор всех тут не нужен. Для размерностей N=9 и N=10 с использованием нашей коллекции квадратов и соответствующего ПО сделать это достаточно просто.

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

N=9, мощность главного класса 1536 = 2^4 * 4! * 4.

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

N=10, мощность главного класса 15360 = 2^5 * 5! * 4.

Найденные значения 1536 и 15360 позволяют расширить указанную выше последовательность A299784.

Умножая найденные значения соответственно на 9! и 10!, можно получить соответствующие значения 557383680 и 55738368000 для расширения последовательности A299787.

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

Последовательности https://oeis.org/A299784 и https://oeis.org/A299787 расширены на размерности N=9 и N=10 в соответствии с https://vk.com/wall162891802_1103.

Решил слить все файлы в одну кучу. Но 14ом млн ждал облом. Стал переводить в списке. Надеялся дотянуть до 20ти. Увы.

Удалось только до 18,8.

Можно было своими старыми программами, но уж больно они медленные. Это окончательно поставило точку в создании "общей" базы.

Хотя еще есть возможность через представителей. Для них кол-во в два раза меньше.

Буду для для архива создавать блоки по 10 млн.

Через месяц будут два блока по 10 млн

 

Нашел представителей, получил 8 млн. Отлично. Теперь с КФ можно не возиться.

Есть еще запас на год. А потом в архив по 10 млн.

И плотно работать с уникальными представителями - работа с ними занимает минуты и все ценное не ускользнет.

Осталось переписать скрипты на новую обработку.

 

SODLS мы посчитали, ESODLS тоже, на очереди ASODLS, BSODLS, СSODLS, ... :). Ну а если серьезно, то в некоторых источниках попадается класс квадратов, именуемых Doubly Self-Orthogonal Diagonal Latin Squares, сокр. DSODLS. По определению такие квадраты самоортогональных от двух преобразований: транспонирование от главной и от побочной диагонали. Число соответствующих ДЛК никто не считал, восполним этот пробел. Это несложно сделать, отталкиваясь от уже известных нам списков SODLS, в которых необходимо отобрать такие SODLS, которые самоортогональны от двух транспонирований, а не только от одного. В итоге получаются следующие числовые ряды, не представленные в OEIS:

* 1, 0, 0, 1, 1, 0, 2, 8, 88, 0 — число главных классов DSODLS (N<11);
* 1, 0, 0, 2, 4, 0, 64, 1152, 28608, 0 — число нормализованных DSODLS (N<11);
* 1, 0, 0, 48, 480, 0, 322560, 46448640, 10381271040, 0 — число DSODLS (N<11).

Несложно заметить, что по определению число DSODLS <= числа SODLS для каждого из типов квадратов.

Определение DSODLS в перспективе можно расширить и на другие канонические CMS схемы путем введения в рассмотрения ДЛК, от которых получаются ОДЛК путем применения к ним соответствующих канонических CMS, дающих ОДЛК из того же главного класса. DSODLS соответствуют две схемы, некоторым другим ESODLS может соответствовать большее число схем.

О максимальной мощности главных классов ДЛК порядка 11<=N<=15.

Максимальную мощность главных классов ДЛК (см. ряд https://oeis.org/A299784 в OEIS) мы знаем до размерности N=10 включительно. Мощности 1<=N<=8 были определены нами полным перебором при подсчете числа главных классов (см. статью E. Vatutin, A. Belyshev, S. Kochemazov, O. Zaikin, N. Nikitina, Enumeration of isotopy classes of diagonal Latin squares of small order using volunteer computing, Communications in Computer and Information Science. Vol. 965. Springer, 2018. pp. 578-586. https://link.springer.com/chapter/10.1007/978-3-030-0..). Мощности для порядков N=9 и N=10 были посчитаны недавно путем нахождения ДЛК без обобщенных симметрий/автоморфизмов (благо таких квадратов абсолютное большинство), см. краткое описание эксперимента https://vk.com/wall162891802_1103. С ДЛК порядка N>10 мы до этого практически не работали... Почему? Кто нам мешает? Никто, нехватка времени! А учитывая текущую эпидемиологическую истерику мирового масштаба, время есть! :) Итак, попытаемся посчитать максимальную мощность главных классов на большие размерности следующим образом: будем брать ДЛК выбранной размерности, строить его главный класс и проверять, совпадает ли его мощность с верхней оценкой. Результаты эксперимента приведены ниже: указан исследуемый ДЛК, его размерность, найденная (максимальная) мощность его главного класса, время вычислительного эксперимента и, для случаев большой размерности, необходимый объем RAM.

N=11, MaxCard4MainClass=15360, 3 сек

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

N=12, MaxCard4MainClass=184320, 12 мин

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

N=13, MaxCard4MainClass=184320, 16 мин

0 1 2 3 4 5 6 7 8 9 10 11 12
10 2 11 1 5 3 12 4 6 7 8 0 9
8 10 1 11 0 4 3 12 5 6 2 9 7
12 5 3 4 8 11 7 9 0 1 6 2 10
6 8 9 7 3 12 11 10 4 0 1 5 2
2 0 7 10 11 6 9 3 12 4 5 8 1
4 6 8 2 12 9 5 11 1 3 7 10 0
1 12 0 6 10 7 2 8 9 5 11 3 4
3 9 4 12 6 10 8 2 7 11 0 1 5
5 4 6 8 9 2 0 1 11 10 12 7 3
11 3 10 0 7 1 4 5 2 12 9 6 8
7 11 5 9 1 8 10 0 3 2 4 12 6
9 7 12 5 2 0 1 6 10 8 3 4 11

N=14, MaxCard4MainClass=2580480, 53 ч, 1.3 ГБ RAM

0 1 2 3 4 5 6 7 8 9 10 11 12 13
11 2 12 1 6 3 8 13 4 5 7 9 0 10
8 10 1 12 0 4 3 5 13 11 6 2 9 7
5 12 11 4 13 7 0 2 10 3 1 6 8 9
6 8 10 13 3 12 9 0 5 4 2 7 11 1
7 4 13 9 12 6 10 11 3 2 0 8 1 5
13 3 7 2 11 9 5 6 0 12 4 1 10 8
9 6 3 0 2 13 7 8 11 1 12 10 5 4
10 9 6 5 1 8 13 12 7 0 11 3 4 2
3 13 4 11 5 1 12 9 2 10 8 0 7 6
2 0 5 10 7 11 4 1 6 8 9 13 3 12
4 5 9 7 8 10 11 3 1 6 13 12 2 0
1 11 8 6 9 0 2 10 12 7 5 4 13 3
12 7 0 8 10 2 1 4 9 13 3 5 6 11

N=15, MaxCard4MainClass=2580480, 81 ч, 1.5 ГБ RAM

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
12 2 11 1 6 3 7 13 14 4 5 8 9 0 10
9 11 1 12 0 4 3 6 5 13 14 7 2 10 8
3 10 13 4 11 8 0 9 2 5 12 1 14 6 7
1 9 14 7 3 13 11 5 0 12 4 6 10 8 2
14 12 10 5 13 6 2 4 11 3 0 9 8 7 1
10 4 7 8 14 12 5 11 6 0 2 13 1 9 3
6 0 3 2 7 9 14 8 12 1 11 10 13 4 5
8 3 0 11 10 14 9 1 7 2 13 4 5 12 6
2 6 4 13 8 7 12 3 9 10 1 14 0 5 11
7 8 6 0 5 11 10 12 13 14 9 2 3 1 4
13 7 5 10 2 0 8 14 1 6 3 12 4 11 9
4 14 12 6 9 1 13 10 3 8 7 5 11 2 0
5 13 8 9 1 2 4 0 10 11 6 3 7 14 12
11 5 9 14 12 10 1 2 4 7 8 0 6 3 13

Таким образом, ряд A299784 может быть дополнен следующими значениями: 15360, 184320, 184320, 2580480, 2580480.

Очень похоже на то, что для всех размерностей N>6 a(N) = 2^m * m! * 4, m=floor(N) благодаря существованию ДЛК без обобщенных симметрий/автоморфизмов.

Умножая полученные значения на N!, получаем соответствующее расширение для ряда https://oeis.org/A299787: 613122048000, 88289574912000, 1147764473856000, 224961836875776000, 3374427553136640000.

Что дальше? Для расчета следующих двух членов ряда, предположительно равных 41287680 каждый, потребуется построить 41287680 ДЛК в составе соответствующего главного класса и проверить их на уникальность. Для этого потребуется параллельная вычислительная система, 54 дня (при линейной экстраполяции, возможно больше) на построение ДЛК, и не менее 9 и 11 ГБ RAM/HDD соответственно для хранения ДЛК.

 

А почему на графиках так резко упала вычислительная мощность у проекта:  https://classic.boincstats.com/en/stats/64/project/detail/credit

 

Цитата: Yura12 от 23.03.2020, 08:03

 

А почему на графиках так резко упала вычислительная мощность у проекта:  https://classic.boincstats.com/en/stats/64/project/detail/credit

 

Видимо потому, что закончилось соревнование

Цитата: Yura12 от 23.03.2020, 08:03

 

А почему на графиках так резко упала вычислительная мощность у проекта:  https://classic.boincstats.com/en/stats/64/project/detail/credit

 

Вот здесь - ещё виднее: http://gerasim.boinc.ru/StatsPage/FloatingPointSpeed.aspx

Сейчас, средняя нагрузка на процессор ~15%. Пиковая - 35%.

 

В проекте практически завершена обработка канонических ESODLS схем со структурой циклов {1:10, 2:45}. Случайным перебором выбраны практически все КФ ОДЛК соответствующего типа в следующих экспериментах:

* exp404 — было найдено 101 новая КФ из 2887 найденных (сокр. 101/2887);
* exp405 — 210/1698;
* exp406 — 401/5468;
* exp407 — 269/3225;
* exp408 — 20/760;
* exp674 — 14/87.
Итого: 1015/14125.

Дальше идут сплошь повторы КФов, дальнейший поиск в данных экспериментах нецелесообразен. Чтобы убедиться, что никаких других КФ ESODLS, соответствующих каноническим схемам, точно нет, необходимо сделать полный перебор (в перспективе).
Далее поиск ESODLS будем продолжать в эксперименте e674, из которого помимо некорректных схем (см. https://vk.com/wall162891802_1082) теперь еще исключены уже обработанные канонические схемы. Версия расчетного модуля изменена на 3.1.4, первая партия WU'шек добавлена, кворум — 1, дедлайн — 7 дней, время счета — 20 минут.

ale4316 и citerra отреагировали на эту запись.
ale4316citerra
НазадСтраница 23 из 191Далее
BOINC.RU