Исследование свойств диагональных латинских квадратов в проектах добровольных распределенных вычислений и не только...
Подсчет главных классов пустышек порядка 1-8
ДЛК делятся на два не пересекающихся класса: у одних из них есть ортогональные им ДЛК, у других — нет. Последних, именуемых иногда пустышками, абсолютное большинство. Число и тех, и других мы уже считали:
* для ДЛК общего вида — A274806(n) = A305571(n) + A305569(n);
* для нормализованных по первой строке ДЛК — A274171(n) = A305570(n) + A305568(n).
Однако есть еще и главные классы... По какой-то причине число главных классов ДЛК с ОДЛК уже посчитано ранее, а вот главные классы пустышек мы своим вниманием обошли. А раз так, восполним этот недостаток. Их количество можно определить путем вычитания числа главных классов ДЛК с ОДЛК из общего числа главных классов ДЛК того же порядка, однако вместо этого поступим по-другому: с использованием генератора КФов сформируем все КФы, а затем среди них найдем КФы-пустышки и посчитаем их количество. Так можно проверить и теоретические положения, и новый генератор. В результате получен следующий числовой ряд, не представленный в OEIS:
0, 0, 0, 0, 1, 2, 967, 4871991
Расчет значений до N<=7 выполняется практически мгновенно, на выяснение значения для N=8 потребовался 1 час работы Core i7 4770 в 1 поток, для расширения ряда вправо на размерность N=9 нужен грид. Для полученного ряда выполняется соотношение, аналогичное приведенным выше:
A330391(n) + ТекущийРяд(n) = A287764(n).
Теоретические положения верны, новый генератор КФов работает исправно.
В подпроект ODLS BS проекта Gerasim (http://gerasim.boinc.ru) добавлена новая версия расчетного модуля 1.1.1 и ~630 тыс. WU'шек эксперимента exp774, целью которых является подсчет числа главных классов ДЛК порядка 9. Напомню, что данное число, равное 3292326155394 (член a(9) последовательности https://oeis.org/A287764), мы знаем с лета прошлого года по итогам расчета, выполненного в проекте на базе кода, разработанного whitefox'ом. В текущем эксперименте мы проверим новый генератор СКФ на базе ESODLS, попытаемся подтвердить ранее найденное число в ходе независимого расчета и попутно подсчитаем другим способом число нормализованных ДЛК порядка 9 (член a(9) последовательности https://oeis.org/A274171). Кворум — 2, дедлайн — 7 дней, время счета WU'шки — до 20 минут, считаем...
PS. Есть подозрение, что небольшая часть WU'шек может считаться в несколько раз дольше основной массы, однако посмотрим... За несколько часов счета мне таких пока не попалось, как и в ходе пристрелочных замеров перед запуском эксперимента на грид.
В подпроект ODLS BS проекта Gerasim@Home (http://gerasim.boinc.ru) добавлена новая версия расчетного модуля 1.1.2, в которой повышена скорость обработки ряда линеек (на тестовой размерности N=8 линейка 1 с высокой кратностью обрабатывается в 21 раз быстрее, линейка 2 средней кратности — в 1,55 раза быстрее). Эта оптимизация, повышающая скорость обработки, надеюсь не последняя, версии расчетного модуля могут меняться в ближайшей перспективе, по каждому изменения отдельно отписываться не буду.
По итогам конференции Information, Computation, and Control Systems for Distributed Environments (ICCS-DE) 2020 (https://iccs-de.icc.ru/en/), прошедшей в Иркутске 6-7 июля, опубликован сборник статей, в котором есть статья
Vatutin E., Nikitina N., Belyshev A., Manzyuk M. On polynomial reduction of problems based on diagonal Latin squares to the exact cover problem (http://ceur-ws.org/Vol-2638/paper26.pdf)
В ней приведены бинарные матрицы, которые используются для полиномиального сведения ряда задач на базе латинских квадратов к задаче о точном покрытии (exact cover) с целью ее решения с использованием алгоритма танцующих связей (DLX). Напомню, что наиболее быстрым способом поиска ОДЛК общего вида является поиск на базе метода Эйлера-Паркера (https://ru.wikipedia.org/wiki/Метод_Эйлера_—_Паркера), при практической программной реализации которого построение множества трансверсалей и нахождение подмножеств из N непересекающихся трансверсалей наиболее быстро реализуются как раз через DLX (более быстрые способы поиска ОДЛК общего вида нам не известны).
Олег Заикин раскопал статью коллеги
https://arxiv.org/abs/1506.01577
В ней дается асимптотическая оценка числа трансверсалей в ЛК. Мы напрямую такими вещами не занимаемся, однако данное исследование лежит совсем рядом с нашими работами (например, см. https://oeis.org/A287644 и https://oeis.org/A287648, дальше по ссылкам). Добавил ссылки на статью коллеги и соотечественника в OEIS
* https://oeis.org/A091323;
* https://oeis.org/A090741.
Так ее видимость среди профильного сообщества будет выше... 
Опубликована статья
Ватутин Э.И., Белышев А.Д. Определение числа самоортогональных (SODLS) и дважды самоортогональных диагональных латинских квадратов (DSODLS) порядков 1–10 // Высокопроизводительные вычислительные системы и технологии. Т. 4. № 1. 2020. С. 58–63. (http://evatutin.narod.ru/evatutin_sodls_and_dsodls_1_to_10.pdf)
В ней подробно рассказано о том, как были получены числовые ряды для SODLS и DSODLS порядков 1—10, с указанием использованных источников данных. Очень хочется надеяться, что вопрос с приоритетами в данной области устаканится и больше возникать не будет.
PS. Францис Гаспалу результаты своих вычислений в открытом виде так и не опубликовал, хотя в ходе переписки он обещал это сделать на своей страничке. На страничке Гарри Уайта приведена только часть числовых рядов, но без подтверждающих их списков находок (КФ ОДЛК соответствующего типа). От соавторства в опубликованной статье оба отказались, хотя я им предлагал, на мой взгляд зря... На мой взгляд было бы весьма интересно ознакомиться с подходами, которые были использованы ими для расчета числовых значений, содержащихся в нашей статье. Главный итог: цифры совпали, а значит с большой долей вероятности они являются верными, OEIS получила еще несколько числовых рядов, связанных с ДЛК.
Некоторые задания ODLS BS считаются часов по 11, без чекпоинтов это жесть.
Зависимость числа линеек СНДЛК от порядка ДЛК N добавлена в OEIS:
Цитата: ale4316 от 20.07.2020, 20:42Некоторые задания ODLS BS считаются часов по 11, без чекпоинтов это жесть.
Начиная с версии 1.12 расчетного модуля таких быть не должно. Такие, например, были в линейке 1 (WU'шки с именами *_line1_*), но после оптимизации кода они начали считаться за время порядка 10 минут. Если вдруг такие попадаются где-то еще на версиях 1.12 и 1.13, дайте мне знать точное имя WU'шек, буду смотреть...
PS. Это связано с тем, что для проверки линеек СНДЛК низкой кратности приходится применять больше ESODLS схем, чем для линеек с высокой кратностью (в идеале, для линеек максимально возможной кратности эта проверка не требуется вообще, а каждое дозаполнение до ДЛК дает новую КФ). Сама проверка простейшая, но их выполняется много и они все тормозят (hotspot). На данный момент этот кусок кода по скорости сделан близким к идеалу, поэтому если такие WU'шки остались, мне интересно было бы посмотреть, в чем дело...
Программная оптимизация генератора КФ СНДЛК на базе ESODLS схем
Для разработанного недавно генератора КФ на базе изоморфизма X-образных заполнений и ESODLS схем была проведена оптимизация его программной реализации. На тестовой размерности N=8 получены следующие изменения в скорости подсчета главных классов по линейкам.
Было (см. https://vk.com/wall162891802_1284):
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
1050 s
Стало:
SCF line 1/20: 8148 SCFs (289,4 ms, 28155,8 SCF/s)
SCF line 2/20: 137801 SCFs (181,7 ms, 758416,7 SCF/s)
SCF line 3/20: 135595 SCFs (77,5 ms, 1749370,0 SCF/s)
SCF line 4/20: 213166 SCFs (92,5 ms, 2304919,1 SCF/s)
SCF line 5/20: 10092 SCFs (220,7 ms, 45720,9 SCF/s)
SCF line 6/20: 270633 SCFs (38,6 ms, 7006432,6 SCF/s)
SCF line 7/20: 837748 SCFs (263,7 ms, 3176745,4 SCF/s)
SCF line 8/20: 405668 SCFs (13,0 ms, 31220850,4 SCF/s)
SCF line 9/20: 214433 SCFs (81,7 ms, 2624568,8 SCF/s)
SCF line 10/20: 193044 SCFs (210,7 ms, 916136,6 SCF/s)
SCF line 11/20: 419434 SCFs (118,8 ms, 3531727,2 SCF/s)
SCF line 12/20: 437267 SCFs (257,5 ms, 1697873,8 SCF/s)
SCF line 13/20: 421525 SCFs (188,2 ms, 2239226,7 SCF/s)
SCF line 14/20: 51530 SCFs (250,2 ms, 205928,5 SCF/s)
SCF line 15/20: 414374 SCFs (38,4 ms, 10796941,3 SCF/s)
SCF line 16/20: 412695 SCFs (194,2 ms, 2125508,6 SCF/s)
SCF line 17/20: 135729 SCFs (133,2 ms, 1018880,0 SCF/s)
SCF line 18/20: 46301 SCFs (27,6 ms, 1678678,4 SCF/s)
SCF line 19/20: 103873 SCFs (185,0 ms, 561466,3 SCF/s)
SCF line 20/20: 4040 SCFs (138,2 ms, 29243,3 SCF/s)
Total DLS CFs = 4873096
106 s
Полученный интегральный выигрыш — 10x в среднем, на линейках с низкой кратностью он существенно выше (например, на линейке 1 — 625x). Оптимизация программ важна и нужна! По ее итогам в подпроекте ODLS BS проекта был произведен ряд изменений версий расчетного модуля, текущая версия 1.16 соответствует приведенным выше цифрам, с ее использованием эксперимент e774 по подсчету главных классов ДЛК порядка 9 будет окончен существенно быстрее.
В итоговой версии кода приблизительно ~2/3 времени отъедает генератор ДЛК, остальные ~1/3 — отображение через CMS схемы + нормализация по главной диагонали + сравнение пары ДЛК на меньше. Из последних трех нормализация занимает примерно половину времени. При необходимости генератор ДЛК можно сделать и быстрее с использованием программной реализации на базе вложенных циклов и битовой арифметики, остальные операции являются элементарными, существенного ускорения от их дальнейшей оптимизации добиться сложно.