Итак, эксперимент по определению быстровычислимых числовых характеристик ДЛК порядка 9 завершен!

Итак, эксперимент по определению быстровычислимых числовых характеристик ДЛК порядка 9 завершен! Все WU'шки обработаны, результаты перепроверены, можно делать анонс, буду краток :).

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

1. Формируются все КФ ДЛК порядка 9 (разбивка на WU'шки при этом была взята более мелкая, чем при первоначальном подсчете КФ ДЛК, в том числе чтобы перепроверить их общее количество, полученное ранее (забегая вперед, перепроверили, все совпало и по отдельным линейкам, и в общем)).

2. Для каждой КФ ДЛК производится получение множества трансверсалей. Фиксируются квадраты, обладающие их минимальным и максимальным количеством.

3. Из множества трансверсалей отбираются диагональные трансверсали, фиксируются квадраты, обладающие их минимальным и максимальным количеством (это быстрее, чем строить множество трансверсалей для канонизатора, а затем строить множество диагональных трансверсалей для получения всех ОДЛК структуры, причем прилично быстрее, в несколько раз!).

4. Производится проверка на наличие ОДЛК к обрабатываемой КФ ДЛК. Если ОДЛК есть, производится получение всех КФ, образующих комбинаторную структуру, они фиксируются и возвращаются на сервер проекта. Так быстрее, чем получение всех ОДЛК, а потом — их КФ, что особенно заметно на больших структурах. Кроме того, таким образом по КФ ОДЛК из текущей линейки находятся (зачастую повторно) КФы из других линеек, что является дополнительной перестраховкой на случай пропуска некоторых WU'шек. На самом деле, при перепроверке полученных результатов, результаты WU'шек были отдельно обработаны по линейкам без данной перестраховки, цифры совпали, что вселяет оптимизм.

5. Для обрабатываемой КФ ДЛК производится построение списка интеркалятов, фиксируются квадраты, обладающие их минимальным и максимальным количеством. Данная операция выполняется быстро и практически не снижает темпа обработки, заново гонять генератор КФ для нее в отдельном эксперименте смысла нет.

Ну а далее результаты были собраны на сервере и постобработаны на моей машине, в результате чего была получены коллекция КФ ОДЛК и рекордные значения на некоторые числовые характеристики.

Теперь несколько замечаний о нужности или не нужности некоторых преобразований (маленький FAQ :).

1. Почему для данного эксперимента не эффективен канонизатор ДЛК по ЛК?

Потому что темп обработки квадратов с его использованием существенно ниже, чем у просто Эйлера-Паркера через DLX. На 9-ках эти цифры я не оценивал, на 10-ках соотношение составляет примерно 200-400 ДЛК/с для канонизатора снаружи и 1000-2000 ДЛК/с для Эйлера-Паркера + DLX, для 9-к отношение цифр будет схожим. От деталей реализации и оптимизации не зависит, особенность чисто алгоритмическая. Почему же тогда на 10-ках мы используем канонизатор? Да потому, что все множество КФ ДЛК порядка 10 мы вряд ли переберем в обозримой перспективе даже на топовых суперкомпьютерах, в данных условиях частичного перебора канонизатор дает дополнительные решения бесплатно из-за того, что внутри него ДЛК темп обработки 8000 ДЛК/с, а снаружи — упомянутые выше 200-400 ЛК/с. При полном переборе всего пространства бесплатных решений не будет, поэтому эффективность его использования падает практически на порядок. Кто кодил его руками с нуля, тот поймет, о чем речь, ну а кто не кодил, а привык использовать готовое... :) В общем и целом, если кто-то еще использует канонизатор, рекомендую от него отказаться, подтверждение части полученных нами цифр будет получено раньше. Вообще надо бы по этому вопросу сделать отдельную статью, займемся на досуге...

2. Почему в ходе данного эксперимента не нужны простые преобразования (повороты циклов, интеркалятов и пр.)?

Да просто потому, что при полном переборе всего пространства поиска новых решений они не дадут, только съедят вычислительное время на клиентах. Для постобработки списка из 75 тыс. КФ ОДЛК с целью перепроверки они вполне могут быть использованы, данная обработка выполняется быстро, несколько десятков минут, а вот для обработки всех подряд КФ в проекте — конечно же нет. Кроме того, использование простых без полного перебора никаких гарантий полноты списка не дает, его результатом будет быстрая накрутка числа находок в начале эксперимента и медленное их пополнение в конце, что и наблюдается, но не у нас... :) Поэтому если вы все еще используете простые преобразования для получения новых результатов (КФ ОДЛК)... В общем я думаю вы меня поняли :)

FAQ закончился, идем дальше.

Теперь немного статистики... Эксперимент занял 89 суток на грид со средней реальной производительностью 2—3 TFLOP/s (8 TFLOP/s в пике) в Gerasim@Home и примерно столько же в RakeSearch, из которых 2 последних дня досчитывались хвосты, что довольно быстро благодаря ручному управлению дедлайном (можно бы эту штуку и автоматизировать на стороне сервера, но это на будущее). Эффективный темп обработки составил 428152 КФ ДЛК/с (без кворума 2 он был бы в 2 раза выше, но доверие к результатом было бы ниже). Расчет был организован параллельно (по различным линейкам) в проектах Gerasim@Home и RakeSearch, которые выполнили примерно одинаковый объем вычислительной работы (как по числу обработанных КФ, так и по числу обработанных линеек). На всякий случай, не все знают, что, например, полная обработка линейки 5 — это не 5% от общего объема пространства перебора, а всего 0,32%. Почему? Потому, что число КФ в линейках напрямую зависит от их кратности, а у 5-й линейки кратность низкая, всего 24. У линейки 6, для примера, кратность составляет 384, и КФ ДЛК в ней (а значит и объем вычислительной работы) в 22 раза больше... Прогнозное время вычислений (125 лет на Core i7 4770 в 1 поток) очень хорошо совпало с выполненным объемом работы (126 лет), выигрыш по сравнению с однопоточным запуском составил 515,8 раз (с кворумом 1 было бы в 2 раза больше, без помощи RakeSearch — в 2 раза меньше). Т.е. два проекта считают примерно так же, как 172 одновременно работающих Core i7 4770 при полной нагрузке (8 потоков) в режиме 24/7.

Полученные результаты позволили получить сразу много цифр по 9-кам, но об этом ниже, оставим на сладкое. Сперва необходимо убедиться, что они получились верные. Самым лучшим способом является независимое подтверждение на независимом коде (ждем "наших партнеров", но по моим оценкам им еще далеко, т.к. меряться тут нужно не числом находок, а объемом обработанного пространства перебора, т.к. от его полного прохождения тут никуда не деться), но чего пока нет, того нет. На данный момент проверка полученных результатов была выполнена своими силами в ходе небольшой постобработки.

1. Ранее известные списки КФ ОДЛК были проверены на вхождение в новый, новых КФ ОДЛК по сравнению с полученным нами списком они не содержат. Первые находки от анализа центрально-симметричных ОДЛК были получены еще в 2017-м, что можно считать началом эксперимента по составлению списка КФ ОДЛК порядка 9. Это я напоминаю на всякий случай, вдруг кто-то захочет померяться датами начала построения коллекции... :) Также напомню, что полученный список составлялся с нуля, без использования каких-либо других источников квадратов (для дополнительной перестраховки и перепроверки).

2. Была произведена попытка расширения списка находок простыми преобразованиями — список не расширился. Для поворота 1-5 интеркалятов это заняло всего около 10 минут времени, было найдено чуть больше 1000 повторных КФ ОДЛК. Поворот циклов и латинских подквадратов/подпрямоугольников еще выполняется, но на данный момент списки так же не расширились (и скорее всего не расширятся, об этом я напишу позже, если потребуется).

3. Была произведена канонизация (ДЛК по ЛК, не путать с просто построением КФ!) для всех КФ в составе списка: новых КФ найдено не было. Именно в таком формате канонизация эффективна: были канонизированы ~75 тыс. КФ ОДЛК, а не все множество из 3292326155394 КФ ДЛК. Что называется, почувствуйте разницу в необходимых вычислительных затратах :).

4. Была произведена обработка полученных результатов по линейкам по отдельности. Число WU'шек, КФ ДЛК и КФ ОДЛК в точности совпало (перестраховка с перекрытием по КФ ОДЛК в составе комбинаторных структур и без него дала один и тот же результат). Эта операция была самой долгой при перепроверке (до суток на одну линейку) ввиду того, что в одну папку требовалась распаковка нескольких сотен тысяч файлов с результатами, а это не очень быстро, HDD работает со случайным чтением/записью, RAM-диск сильно процесс не ускоряет, тут видимо тормоза начинаются на уровне NTFS.

5. Число КФ SODLS и DSODLS в точности совпало со значениями, полученными ранее как нами (по известным спискам, вот-вот про это выйдет статья по итогам RSD), так и Harry White'ом и Francis'ом Gaspalou. Это независимо ни от кого подтверждает полученные ранее значения и списки. С числом КФ SODLS интрига сохранялась буквально до последних дней эксперимента, т.к. 3 недостающие КФ SODLS были найдены за 2 дня до завершения основной части WU'шек последней 16-й линейки.

Ну и теперь самое интересное — результаты эксперимента!

1. Общее число обработанных КФ ДЛК порядка 9: A287764(9) = 3292326155394. Было известно ранее, совпало, независимая проверка, 3-я по счету.

2. Число найденных КФ ОДЛК порядка 9: A330391(9) = 75307 (раскладка по линейкам на картинке внизу). Новая цифра, получены впервые, до этого было известно лишь нижнее ограничение, которые мы могли усиливать (и усиливали) практически каждый день, но в OEIS добавлять не стали, смысла в этом не вижу, как и в публикации частичных списков находок при условии, что в обозримой перспективе будет найден полный. А вот финальное значение очень даже стоит опубликовать!

3. Минимальное значение числа трансверсалей в ДЛК порядка 9: A287645(9) = 68. Значение было добавлено ранее на основании известного нижнего ограничения на данную величину со стороны ЛК, дополнительно перепроверили полным перебором, подтверждено.

4. Максимальное значение числа трансверсалей в ДЛК порядка 9: A287644(9) = 2241. Аналогично рассмотренному выше, значение было добавлено ранее на основании известного верхнего ограничения на данную величину со стороны ЛК, перепроверено полным перебором, подтверждено.

5. Минимальное значение числа диагональных трансверсалей в ДЛК порядка 9: A287647(9) = 0. Было добавлено ранее на основании нижнего ограничения ограничения 0 <= A287647(N), перепроверено полным перебором, подтверждено.

6. Максимальное значение числа диагональных трансверсалей в ДЛК порядка 9: A287648(9) = 333. Ранее нами по результатам части поиска было добавлено нижнее ограничение A287648(9) >= 333, теперь его можно трансформировать в равенство по результатам полного перебора. Поведение конкурентов в части этой цифры, найденной для известного (как потом выяснилось) блочного квадрата "задним числом" после публикации нашей находки, считаю неуместным, некорректным и не этичным...

7. Максимальное число нормализованных ОДЛК для одного ДЛК порядка 9: A287695(9) = 614. До этого было установлено нижнее ограничение A287695(9) >= 614 (приоритет не наш), полным перебором мы его превратили в точное равенство, этот результат за нами! Возражения не принимаются, в OEIS эту информацию постараемся отразить как можно точнее :)

8. Минимальное число интеркалятов в ДЛК порядка 9: A307163(9) = 0. Было добавлено ранее на основании нижнего ограничения ограничения 0 <= A307163(N), перепроверено полным перебором, подтверждено.

9. Максимальное число интеркалятов в ДЛК порядка 9: A307164(9) = 72. Было добавлено ранее на основании верхнего ограничения ограничения от ЛК, перепроверено полным перебором, подтверждено.

10. Соотношение числа КФ ОДЛК к числу КФ пустышек — 1 : 43718615 (ситуация хуже, чем с ДЛК порядка 10, для которых приблизительно 1 : 30000000, см. http://evatutin.narod.ru/evatutin_co_dls_bachelors_cnt.pdf).

11. Число КФ ESODLS порядка 9: A309210(9) = 18865. Значение найдено впервые, в перспективе его надо бы перепроверить с использованием ESODLS CMS схем (данные эксперименты, только для 10-к, выполнялись весной в Gerasim@Home случайным перебором (точнее, по стратегии RS+LBF, см. http://evatutin.narod.ru/evatutin_co_brief.pdf) и в RakeSearch SAT'ом).

12. Число КФ SODLS порядка 9: A329685(9) = 470 (из них 131 trans_self_ort и 427 anti_trans_self_ort). Найдено и опубликовано ранее, независимо перепроверено полным перебором, подтверждено.

13. Число КФ DSODLS порядка 9: A333366(9) = 88. Найдено и опубликовано ранее, независимо перепроверено полным перебором, подтверждено.

14. Число КФ пустышек для ДЛК порядка 9: A337309(9) = A287764(9) - A330391(9) = 3292326155394 - 75307 = 3292326080087.

Ну и кроме всего прочего, в ходе анализа полученных результатов было найдено 437 новых комбинаторных структур из ОДЛК порядка 9 (в дополнение к известным ранее 227, см. http://evatutin.narod.ru/evatutin_ls_all_structs_n9_rus.pdf). Данный результат необходимо перепроверить, возможно число структур получится дополнительно немного увеличить, после чего будет опубликовано точное значение и описание.

Полученный список КФ ОДЛК порядка 9 позволяет посчитать и еще группу числовых характеристик + ограничений на них, что будет сделано в перспективе.

Все написанное выше тянет на статью (научную), чем мы планируем заняться с коллегами в самое ближайшее время :)

PS. Чуть не забыл самое главное: полный список находок можно скачать здесь: http://evatutin.narod.ru/evatutin_odls_9p.zip :)

Источник: evatutin.narod.ru

Комментарии: