Исследование свойств диагональных латинских квадратов в проектах добровольных распределенных вычислений и не только...
Название ветки давно уже другое и обсуждаются здесь уже давно другие вопросы, связанные с квадратами и не связанные с Герасимом. Возможно стоит что-то поменять? Герасим вроде бы обсуждается в ряде других веток, или я не прав?
Эдуард Игоревич,
Вот Народ заходит на форум, смотрит > Российские проекты > Gerasim@home.
Заходит, а там ... Латинские квадраты, Симметричные кортежи
Что они там делают?
Ну, создайте себе тему, переместите туда квадраты, и пишите туда про квадраты.
А тему Gerasim@home. оставьте для Герасима.
p.s. А то что на форуме порядка нет - это Вы правы.
поздравляю с удачными итогами экспериментов и с днюхой! 
А ведутся ли дальнейшие работы по исследованию квадратов с помощью FPGA ?
появилась в интернете новая статья "две российские FPGA платы, полностью импортозамещающие 35 американских и китайских плат" https://habr.com/ru/articles/847582/
В ходе экспериментов со спектрами числа трансверсалей в ДЛК порядка 14 найден ДЛК
0 1 2 3 4 5 6 7 8 9 10 11 12 13
1 2 3 0 13 6 8 4 9 12 5 7 11 10
13 6 8 11 3 0 5 2 10 1 7 12 9 4
11 13 0 4 9 7 1 8 3 10 2 6 5 12
8 11 7 10 5 9 12 0 2 3 1 13 4 6
2 3 10 8 6 12 11 5 7 4 9 0 13 1
7 10 1 2 12 4 13 9 0 5 3 8 6 11
5 9 12 1 7 10 4 11 6 8 13 3 2 0
6 12 11 13 10 8 9 3 1 2 0 4 7 5
12 4 13 6 1 2 3 10 11 7 8 5 0 9
9 7 4 5 0 1 2 13 12 11 6 10 3 8
4 5 6 12 2 3 10 1 13 0 11 9 8 7
3 0 5 9 8 11 7 6 4 13 12 1 10 2
10 8 9 7 11 13 0 12 5 6 4 2 1 3
у которого 1714 диагональных трансверсалей, что позволяет усилить установленное ранее верхнее ограничение с a(14)<=5173 до a(14)<=1714 в числовом ряду https://oeis.org/A287647.
PS. Точнее говоря, найден данный квадрат был давно, еще год назад, но по какой-то причине не проанонсирован, восполняем досадный пробел.
В ходе экспериментов со спектрами числа трансверсалей в ДЛК порядка 14 найден ДЛК
0 1 2 3 4 5 6 7 8 9 10 11 12 13
1 2 3 0 5 9 7 6 10 13 11 12 8 4
6 7 5 9 11 10 13 4 1 8 0 3 2 12
7 6 9 13 12 11 4 5 2 10 1 0 3 8
11 10 8 12 6 3 1 2 13 0 9 5 4 7
4 5 11 10 0 1 8 12 6 2 7 13 9 3
13 4 10 8 3 0 12 11 7 1 6 9 5 2
5 9 13 4 1 12 10 8 3 11 2 7 6 0
10 8 12 11 7 4 0 1 9 3 5 2 13 6
12 11 0 1 9 6 2 3 4 7 13 8 10 5
9 13 4 5 2 8 11 10 0 12 3 6 7 1
3 0 7 6 10 2 9 13 12 5 8 4 1 11
8 12 1 2 13 7 3 0 5 6 4 10 11 9
2 3 6 7 8 13 5 9 11 4 12 1 0 10
у которого 1580 диагональных трансверсалей, что позволяет усилить установленное ранее верхнее ограничение с a(14)<=1714 до a(14)<=1580 в числовом ряду https://oeis.org/A287647.
В проекте RakeSearch завершена обработка очередного (48-го) интересного ДЛК порядка 12
0 1 2 3 4 5 6 7 8 9 10 11
1 2 3 4 5 0 11 6 7 8 9 10
6 11 10 9 8 7 4 3 2 1 0 5
4 5 0 1 2 3 8 9 10 11 6 7
9 8 7 6 11 10 1 0 5 4 3 2
7 6 11 10 9 8 3 2 1 0 5 4
5 0 1 2 3 4 7 8 9 10 11 6
10 9 8 7 6 11 0 5 4 3 2 1
11 10 9 8 7 6 5 4 3 2 1 0
3 4 5 0 1 2 9 10 11 6 7 8
8 7 6 11 10 9 2 1 0 5 4 3
2 3 4 5 0 1 10 11 6 7 8 9
у которого 25312 диагональных трансверсалей и 497890762 ОДЛК, что позволяет ему занять 36-е место в соответствующем спектре, который на данный момент включает в своем составе 5827 элементов и доступен тут:
https://evatutin.narod.ru/spectra/spectrum_dls_odls_n12_xxxx_known_items.txt
Загруженные файлы:
В ходе экспериментов со спектрами числа трансверсалей в ДЛК порядка 14 найден ДЛК
0 1 2 3 4 5 6 7 8 9 10 11 12 13
1 2 3 0 5 8 9 12 10 11 13 4 6 7
3 0 10 12 6 9 13 8 11 7 4 2 1 5
5 13 6 4 11 0 12 2 1 3 8 9 7 10
4 12 13 6 9 11 7 10 0 5 1 3 2 8
2 6 4 1 13 7 5 11 12 8 3 10 0 9
6 4 1 2 7 12 8 0 3 10 9 13 5 11
8 10 12 11 0 1 3 6 13 4 7 5 9 2
11 8 7 9 3 4 2 13 5 6 0 12 10 1
10 5 11 8 1 13 4 9 7 12 2 0 3 6
12 3 0 10 2 6 1 5 9 13 11 7 8 4
13 7 9 5 8 10 11 3 2 0 6 1 4 12
9 11 8 7 12 3 10 1 4 2 5 6 13 0
7 9 5 13 10 2 0 4 6 1 12 8 11 3
у которого 1446 диагональных трансверсалей, что позволяет усилить установленное ранее верхнее ограничение с a(14)<=1580 до a(14)<=1446 в числовом ряду https://oeis.org/A287647.
PS. То, что данная граница "зашевелилась" — большая удача, т.к. примерно за год расчетов до этого она не сдвигалась с места и было подозрение, что сдвинуть ее уже не получится, каждое усиление (сейчас и в перспективе будущих экспериментов) дается со все большим трудом. В настоящее время соответствующие эксперименты идут в несколько потоков на моей машине, для грида вычислительной работы мало, там ведутся расчеты в рамках других подпроектов и соответствующих задач. В ближайшей перспективе скорее всего в грид пойдет не порядок N=15, а случайный диагонализатор для спектров порядка N=14, программный код которого еще предстоит немного подрихтовать...
Постобработка результатов серии экспериментов, выполненных не так давно в проекте RakeSearch (https://rake.boincfast.ru/rakesearch/), почти завершена (в настоящее время все еще выполняется проверка одного из спектров на предмет правильности значений в его составе). На момент завершения экспериментов в проекте мощности спектров составили
* для диагональных трансверсалей — 294709 элементов;
* для трансверсалей общего вида — 282889 элементов.
Далее в ходе небольшой постобработки спектры можно расширить по примерно следующей стратегии:
1. Берутся новые значения спектра трансверсалей (t) (исходное множество было получено по итогам года расчета в проекте).
2. По ним строится спектр диагональных трансверсалей (dt), новые значения добавляются в соответствующий интегральный спектр.
3. Для новых значений последовательно выполняются процедуры расширения путем вращения 1 интеркалята и затем 1 цикла, спектр замыкается.
4. Далее по новым значениям спектра диагональных трансверсалей получаются новые значения спектра трансверсалей общего вида.
5. Опять выполняются процедуры вращения.
И т.д. до тех пор, пока спектры не перестанут меняться. Схематично этот процесс представлен ниже:
sp t -> 1 int rot -> 1 loop rot -> sp dt -> 1 int rot -> 1 loop rot -> sp t -> ... и т.д.
Данные расчеты выполняются последовательно в однопоточном режиме с длительностью каждой из итераций от нескольких минут до суток. В итоге за ~10 суток запусков спектры были слегка расширены и в настоящее время имеют следующие мощности:
* для диагональных трансверсалей — 297089 элементов (+2380 элементов);
* для трансверсалей общего вида — 290680 элементов (+7791 элемент).
В данном случае хорошо работает именно совместное расширение спектров, что следует запомнить в плане переходе к следующей серии экспериментов в отдаленной перспективе. Далее подобным образом указанная пара спектров уже не расширяется.
Следующим логичным шагом является выполнение диагонализации квадратов, образующих спектры. Данная процедура в совокупности с хождением по окрестностям отлично себя показала на меньших размерностях (10 <= N <= 13), но для N=14 есть нюанс, связанный с началом "комбинаторного взрыва". Для N=13 диагонализация с использованием разработанного ранее распределенного диагонализатора (см. https://evatutin.narod.ru/evatutin_ls_distr_diag.pdf) выполнялась около полугода в проекте. В данном случае и сами спектры мощнее приблизительно в 15 раз, и квадраты немного больше, и трансверсалей в них больше. Все эти факторы напрямую влияют на вычислительную сложность диагонализации, что по оценкам потребует не менее 50 лет расчетов в проекте при текущей реальной производительности (кстати, весьма неплохой, ранее в проекте Gerasim@Home она была кратно ниже, чему видимо есть ряд причин). Поэтому для данной размерности диагонализация в полном объеме выполняться не будет (внуки вырастут раньше, чем она закончится :), вместо этого мы продиагонализируем полностью младшую часть спектров (заодно оценим время и подгоним под него вычислительную сложность WU'шек), продиагонализируем топовый квадрат (что уже было сделано ранее, см. https://vk.com/wall162891802_2440), а среднюю и наиболее массовую часть спектра будем диагонализировать эвристически до тех пор, пока это будет иметь смысл (будет наблюдаться увеличение мощности спектров). Первая партия прицелочных WU'шек сформирована и с ближайшее время пойдет в расчет в совокупности с обновленной версией расчетника, далее будет анализ результатов и запуск соответствующего нового большого эксперимента длительностью от нескольких недель до нескольких месяцев. Считаем...
На предстоящий Национальный суперкомпьютерный форум (НСКФ 2024), традиционно проходящий в конце ноября — начале декабря, в состав нашей тематической секции по гридам подано 3 доклада по результатам исследования свойств диагональных латинских квадратов и расчетов в проекте добровольных распределенных вычислений RakeSearch на платформе BOINC и не только:
Новиков А.О., Ватутин Э.И. О построении нециклических пандиагональных латинских квадратов различных порядков
Ватутин Э.И. Классификация ошибок, возникающих при решении вычислительно сложных задач на платформе BOINC на базе опыта расчетов в проектах Gerasim@Home и RakeSearch
Ватутин Э.И., Манзюк М.О., Никитина Н.Н., Курочкин И.И., Альбертьян А.М. Построение спектров числа диагональных трансверсалей и трансверсалей общего вида в диагональных латинских квадратах порядка 14 в проекте добровольных распределенных вычислений RakeSearch на платформе BOINC
Кроме того, в рамках наших тематических секций и форума в целом планируется еще ряд докладов, так или иначе связанных с BOINC и российским сегментом добровольных вычислений (включая обзорный пленарный доклад в соавторстве с Курочкиным И.И. и рядом других соавторов из числа организаторов российских проектов добровольных вычислений). Как всегда должно быть интересно, ждем начала форума!