Исследование свойств диагональных латинских квадратов в проектах добровольных распределенных вычислений и не только...
В проекте RakeSearch завершена обработка очередного (37-го) интересного ДЛК порядка 12
0 1 2 3 4 5 6 7 8 9 10 11
1 2 0 4 9 8 11 6 10 3 5 7
2 0 1 9 3 10 7 11 5 4 8 6
6 11 7 5 8 4 1 0 9 10 3 2
11 7 6 8 10 9 2 1 3 5 4 0
4 9 3 1 2 11 8 5 7 0 6 10
10 5 8 7 6 0 3 9 1 11 2 4
8 10 5 11 7 2 9 4 0 6 1 3
9 3 4 2 0 7 10 8 6 1 11 5
5 8 10 6 11 1 4 3 2 7 0 9
7 6 11 10 5 3 0 2 4 8 9 1
3 4 9 0 1 6 5 10 11 2 7 8
у которого 25548 диагональных трансверсалей и 527873490 ОДЛК, что позволяет ему занять 28-е место в соответствующем спектре, который на данный момент включает в своем составе 5684 элемента и доступен тут:
https://evatutin.narod.ru/spectra/spectrum_dls_odls_n12_xxxx_known_items.txt
Загруженные файлы:
В ходе серии вычислительных экспериментов со спектрами числа интеркалятов в ЛК порядка 20, приведенных в графическом виде во вложении, получен интегральный спектр мощностью 1362 элемента, что больше мощности известного на данный момент спектра числа интеркалятов в ДЛК порядка 20 (1009 элементов). Отдельные вычислительные эксперименты были выполнены в однопоточном режиме, их длительность составила до 13 суток. В составе полученного спектра присутствуют ЛК
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
1 3 0 4 2 6 8 5 9 7 11 13 10 14 12 16 18 15 19 17
2 0 4 1 3 7 5 9 6 8 12 10 14 11 13 17 15 19 16 18
3 4 1 2 0 8 9 6 7 5 13 14 11 12 10 18 19 16 17 15
4 2 3 0 1 9 7 8 5 6 14 12 13 10 11 19 17 18 15 16
5 15 7 8 9 10 1 18 17 16 19 3 2 6 4 13 12 14 0 11
6 16 17 18 13 19 12 14 0 11 9 8 7 15 1 10 2 5 4 3
7 5 9 15 8 18 10 16 1 17 2 19 4 3 6 14 13 11 12 0
8 9 15 7 5 17 16 1 18 10 6 4 3 2 19 0 11 12 14 13
9 7 8 5 15 16 18 17 10 1 4 2 6 19 3 11 14 0 13 12
10 14 12 11 19 2 13 4 3 15 5 0 17 18 16 8 9 6 7 1
11 19 14 12 10 3 15 13 4 2 18 16 0 17 5 7 1 9 6 8
12 10 19 14 11 4 2 15 13 3 17 5 16 0 18 6 8 1 9 7
13 17 18 6 16 11 14 0 19 12 1 7 15 9 8 3 5 4 10 2
14 11 10 19 12 13 3 2 15 4 0 18 5 16 17 9 7 8 1 6
15 8 5 9 7 1 17 10 16 18 3 6 19 4 2 12 0 13 11 14
16 18 6 13 17 12 0 19 11 14 8 15 9 1 7 2 4 10 3 5
17 6 13 16 18 14 19 11 12 0 7 9 1 8 15 5 10 3 2 4
18 13 16 17 6 0 11 12 14 19 15 1 8 7 9 4 3 2 5 10
19 12 11 10 14 15 4 3 2 13 16 17 18 5 0 1 6 7 8 9
и
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
1 3 0 4 2 6 8 5 9 7 11 13 10 14 12 17 15 19 16 18
2 0 4 1 3 7 5 9 6 8 12 10 14 11 13 16 18 15 19 17
3 4 1 2 0 8 9 6 7 5 13 14 11 12 10 19 17 18 15 16
4 2 3 0 1 9 7 8 5 6 14 12 13 10 11 18 19 16 17 15
5 7 6 9 8 0 2 1 4 3 17 15 19 16 18 11 13 10 14 12
6 5 8 7 9 1 0 3 2 4 15 16 17 18 19 10 11 12 13 14
7 9 5 8 6 2 4 0 3 1 19 17 18 15 16 13 14 11 12 10
8 6 9 5 7 3 1 4 0 2 16 18 15 19 17 12 10 14 11 13
9 8 7 6 5 4 3 2 1 0 18 19 16 17 15 14 12 13 10 11
10 12 11 14 13 17 15 19 16 18 0 2 1 4 3 6 8 5 9 7
11 10 13 12 14 15 16 17 18 19 1 0 3 2 4 5 6 7 8 9
12 14 10 13 11 19 17 18 15 16 2 4 0 3 1 8 9 6 7 5
13 11 14 10 12 16 18 15 19 17 3 1 4 0 2 7 5 9 6 8
14 13 12 11 10 18 19 16 17 15 4 3 2 1 0 9 7 8 5 6
15 16 17 18 19 11 10 13 12 14 6 5 8 7 9 0 1 2 3 4
16 18 15 19 17 13 11 14 10 12 8 6 9 5 7 2 0 4 1 3
17 15 19 16 18 10 12 11 14 13 5 7 6 9 8 1 3 0 4 2
18 19 16 17 15 14 13 12 11 10 9 8 7 6 5 4 2 3 0 1
19 17 18 15 16 12 14 10 13 11 7 9 5 8 6 3 4 1 2 0
у которых соответственно 0 и 1500 интеркалятов, что позволяет усилить установленное ранее верхнее ограничение с a(20)<=11 до a(20)=0 на минимальное число интеркалятов в ЛК и усилить установленное ранее нижнее ограничение с a(20)>=1100 до a(20)>=1500 в числовом ряду https://oeis.org/A092237. Найденный квадрат, имеющий максимально известное на данный момент число интеркалятов для данной размерности, является неканоническим блочным вида 4x5, что уже попадалось ранее для ряда меньших порядков и что делает актуальным более подробное изучение свойств квадратов данного типа в перспективе...
В проекте RakeSearch (https://rake.boincfast.ru/rakesearch/) завершена обработка очередного (38-го) интересного ДЛК порядка 12
0 1 2 3 4 5 6 7 8 9 10 11
1 2 3 11 5 7 4 9 0 10 6 8
9 10 6 4 8 0 11 1 7 2 3 5
10 6 4 5 0 1 8 2 9 3 11 7
7 9 10 6 11 8 3 0 5 1 2 4
2 3 11 8 7 9 5 10 1 6 4 0
8 0 1 2 6 4 10 5 11 7 9 3
6 4 5 7 1 2 0 3 10 11 8 9
5 7 9 10 3 11 2 8 4 0 1 6
4 5 7 9 2 3 1 11 6 8 0 10
11 8 0 1 10 6 9 4 3 5 7 2
3 11 8 0 9 10 7 6 2 4 5 1
у которого 25540 диагональных трансверсалей и 541571814 ОДЛК, что позволяет ему занять 26-е место в соответствующем спектре, который на данный момент включает в своем составе 5711 элементов и доступен тут:
https://evatutin.narod.ru/spectra/spectrum_dls_odls_n12_xxxx_known_items.txt
Загруженные файлы:
В OEIS после подтверждения очередной серии правок добавлено описание двух новых числовых рядов:
* https://oeis.org/draft/A372922 — Число диагонализированных циклических диагональных латинских квадратов порядка N=2n+1
* https://oeis.org/draft/A372923 — Число диагонализированных циклических диагональных латинских квадратов порядка N=2n+1 с фиксированной первой строкой
Ждем подтверждения...
PS. Напомню, что данные числовые ряды были посчитаны летом прошлого года, терпеливо ждали своего часа и вот наконец дождались. Данный редкий тип квадратов интересен как минимум тем, что в спектрах числа диагональных трансверсалей в ДЛК они образуют компактную полоску в старшей части спектра (см. картинку в https://vk.com/wall162891802_2443), соответствующие значения в составе которой другими методами получить не удается. Данный тип квадратов теоретически объясняет, откуда берется эта полоска.
Серию вычислительных экспериментов со спектрами числа интеркалятов в ДЛК порядков 10-24 можно считать завершенной (по крайней мере пока). Напомню, что данные эксперименты выполнялись последние полгода на моей машине в однопоточном режиме: они относительно легкие для грида, а для однопоточного режима время счета составляет от нескольких часов до нескольких суток, что в общем то приемлемо (привет моим студентам, для которых оставить компьютер считать на ночь — уже подвиг! :). Эксперименты заключались в серии запусков (по нескольку десятков для каждой размерности), первым из которых было получение опорного спектра от какого-то специального типа ДЛК, существующего для данной размерности, а последующие были направлены на его расширение путем хождения по окрестностям, соответствующие картинки неоднократно публиковались (каждый квадратик с изображением спектра — отдельный запуск). В результате были получены как сами аппроксимации спектров, так и усилен ряд старых и получен ряд новых нижних оценок на мощности соответствующих спектров, что теперь добавлено в OEIS:
https://oeis.org/draft/A345760
В ходе экспериментов расчетный код неоднократно правился: были добавлены чекпоинты и ряд мелких удобных фишек, облегчающих обработку и анализ результатов.
Что дальше? Для порядков N=25 и выше время однопоточных запусков уже становится достаточно большим (от 2-3 недель), а это верный признак того, что пора переходить либо в многопоточный режим (т.е. переписать часть расчетного кода), либо в грид (тут весь код есть, нужно лишь время на организацию еще одного подпроекта, генерацию WU'шек и обработку результатов, включая досчет хвостов в однопоточном режиме), чем мы будем заниматься в перспективе по мере наличия свободного времени...
Для порядков 9<N<16 в ходе выполненных экспериментов возникла идея попробовать уйти из мира ДЛК в мир ЛК, поработать там, а потом вернуться обратно, для чего опять таки потребовалось поправить часть расчетного кода. Переход от ДЛК к ЛК осуществляется достаточно просто, фактически просто игнорированием ограничений на дублирование элементов на диагоналях, возврат от ЛК к ДЛК сложнее и потребовал выполнения диагонализации, которая, начиная с порядка N=16 и выше, становится вычислительно трудной (что опять таки потребовало модификации части кода, т.к. диагонализацию спектров ранее так мы не делали). Сама идея подобного расширения спектров хорошо себя зарекомендовала для порядков N<16, мощности спектров ДЛК удалось расширить подобным образом, что уже не удавалось сделать хождениями по окрестностям. Для порядков N=16 и, возможно, 17 и 18 в перспективе можно выполнить распределенную диагонализацию и дополнительно расширить соответствующие аппроксимации спектров, далее это уже не сработает ввиду чрезмерной вычислительной сложности. Попутно был построен ряд аппроксимаций спектров ЛК, что изначально не планировалось. С ними тоже можно дополнительно поработать в перспективе...
В общем наработана куча нового научного материала, который теперь надо структурировать и укомплектовать в большую статью, чем мы и будем заниматься с коллегами в ближайшей перспективе (успеть бы на RSD). Ну а далее, все алгоритмические приемы, отточенные на данных спектрах, вполне можно применить к спектрам других числовых характеристик (например, трансверсалей и диагональных трансверсалей). Можно попробовать построить спектры циклов различного типа, которые по своей сути близки к интеркалятам (являются одним из их логичных расширений), что интересно как само по себе, так и, возможно, позволит увеличить мощность текущих спектров. Работы впереди как всегда много, считаем дальше!
Загруженные файлы:
Подключите, пожалуйста команду kvt.kurskstu к соревнованию по проекту RakeSearch https://www.boincstats.com/stats/challenge/team/chat/1123
Здравствуйте! Имеется компьютер с процессором Intel Core i3-10105 4 ядра. Hyper Threading включен, то есть 8 потоков.
Так вот такой вопрос.
А имеет ли смысл запускать на нём одновременно больше, чем 4 задания?
Всё равно, хоть и 8 потоков и диспетчер задач показывает 8 логических процессоров, - но реально физических то только 4.
Просто будет ли того, если запустить не 4, а 7 параллельно работающих заданий RakeSearch - хоть какой-то выигрыш?
Или просто будут работать параллельно, но увеличится время выполнения заданий, а суммарного выигрыша не будет?
Ведь по логике физических ядер то только 4.
Здравствуйте! Проверьте пожалуйста, что не так с заданиями. Все задания завершаются на 3 секунде с ошибкой.
Rake search пишет что Joint search of ODLS12 with Gerasim project завершён на 101.328 и продолжает давать задания. Что это значит?