Исследование свойств диагональных латинских квадратов в проектах добровольных распределенных вычислений и не только...
Цитата: Yura12 от 18.12.2022, 11:06А можно также спросить, а есть примерные, предварительные оценки, а сколько ещё примерно будут проводиться эксперименты по латинским квадратам в проекте RakeSearch? Год? 2 года? Или дольше?
Пока не надоест мне и hoarfrost'у с Наташей, которые мне здорово помогают с серверной частью проекта, за что им большое спасибо! Идей много, не посчитанного тоже много, будем потихоньку разгребать... 
Возьмем имеющиеся на данный момент спектры числа трансверсалей, диагональных трансверсалей и интеркалятов, переведем образующие их квадраты в списки КФов, построим общий список, а по нему — спектры перечисленных числовых характеристик, объединим полученные спектры с исходными. Для спектров числа трансверсалей и интеркалятов новых значений данная процедура не дала, а вот спектр числа диагональных трансверсалей удалось расширить с 12050 до 12409 элементов:
Min value = 4903, max value = 131106, width = 126204, cardinality = 12409, density = 0,10
Таким образом, в числовом ряду A345370 нижнее ограничение на член a(13) усилено с a(13)>=12050 до a(13)>=12409.
В дополнение к числовому ряду https://oeis.org/A357473 (число типов обобщенных симметрий в ДЛК) в OEIS подтверждено добавление еще трех числовых рядов:
* https://oeis.org/A358515 — число типов обобщенных симметрий в парастрофических срезах в ДЛК
* https://oeis.org/A358394 — число типов обобщенных симметрий в ОДЛК
* https://oeis.org/A358891 — число типов обобщенных симметрий в парастрофических срезах в ОДЛК
Возьмем циклические ДЛК порядка 11, переведем их в КФы и подвергнем полученное множество из 2 КФов процедуре диагоналиазации, в результате чего получен список из 81 КФ ДЛК, которые изоморфны циклическим ДЛК как ЛК. Полученные квадраты обладают большим числом диагональных трансверсалей, а следовательно — большим числом ОДЛК, что автоматически помещает их в состав редких комбинаторных структур. Анализом самих структур займемся чуть позже, на данный момент осуществлено построение множеств образующих их КФ:
n11_huge5_24277C
n11_huge6_21219C
n11_huge7_18241C
...
n11_huge84_28935C
но сам анализ не выполнялся, некоторые ДЛК могут входить в состав одной и той же структуры, т.е. полученные множества будут повторяться. Множества полученных редких КФ ОДЛК можно использовать для построения спектров быстровычислимых числовых характеристик ОДЛК порядка 11. Расчет для числа ОДЛК в настоящее время еще не завершен, а для других числовых характеристик получено расширение известных спектров ОДЛК:
* число трансверсалей в ОДЛК: 3582 -> 3588 (+6 элементов);
* число диагональных трансверсалей в ОДЛК: 482 -> 560 (+78 элементов);
* число интеркалятов в ОДЛК: 76 -> 76 (без расширения).
#ODLS
В ходе досчета хвостов при работе со спектрами числа трансверсалей и диагональных трансверсалей в ДЛК порядка 13 найден квадрат
0 1 2 3 4 5 6 7 8 9 10 11 12
1 2 0 4 3 6 5 8 7 11 12 9 10
6 12 11 0 8 4 3 10 5 7 2 1 9
8 11 3 12 10 1 2 9 4 6 7 5 0
4 7 9 10 6 2 1 11 3 5 0 12 8
5 6 10 7 0 9 11 4 12 8 3 2 1
12 9 5 1 2 11 7 6 10 0 4 8 3
3 10 12 2 7 8 4 5 6 1 9 0 11
2 8 7 9 11 10 12 0 1 3 5 4 6
11 3 4 5 12 0 8 2 9 10 1 6 7
9 4 1 6 5 7 0 3 11 12 8 10 2
7 0 8 11 9 12 10 1 2 4 6 3 5
10 5 6 8 1 3 9 12 0 2 11 7 4
у которого 43835 трансверсалей, что позволяет усилить верхнее ограничение в числовом ряду A287645 с a(13)<=43866 до a(13)<=43835. Мощности соответствующих спектров на данный момент слегка увеличились и составляют 75265 (трансверсали) и 12722 (диагональные трансверсали) элементов.
а какие порядки уже ПОЛНОСТЬЮ просчитаны-прочёсаны?
а то вон даже на "всего лишь 11м" до сих пор новости обнаруживаются.
Цитата: Шмяка от 01.01.2023, 21:21а какие порядки уже ПОЛНОСТЬЮ просчитаны-прочёсаны?
а то вон даже на "всего лишь 11м" до сих пор новости обнаруживаются.
По ДЛК все до 12 включительно, 13-й дочесываем, 14 и 15 прочесаны частично. По ОДЛК — до 9 включительно, 10 более менее, более старшие только частично, их будем чесать позже. Но тут дело в том, что появляются новые идеи, как можно попробовать найти элементы в той или иной части спектра. Не все из них пока воплощены в коде, это работа на будущее. Главное, что есть результат — спектры потихоньку растут...
PS. Вот тут http://evatutin.narod.ru/evatutin_dls_spectra_m1_m2_d.pdf моя презентация с прошедшего НСКФ'а, на слайдах 5-16 есть ответ на вопрос о спектрах ДЛК и методах, которые были использованы для их построения.
В подпроект по спектрам ДЛК порядка 13 проекта RakeSearch добавлена новая версия расчетного модуля, которая пока функционирует в тестовом режиме (но вроде без ошибок!) и первая партия из чуть более чем 10 тыс. тестовых WU'шек. Цель — распределенная диагонализация ДЛК в составе спектров с целью их расширения. До этого для более маленьких порядков мы выполняли просто диагонализацию, начиная с данного порядка это будет слишком долго, поэтому был разработан код, выполняющий ее по частям. Подробности завтра...
Распределенная диагонализация
В комбинаторике есть понятие т.н. "комбинаторного взрыва", когда с ростом размерности задачи ее вычислительная сложность резко возрастает и применение ряда методов, работавших до этого для малых размерностей, становится невозможным из-за необходимости огромных вычислительных затрат. На примере решаемых в настоящее время задач, связанных с построением спектров, данная ситуация для диагонализации и поквадратного обхода окрестностей начинает проявляться на размерности N=13. И если диагонализацию еще можно реализовать по частям (что и было сделано), то поквадратный обход для данной окрестности уже невозможен (приблизительная оценка необходимых вычислительных затрат — 80 лет в проекте), следовательно мы пойдем другим путем :).
В решаемых в настоящее время задачах, связанных с построением спектров, диагонализация применяется совместно с анализом окрестностей и позволяет как увеличить мощность результирующего спектра, так и сдвинуть его верхнюю и нижнюю границы в ситуациях, когда спектр близок в пределу и просто обходом окрестностей границы уже не сдвигаются (это не единственное применение диагонализации, остальные пока оставим в стороне). Для размерности N=12 диагонализация уже выполнялась от нескольких часов до нескольких десятков часов на квадрат (для рекордсмена по числу трансверсалей — более недели в 1 поток на моей машине), для текущей размерности N=13 самые легкие квадраты будут диагонализироваться несколько часов, тяжелые — до нескольких месяцев, что неприемлимо. Поэтому, пользуясь свободным временем, в коде был реализован распределенный вариант диагонализатора, который давно созрел в голове и ждал, когда же его наконец реализуют...
В двух словах диагонализация выполняется следующим образом: из множества трансверсалей ЛК находятся подходящие пары трансверсалей, по которым производится ряд целенаправленных перестановок строк и столбцов исходного ЛК с целью получения результирующего ДЛК с интересными свойствами, что сильно быстрее (на много порядков) лобовой перестановки всех возможных пар строк и столбцов. Далеко не все пары трансверсалей являются интересными, однако проверять необходимо все, при этом пары (T[i], T[j]) и (T[j], T[i]) проверять дважды смысла нет, что при изображении соответствия трансверсалей в виде бинарной матрицы (0 — не подходят, 1 — подходят) приводит к необходимости обхода не всей матрицы, а ее половины — верхней или нижней треугольной подматрицы (для определенности обходится верхняя). В программировании это обычное дело, применяется очень часто в ряде алгоритмов, псевдокод выглядит примерно так:
for (int i = 0; i < NT; i++)
for (int j = i+1; j < NT; j++)
...
Если код работает долго, значит его необходимо разбивать на куски и запускать их параллельно (в нашем случае — распределенно в проекте по принципу "1 кусок — 1 WU'шка"). Простейшим способом распараллеливания является разбиение по внешнему циклу (по i), однако здесь есть проблема: в таком случае в каждой WU'шке потребуется хранить полное множество трансверсалей (для порядка N=13 их уже бывает более миллиона, для бОльших порядков их будет сильно больше, см. https://oeis.org/A287644), что потребует минимум сотен МБ — единиц-десятков ГБ оперативной памяти на WU. Более подходящей видится следующая стратегия: матрица разбивается на квадраты заданного размера K x K, одна WU'шка производит обработку одного квадрата (см. рис., на нем изображен один из самых легких ДЛК с 43 тыс. трансверсалей и разбиение на WU'шки по 20 тыс. x 20 тыс. трансверсалей в квадрате, всего 6 WU'шек). При этом возникает ряд нюансов, но они терпимые и легко реализуются в коде. К ним относятся:
* необходимость построения разбиения на квадраты, некоторые из которых частично попадают под главную диагональ (на рисунке изображены оранжевым) — в составе соответствующих WU'шек необходима проверка и отсечение пар трансверсалей из нижней треугольной подматрицы (красные квадраты и прямоугольники обрабатываются полностью);
* наличие маленьких прямоугольников и квадратов по краям (им будут соответствовать более короткие WU'шки с рядом дополнительных проверок, чтобы не вылезти за пределы анализируемой области вправо и вниз);
* обходимость хранения множества трансверсалей по кускам (точнее, в два куска в диапазонах [x; x+K] и [y; y+K], (x,y) — координаты верхнего левого угла анализируемого квадрата/прямоугольника, диапазоны иногда могут пересекаться (в данной задаче — совпадать полностью, в перспективных задачах по эвристической работе со спектрами — частично пересекаться)).
Неоспоримым плюсом подхода является его универсальность: на квадраты можно разбить как легкие, так и тяжелые ДЛК, в последнем случае просто квадратов будет больше (для топового ДЛК порядка 13 — около 2500 при текущем разбиении), возможно управлять средним временем счета WU'шек и затратами памяти путем изменения размера квадрата K (критичным в данной задаче является именно время счета, которое в проекте не желательно делать как сильно маленьким (минуты и меньше), так и сильно большим (десятки часов), затраты памяти приемлемые).
Кроме описанного выше распараллеливание также сделано по парастрофическим преобразованиям (по 3 на ДЛК из 6 возможных, транспонирование исключено, т.к. оно дает ДЛК из того же главного класса и не интересно) и т.н. slice'ам для каждого из них (тоже 3, итого 9 комбинаций), в данном случае все тривиально в плане распараллеливания.
Вчера в проект была добавлена новая версия расчетного модуля с включенным рядом отладочных проверок и чуть более чем 10 тыс. WU'шек для 200 наиболее легких ДЛК с целью тестирования корректности кода и анализа затрат времени. В настоящее время выполняется досчет хвостов, после чего можно будет приступать к более подробному анализу, однако уже сейчас видно, что вроде все более менее норм. Среднее время счета у меня на Core i7 4770 было в районе 7-8 минут, максимальное — около 20 минут для K=20000. В перспективе K будет немного увеличено, WU'шки немного потяжелеют и расчет будет запущен в боевом режиме. Досчитываем хвосты и считаем другие подпроекты...
PS. Применение распределенной диагонализации отнюдь не ограничивается рассмотренным выше экспериментом, который мы будем выполнять в ближайшие недели. В перспективе оно планируется к использованию как для сдвига верхних и нижних границ для некоторых оценок, так и в составе следующей серии эвристических алгоритмов расширения текущих спектров, когда текущая серия отработает и спектры перестанут меняться.
PPS. При организации подобного распределенного расчета в грид есть еще один нюанс, связанный с построением необходимого множества трансверсалей. Его можно однократно получить в процессе генерации WU'шек, а затем передать на клиент, а можно получить первым этапом при счете WU'шки. В данном эксперименте выбран первый вариант (на генерацию нужных трансверсалей теряем 1-2 секунды в каждой WU'шке, зато экономим несколько сотен КБ исходных данных WU'шки (а они сперва генерируются, потом хранятся в одной из таблиц БД на сервере проекта, затем передаются на клиент, копируются/мапятся в папку слота при старте расчета)). В перспективе с ростом размерности вполне вероятна ситуация, в которой получение нужных подмножеств трансверсалей подобным образом в каждой WU'шке станет неприемлемо долгим и придется перейти ко второму варианту...
Расчет тестовых WU'шек для распределенной диагонализации успешно завершен, процесс слегка растянулся из-за 7-дневного дедлайна и долгого ожидания хвостов, но главное — результат, а он есть и весьма неплохой! Спектр числа диагональных трансверсалей в ДЛК порядка 13, который до этого имел мощность 12722 элемента и обходами окрестностей образующих его квадратов уже не расширялся, диагонализацией всего 200 первых ("младших" по числу трансверсалей) ДЛК расширен до 12858 (+136) элементов, верхнее ограничение на минимальное значение усилено с 4903 до 4863, соответствующий квадрат
0 1 2 3 4 5 6 7 8 9 10 11 12
1 2 3 4 5 12 7 11 6 8 9 10 0
12 8 11 5 0 10 2 3 9 7 4 1 6
4 3 1 12 2 11 9 10 5 0 6 7 8
8 5 12 0 6 7 1 4 11 10 3 2 9
11 9 6 7 10 4 12 5 1 3 0 8 2
9 0 5 8 12 6 3 1 10 11 2 4 7
10 6 7 9 11 1 5 8 4 2 12 0 3
5 12 0 10 8 9 4 2 7 6 1 3 11
7 11 10 6 9 2 0 12 3 1 8 5 4
6 10 9 11 7 3 8 0 2 4 5 12 1
3 7 4 2 1 8 10 6 0 12 11 9 5
2 4 8 1 3 0 11 9 12 5 7 6 10
но это еще не все! Обход окрестностей новых ДЛК в данном спектре путем поворота 1 интеркалята позволил еще увеличить мощность спектра до 12871 (еще +13) и усилить верхнее ограничение до 4846, подтверждающий квадрат
0 1 2 3 4 5 6 7 8 9 10 11 12
1 2 0 4 5 7 12 11 3 8 6 9 10
9 10 7 8 3 11 4 5 2 12 1 6 0
12 9 5 11 8 3 1 10 7 6 0 4 2
2 0 12 9 1 4 10 6 11 7 3 5 8
10 8 3 6 12 9 11 2 4 1 7 0 5
7 11 6 2 0 1 3 4 12 5 8 10 9
5 7 4 12 9 10 0 8 6 2 11 1 3
11 6 1 5 7 2 9 0 10 3 12 8 4
8 3 11 0 10 6 5 12 9 4 2 7 1
3 4 8 10 6 12 7 9 1 0 5 2 11
6 5 9 1 11 8 2 3 0 10 4 12 7
4 12 10 7 2 0 8 1 5 11 9 3 6
Ну и наконец обход окрестностей новых ДЛК путем поворота 1 цикла позволил увеличить мощность спектра до 12917 (еще +46) и верхнее ограничение до 4756 для квадрата
0 1 2 3 4 5 6 7 8 9 10 11 12
1 2 0 4 3 10 8 11 6 12 5 7 9
8 12 9 5 10 2 3 0 4 7 6 1 11
11 6 7 8 0 3 5 9 2 1 4 12 10
2 10 5 11 7 1 12 4 9 6 0 3 8
9 7 4 12 6 11 1 2 10 0 3 8 5
12 9 10 2 5 6 4 1 3 11 8 0 7
3 4 11 9 12 8 0 6 1 10 7 5 2
10 5 1 7 11 0 9 3 12 8 2 4 6
4 3 12 10 9 7 2 8 0 5 11 6 1
7 11 3 6 8 4 10 12 5 2 1 9 0
6 0 8 1 2 12 7 5 11 3 9 10 4
5 8 6 0 1 9 11 10 7 4 12 2 3
Последний квадрат имеет еще и 43225 трансверсалей общего вида, что позволяет усилить верхнее ограничение на минимальное количество трансверсалей в ДЛК порядка 13 с a(13)<=43835 до a(13)<=43225 в числовом ряду A287645.
Первые результаты нового эксперимента показали в точности то, что от них и ожидалось, поэтому далее в ближайшей перспективе он будет запущен в полномасштабном режиме.