Исследование свойств диагональных латинских квадратов в проектах добровольных распределенных вычислений и не только...
На конференцию "Russian Supercomputing Days 2023", которая будет проходить в сентябре в МГУ, нашим коллективом авторов подготовлена большая 18-страничная англоязычная статья
Diagonalization and canonization of Latin squares
В ней подробно рассмотрены особенности программной реализации процедур диагонализации и канонизации, приведены соответствующие алгоритмы, примеры и оценки их трудоемкости.
Ждем рассмотрения программным комитетом...
Уже завтра стартует соревнование по RakeSearch на BoincStats
А может быть в связи с этим имеет смысл в ближайшую неделю чтобы проект выдавал бы только тяжёлые задания, а лёгкие задания временно отключить?
По итогам прошедшего Национального суперкомпьютерного форума 2022 опубликован сборник трудов конференции, включающий в своем составе работы по нашему направлению, отобранные программным комитетом для опубликования. В их числе есть три работы, связанные с латинскими квадратами:
Ватутин Э.И. Специальные виды диагональных латинских квадратов // Облачные и распределенные вычислительные системы в электронном управлении (ОРВСЭУ – 2022) в рамках Национального суперкомпьютерного форума (НСКФ – 2022). Переславль-Залесский, 2023. С. 9–18. http://evatutin.narod.ru/evatutin_dls_spec_types_list.pdf
Ватутин Э.И., Никитина Н.Н., Манзюк М.О., Курочкин И.И., Альбертьян А.М., Крипачев А.В., Пыхтин А.И. Методы построения спектров быстровычислимых числовых характеристик диагональных латинских квадратов // Облачные и распределенные вычислительные системы в электронном управлении (ОРВСЭУ – 2022) в рамках Национального суперкомпьютерного форума (НСКФ – 2022). Переславль-Залесский, 2023. С. 19–23. http://evatutin.narod.ru/evatutin_dls_heur_spectra_method_2.pdf
Шалдунов И.И., Ватутин Э.И. Сравнение способов заполнения диагональных латинских квадратов для итерационной реализации метода полного перебора // Облачные и распределенные вычислительные системы в электронном управлении (ОРВСЭУ – 2022) в рамках Национального суперкомпьютерного форума (НСКФ – 2022). Переславль-Залесский, 2023. С. 51–59. http://evatutin.narod.ru/evatutin_dls_bf_pace_shaldunov.pdf
Первая посвящена классификации типов всех (ну или почти всех, по крайней мере самых интересных — так точно) ДЛК специального вида: симметричных, квадратов Брауна, (полу)циклических и т.д. Необходимость в данной классификации назрела давно, т.к. результаты текущих экспериментов показывают, что, например, топовые представители спектров трансверсалей, интеркалятов, ОДЛК являются не случайными квадратами, а имеют вполне определенный тип. А это в свою очередь значит, что свойства обозначенных типов квадратов в перспективе надо бы поисследовать более подробно.
Во второй приведено описание стратегии распределенного формирования аппроксимаций спектров числовых характеристик ДЛК с использованием проекта RakeSearch и полученные на момент написания публикации результаты (в настоящее время часть результатов уже усилена по итогам дальнейших расчетов).
В третьей работе мой бакалавр попробовал разобраться с тем, как влияет порядок заполнения ячеек на темп генерации ДЛК в полнопереборной реализации. Он перепробовал как наши идеи, которые когда-то давно мы апробировали вместе с Олегом Заикиным и Степаном Кочемазовым, и реализовал часть своих. В результате эффект сильного влияния порядка заполнения на темп независимо подтвержден на разработанной им программной реализации, более эффективного порядка заполнения не найдено, студент получил кучу experience'а и level up (c) :), первую научную публикацию и, надеюсь, будет продолжать работу в данном направлении.
Цитата: Yura12 от 18.04.2023, 14:53Уже завтра стартует соревнование по RakeSearch на BoincStats
А может быть в связи с этим имеет смысл в ближайшую неделю чтобы проект выдавал бы только тяжёлые задания, а лёгкие задания временно отключить?
Сейчас во всех 3 подпроектах задания тяжелые: от 1 до 3 часов счета. Есть небольшая часть легких в DDLX, но они будут незаметны на фоне остальных. К соревнованию готовы! 
Понятно. А чекпоинты сейчас в проекте есть?
В проекте добровольных распределенных вычислений RakeSearch завершена разведка второго парастрофического среза, ее результаты в графическом виде приведены ниже. Напомню, что числа в районе нескольких сотен ("красная" карта) соответствуют числу однушек для каждого из выбранных кодов симметрии, числа в районе 0-10 (иногда больше, "желто-красная" карта) соответствуют числу двушек, ну а третья картинка — перечень более редких комбинаторных структур. По итогам хвоста разведки в ожидаемых местах найден ряд потенциально интересных точек с кодами симметрии
2-(31,1)
2-(31,4)
2-(31,16)
2-(31,31)
2-(32,1)
которые в ближайшей перспективе мы будем исследовать более подробно. Также напомню, что на данный момент завершена обработка 1-3 парастрофических срезов, впереди предстоит обработка 4-6, первые WU'шки для разведки в 4-м срезе уже добавлены в проект и считаются. Общее количество найденных КФ ОДЛК порядка 10 приближается к 21 млн.
Сборник нашей конференции Облачные и распределенные вычислительные системы в электронном управлении (ОРВСЭУ – 2022), которая проводилась в рамках Национального суперкомпьютерного форума (НСКФ – 2022) в конце 2022 г., проиндексирован в РИНЦ:
Возьмем и выпишем порядки N, для которых существуют циклические ДЛК, для чего требуется программа объемом чуть более 100 строк, разрабатываемая по готовому написанному ранее коду за 5 минут. В результате ее запуска в диапазоне порядков 1 <= N <= 100 получается следующий числовой ряд
1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, 41, 43, 47, 49, 53, 55, 59, 61, 65, 67, 71, 73, 77, 79, 83, 85, 89, 91, 95, 97
Данный числовой ряд уже присутствует в OEIS под номером https://oeis.org/A007310 и представляет собой числа, дающие 1 или 5 в остатке при делении на 6. Соответственно, установлено условие существования циклических ДЛК, что не может не радовать! Описание данного ряда в OEIS не содержит ни слова про латинские квадраты, а значит в перспективе по мере подтверждения текущей серии правок данный пробел может быть восполнен.
числа, дающие 1 или 5 в остатке при делении на 6.
множество "6х+1" плюс множество "6х+5"
как оно просто оказалось... а сколько уже лет мы эти квадраты мучаем?