Исследование свойств диагональных латинских квадратов в проектах добровольных распределенных вычислений и не только...
В ходе ручного улучшения окрестностей в области ДЛК с малым числом трансверсалей были найдены два интересных ДЛК:
0 1 2 3 4 5 6 7 8 9 10 11 12
1 2 0 4 3 6 10 8 7 11 12 9 5
12 6 11 0 7 4 3 5 10 1 2 8 9
7 4 3 12 10 1 2 9 11 6 8 5 0
4 8 9 5 6 2 1 11 3 10 0 12 7
10 12 5 8 0 9 11 4 6 7 3 2 1
6 9 10 2 1 11 8 12 5 0 4 7 3
3 5 6 1 2 7 4 10 12 8 9 0 11
2 7 8 9 11 10 12 0 1 3 5 4 6
11 3 4 10 12 0 7 2 9 5 1 6 8
9 11 1 6 5 8 0 3 4 12 7 10 2
8 0 7 11 9 12 5 1 2 4 6 3 10
5 10 12 7 8 3 9 6 0 2 11 1 4
4903 диагональных трансверсали
0 1 2 3 4 5 6 7 8 9 10 11 12
1 2 0 4 8 6 11 10 12 7 9 3 5
11 10 6 1 5 3 8 0 9 4 2 12 7
5 9 12 8 6 2 7 3 0 11 4 10 1
9 11 1 5 12 0 10 8 6 3 7 4 2
3 6 11 9 2 4 12 1 7 0 8 5 10
8 0 10 7 11 1 9 6 3 5 12 2 4
10 4 7 2 9 8 0 5 11 12 6 1 3
6 7 5 12 10 11 3 4 1 2 0 8 9
4 8 3 0 7 12 1 2 5 10 11 9 6
2 12 4 11 0 7 5 9 10 1 3 6 8
12 5 8 10 3 9 2 11 4 6 1 7 0
7 3 9 6 1 10 4 12 2 8 5 0 11
43866 трансверсали, что позволяет усилить два известных верхних ограничения:
* ряд A287645: с a(13)<=43979 до a(13)<=43866;
* ряд A287647: с a(13)<=5105 до a(13)<=4903.
Мощности спектров числа трансверсалей и диагональных трансверсалей подросли и на данный момент составляют соответственно 74315 и 12036 элементов соответственно. Эксперименты продолжаются...
В результате обработки ДЛК порядка 12
0 1 2 3 4 5 6 7 8 9 10 11
1 2 0 4 5 3 8 6 7 11 9 10
2 0 1 5 3 4 7 8 6 10 11 9
8 7 6 9 11 10 1 0 2 5 4 3
7 6 8 11 10 9 2 1 0 3 5 4
11 10 9 8 7 6 5 4 3 2 1 0
5 3 4 1 2 0 11 9 10 7 8 6
9 11 10 6 8 7 4 3 5 1 0 2
10 9 11 7 6 8 3 5 4 0 2 1
4 5 3 0 1 2 9 10 11 8 6 7
3 4 5 2 0 1 10 11 9 6 7 8
6 8 7 10 9 11 0 2 1 4 3 5
с 27760 диагональными трансверсалями и 198144 трансверсалями общего вида выяснено, что у него 1228403532 (расчет выполнен в проекте RakeSearch). Новых элементов в спектр числа ОДЛК это не дало, что весьма неожиданно! Причиной этому является то, что в формируемом спектре уже присутствует ДЛК
0 1 2 3 4 5 6 7 8 9 10 11
1 2 0 4 5 3 8 9 10 11 6 7
2 0 1 5 3 4 10 11 6 7 8 9
11 7 9 8 10 6 5 1 3 2 4 0
10 6 8 7 9 11 0 5 1 3 2 4
9 11 7 6 8 10 4 0 5 1 3 2
5 3 4 2 0 1 7 8 9 10 11 6
4 5 3 1 2 0 11 6 7 8 9 10
3 4 5 0 1 2 9 10 11 6 7 8
6 8 10 9 11 7 1 3 2 4 0 5
7 9 11 10 6 8 3 2 4 0 5 1
8 10 6 11 7 9 2 4 0 5 1 3
у которого 27760 диагональных трансверсалей, 198144 трансверсали общего вида и 1228403532 ОДЛК. Оба ДЛК являются КФами, друг в друга комбинациями М-преобразований не переводятся (т.е. не изоморфны как ДЛК), а тем не менее имеют как одно и то же число диагональных трансверсалей, так и одно и то же число ОДЛК. Первый квадрат является горизонтальным Брауном, второй какими-то особыми свойствами не обладает (или мы их не видим).
Формируемый спектр с момента публикации последнего анонса расширен в младшей части за счет экспериментов, выполняемых в однопоточном режиме на моей машине, и в настоящее время включает в своем составе 4915 элементов:
http://evatutin.narod.ru/spectra/spectrum_dls_odls_n12_xxxx_known_items.txt
Обработка спектра числа трансверсалей в ДЛК порядка 13 от известных пандиагональных/полуциклических ДЛК завершена. Напомню, что исходный опорный спектр включал в своем составе всего 6 элементов. Поворотом 1 интеркалята данный спектр был расширен до 13578 элементов. Поворот 1 цикла операция более длительная, основная часть расчетов была выполнена в проекте RakeSearch, далее обработка хвостов была запущена на моей машине в 1 поток. Наконец она завершена, за 5,5 суток расчетов спектр расширен до 32504 элементов.
В настоящее время на моей машине в 1 поток производится обработка хвоста от другого опорного спектра на базе квадратов Гергели вращением 1 интеркалята, по ее завершению в проект RakeSearch будет добавлена новая партия WU'шек для поворота циклов.
19 880 960 
Цитата: SETI_Home_v8 от 13.11.2022, 18:07Цитата: evatutin от 13.11.2022, 16:28Обработка спектра числа трансверсалей в ДЛК порядка 13 от известных пандиагональных/полуциклических ДЛК завершена.
А 14 порядок спектра числа трансверсалей в ДЛК будет?
Будет сразу как закончим эксперименты по порядку 13
В период с 29 ноября по 2 декабря на базе Института программных систем им. А.К. Айламазяна РАН традиционно пройдет Национальный суперкомпьютерный форум (https://2022.nscf.ru), на котором будет представлен ряд близких нам (по духу и не только ) тематических секций. В рамках секции Гриды из рабочих станций и комбинированные гриды с моим участием планируется 3 доклада:
1. Ватутин Э.И. Специальные виды диагональных латинских квадратов
2. Ватутин Э.И., Никитина Н.Н., Манзюк М.О., Курочкин И.И., Альбертьян А.М., Крипачев А.В., Пыхтин А.И. Методы построения спектров быстровычислимых числовых характеристик диагональных латинских квадратов
3. Шалдунов И.И., Ватутин Э.И. Сравнение способов заполнения диагональных латинских квадратов для итерационной реализации метода полного перебора
Первый доклад будет посвящен обобщению классификации специальных видов ДЛК, которые имеют интересные свойства и находят применение при решении текущих задач на базе ДЛК, выполняемых в рамках нашей научной группы. Видов ДЛК набралось больше десятка, давно пора свести их в одной публикации с прицелом на будущее исследование их свойств. Во втором докладе планируется подробное рассмотрение текущих результатов по построению спектров быстровычислимых характеристик ДЛК/ОДЛК и анализ эффективности используемых для этого методов (на данный момент их 3, сокращенно обозначенные как M1, M2 и d, в перспективе планируется разработка ряда дополнительных методов). Третий доклад будет сделан бакалавром нашей кафедры Шалдуновым Иваном и будет посвящен анализу влияния порядка заполнения элементов ДЛК на темп их дозаполнения методом полного перебора. Это направление работы было одним из первых в нашем исследовании свойств ДЛК, несколько лет назад совместно с Олегом Заикиными и Степаном Кочемазовым была разработана весьма эффективная программная реализация на базе вложенных циклов и битовой арифметики, позволившая осуществить перебор ДЛК порядка 10 с рекордным темпом 6,6 млн. ДЛК/с в 1 поток. Если все получится как планируется, темп перебора будет увеличен, а принцип, лежащий в основе данной программной реализации, будет расширен на смежные задачи на базе ДЛК.
С презентациями докладов можно ознакомиться тут: http://evatutin.narod.ru/evatutin_dls_spec_types.pdf и http://evatutin.narod.ru/evatutin_dls_spectra_m1_m2_d.pdf
Вопрос, а так планируется ли издать какую-нибудь книгу, посвящённую всем результатам исследований в Gerasim / RakeSearch?
Цитата: Yura12 от 14.11.2022, 10:40Вопрос, а так планируется ли издать какую-нибудь книгу, посвящённую всем результатам исследований в Gerasim / RakeSearch?
Я бы хотел, но тут вопрос в наличии свободного времени. Для этого надо кое-что описать, нарисовать, досчитать и структурировать. Материал на книгу (по объему) есть точно. Делать надо. Когда — хз...
А нельзя как-то организоваться в Вашем институте, чтобы привлечь к этому делу студентов, пишущих курсовые / дипломные, может даже аспирантов, чтобы они оказывали бы помощь, взяли на себя хоть часть работы, чтобы дело пошло быстрее?