Исследование свойств диагональных латинских квадратов в проектах добровольных распределенных вычислений и не только...
Цитата: Pavel Kirpichenko от 09.09.2024, 07:18Цитата: Melter163 от 08.09.2024, 23:59А что, где-то нормальное пояснение есть??? Я потому вопрос и поднимал, но ответа так и не получил где понятным языком бы обьяснялось для чего все это делается
Я же поделился ссылкой на подкаст. Там все доступно вполне.
Перешёл в этот канал. Послушал. Извините, но всё равно не понял для чего ищем эти квадраты. Может здесь понятным языком объясните для чего их считаем? Для чего они пригодятся?
Цитата: evatutin от 13.09.2024, 21:55Цитата: Melter163 от 06.09.2024, 18:05Жалко, что направление РВ (распределённых вычислений) умирает как по мне. Проектов нормальных российских толком нету. Gerasim как я понял по названию приложений, на какой-то американский проект считает. RakeSearch фиг поймёшь что считает. Квадраты, а нафига они, для чего они, где пригодятся? Ни ответа, ни привета. Evatutin бестолку вопросы задавать, полный игнор, в смоём мире живёт. Посмотрел последние сообщения в этой ветке, ему задают вопрос, игнор полный. Жаль, что в России так складывается отношение к кранчерам и вообще к проектам. За рубежом есть проекты и довольно интересные. Но из-за политической ситуации никакого желания на них работать нет. Хочется круглосуточно на российские проекты работать, а понимания нету на что именно.
Где игнор? Где вопросы?
Ну прочите внимательней. Могу повторить:
Для чего ищем квадраты?
Где они могут пригодиться? В какой отрасли, сфере и т.д.
В проекте RakeSearch (https://rake.boincfast.ru/rakesearch/) завершена обработка очередного (47-го) интересного ДЛК порядка 12
0 1 2 3 4 5 6 7 8 9 10 11
1 2 0 4 5 3 8 9 10 11 6 7
6 8 10 7 9 11 0 3 1 4 2 5
8 10 6 9 11 7 1 4 2 5 0 3
10 6 8 11 7 9 2 5 0 3 1 4
2 0 1 5 3 4 10 11 6 7 8 9
5 3 4 1 2 0 11 8 7 10 9 6
4 5 3 0 1 2 9 6 11 8 7 10
11 7 9 8 10 6 5 1 3 2 4 0
9 11 7 6 8 10 4 0 5 1 3 2
7 9 11 10 6 8 3 2 4 0 5 1
3 4 5 2 0 1 7 10 9 6 11 8
у которого 25318 диагональных трансверсалей и 481418765 ОДЛК, что позволяет ему занять 37-е место в соответствующем спектре, который на данный момент включает в своем составе 5813 элементов и доступен тут:
https://evatutin.narod.ru/spectra/spectrum_dls_odls_n12_xxxx_known_items.txt
Загруженные файлы:
Не забываем, что с утра 28 сентября будет соревнование по отечественному проекту распределённых вычислений Gerasim@home https://www.boincstats.com/stats/challenge/team/chat/1125
Присоединяйтесь! Делайте вклад в науку и математические открытия!
Цитата: Yura12 от 27.09.2024, 19:38Не забываем, что с утра 28 сентября будет соревнование по отечественному проекту распределённых вычислений Gerasim@home https://www.boincstats.com/stats/challenge/team/chat/1125
Присоединяйтесь! Делайте вклад в науку и математические открытия!
Gerasim@Home в настоящее время к расчетам в области латинских квадратов отношения не имеет, вы видимо ошиблись веткой для анонса соревнований
В OEIS добавлены подтверждающие списки для спектров числа трансверсалей в ЛК порядков 1-8:
Напомню, что сами спектры впервые были посчитаны коллективом авторов (Alvaro R. Belmonte et al., см. описание к числовому ряду A309344) в июле 2019 г., в OEIS были добавлены только мощности найденных спектров без указания их состава. Независимо от указанного научного коллектива данные списки были перепроверены и добавлены в OEIS в текстовом виде с указанием значений, образующих спектры, и подтверждающих их квадратов, а также в графическом виде, по которому видно, что с большой долей вероятности число трансверсалей в ЛК подчиняется тем же закономерностям, что и в ДЛК (значение четно для квадратов четного порядка). Для подтверждения данной гипотезы в будущем необходимо построить аппроксимации спектров бОльших порядков N>8 и убедиться в этом с большей уверенностью, чем мы и будем заниматься в перспективе.
В проекте RakeSearch завершен масштабный 6-летний эксперимент по поиску ОДЛК порядка 10 в окрестностях обобщенных симметрий в парастрофических срезах, полученные результаты постобработаны и проанализированы, можно подводить первые итоги. Напомню кратко, как мы исторически пришли к данному поиску. Сперва поиск ОДЛК производился для выборок случайных ДЛК, что давало пополнение коллекции ОДЛК однушками, двушками и реже трешками, четверками и линиями-4. Чуть позднее данный поиск был заменен поиском по линейкам, что принципиально не изменило структуры находок. Далее был обнаружен такой интересный тип ДЛК как симметричные в одной плоскости, для которых был открыт еще целый ряд комбинаторных структур. Вслед за плоскостной симметрией была попытка поиска дважды симметричных ДЛК (в горизонтальной и вертикальной плоскостях одновременно), но чуть позже оказалось, что подобные ДЛК не существуют для порядков, отличных от N=4k, к которым порядок N=10 не относится. Из курса школьной геометрии известно, что кроме симметрий относительно прямой существуют также симметрии относительно точки, соответственно возникла идея попробовать поискать ДЛК порядка 10, обладающие данной центральной симметрией. В ходе реализации данной идеи выяснилось, что центрально-симметричные ДЛК не существуют для порядков N=4k+2, к которым относится порядок N=10, однако чуть позже было показано, что симметрия может быть частичной: M ячеек квадрата могут иметь значения, расставленные в соответствии с симметрией, а остальные N^2-M — произвольным образом. Среди таких частично центрально-симметричных ДЛК был найден ряд интересных ОДЛК, в том числе входящих в состав редких комбинатрных структур, включающих в своем составе ДЛК с 10 ОДЛК. Далее было показано, что найденные симметрии могут быть описаны не только геометрически, но и с использованием достаточно несложных математических формул. От формул можно перейти к дискретной табличной форме записи, а от нее — к перестановкам, описывающим симметрию. Такие симметрии, названные обобщенными, уже невозможно увидеть "глазом" (геометрически), однако математически они прекрасно описываются и соответствующие им ОДЛК обладают рядом интересных свойств, в первую очередь — входят в состав редких комбинаторных структур (другой точкой зрения на обобщенные симметрии являются автоморфизмы в ЛК/ДЛК, два этих понятия тождественны и могут быть преобразованы друг в друга взаимно однозначно). Далее было показано, что из всего множества из 10! перестановок можно выделить 42 класса по структурам мультимножеств длин циклов, ну а еще чуть далее было выяснено, что каждая обощенная симметрия описывается тройкой перестановок (Px, Py, Pv) из данных классов. Не все многообразие из 42^3 комбинаций существуют, не у всех есть интересные окрестности, однако у некоторых они действительно интересны и... был начат текущий эксперимент. Чуть позднее к описанию обобщенных симметрий еще были добавлены парастрофические преобразования, с их участием пространство поиска было увеличено с 1 до 6 парастрофических срезов, мелкие WU'шки были аггрегированы в состав более крупных для более быстрого счета в условиях наличия других подпроектов и стартовал объемный в плане вычислений текущий эксперимент в его конечной версии. Для выбранной случайной комбинации перестановок (Px, Py) из заданных классов происходил подбор случайной подходящей перестановки Pv, далее на ограниченном множестве WU'шек производилась разведка данной области, и если область оказывалась интересной (находились редкие комбинаторные структуры), она исследовалась более подробно до тех пор, пока новые интересные редкие комбинаторные структуры не переставали появляться. И вот так, клеточка за клеточкой и был выполнен текущий эксперимент: были проанализированы 6 парастрофических срезов по 42^2 клеточек в каждом. Для не интересных окрестностей выполнялась только разведка путем обсчета 10 тыс. WU'шек на удалениях M in {50, 60, 70, 80}, для интересных производилось более подробное исследование партиями по 100 тыс. WU'ек на тех же удалениях. Наиболее интересные области (например, 1-(1,31), 1-(4,31) и др.) были проанализированы в общей сложности с использованием более чем 1,5 млн. WU'шек и если в них и осталось что-то интересное и нами не найденное, то с очень маленькой вероятностью. В итоге по результатам обработки данных эксперимента был сформирован следующий перечень редких комбинаторных структур:
2 CFs - 18735
3 CFs - 45446
LINE3 (B):2 - 41458, 32:1, where:
2 CFs - 18735
3 CFs - 22723
LINE4 (C):1 - 116, where:
2 CFs - 4
4 CFs - 112
LINE4 (C):2 - 116, where:
2 CFs - 4
4 CFs - 112
LINE5 (D):1 - 17, where:
3 CFs - 17
LINE5 (D):2 - 34, where:
3 CFs - 34
LOOP4 (E):2 - 2248, where:
1 CFs - 2
2 CFs - 138
3 CFs - 1464
4 CFs - 644
1TO3 (F):1 - 348, where:
4 CFs - 348
1TO3 (F):3 - 116, where:
4 CFs - 116
1TO4 (G):1 - 1290, where:
3 CFs - 882
5 CFs - 408
1TO4 (G):4 - 543, where:
3 CFs - 441
5 CFs - 102
1TO5 (k):1 - 10, where:
6 CFs - 10
1TO5 (k):5 - 2, where:
6 CFs - 2
1TO6 (H):1 - 42, where:
4 CFs - 24
7 CFs - 18
1TO6 (H):6 - 11, where:
4 CFs - 8
7 CFs - 3
1TO7 (h):1 - 7, where:
8 CFs - 7
1TO7 (h):7 - 1, where:
8 CFs - 1
1TO8 (I):1 - 48, where:
5 CFs - 32
9 CFs - 16
1TO8 (I):8 - 10, where:
5 CFs - 8
9 CFs - 2
RHOMBUS3 (J):2 - 9, where:
5 CFs - 9
RHOMBUS3 (J):3 - 6, where:
5 CFs - 6
RHOMBUS4 (K):2 - 73, where:
3 CFs - 2
4 CFs - 23
5 CFs - 32
6 CFs - 16
RHOMBUS4 (K):4 - 34, where:
3 CFs - 1
4 CFs - 17
5 CFs - 8
6 CFs - 8
FISH (N):1 - 7, where:
4 CFs - 1
6 CFs - 6
FISH (N):2 - 11, where:
4 CFs - 2
6 CFs - 9
FISH (N):4 - 4, where:
4 CFs - 1
6 CFs - 3
TREE1 (V):1 - 2, where:
4 CFs - 2
TREE1 (V):2 - 1, where:
4 CFs - 1
TREE1 (V):3 - 1, where:
4 CFs - 1
CROSS (X):1 - 16, where:
6 CFs - 16
CROSS (X):2 - 4, where:
6 CFs - 4
CROSS (X):4 - 4, where:
6 CFs - 4
DAEDALUS10 (i):1 - 6, where:
12 CFs - 6
DAEDALUS10 (i):2 - 4, where:
12 CFs - 4
DAEDALUS10 (i):4 - 1, where:
12 CFs - 1
DAEDALUS10 (i):10 - 1, where:
12 CFs - 1
FLYER (j):1 - 2, where:
8 CFs - 2
FLYER (j):2 - 3, where:
8 CFs - 3
FLYER (j):4 - 3, where:
8 CFs - 3
VENUS (l):1 - 1, where:
5 CFs - 1
VENUS (l):2 - 3, where:
5 CFs - 3
VENUS (l):4 - 1, where:
5 CFs - 1
DAEDALUS8 (m):1 - 2, where:
6 CFs - 2
DAEDALUS8 (m):2 - 2, where:
6 CFs - 2
DAEDALUS8 (m):4 - 1, where:
6 CFs - 1
DAEDALUS8 (m):8 - 1, where:
6 CFs - 1
RHOMBUS5 (n):2 - 4, where:
5 CFs - 4
RHOMBUS5 (n):5 - 1, where:
5 CFs - 1
1TO10 (o):1 - 5, where:
6 CFs - 5
1TO10 (o):10 - 1, where:
6 CFs - 1
ROBOT (p):1 - 4, where:
5 CFs - 4
ROBOT (p):2 - 4, where:
5 CFs - 4
ROBOT (p):4 - 2, where:
5 CFs - 2
STINGRAY (q):1 - 1, where:
5 CFs - 1
STINGRAY (q):2 - 3, where:
5 CFs - 3
STINGRAY (q):3 - 1, where:
5 CFs - 1
Как уже было отмечено выше, многие из перечисленных выше структур другими методами не находятся в принципе. Напомню также, что данный эксперимент стартовал в проекте Gerasim@Home в 2018 году и был успешно завершен уже в проекте RakeSearch в сентябре 2024 года в аккурат на мой день рождения (вместе с еще одним параллельно выполнявшимся экспериментом по спектрам, бывает же так :), отдельный анонс с его результатами скоро будет). На данный момент поиск ОДЛК в окрестностях обобщенных симметрий завершен, число найденных КФ ОДЛК порядка 10 перевалило за 26,5 млн., будем готовить серию статей по его результатам. В ближайшее время поиск ОДЛК порядка 10 будет продолжен другими методами, идеи, где можно попытаться найти что-то интересное есть и еще, надо лишь найти время на их практическое воплощение...
Загруженные файлы:
Завершена основная часть расчетов, направленная на построение спектра числа трансверсалей в ДЛК порядка 14. Напомню, что стратегия данного эксперимента заключалась в формировании некоторого опорного спектра от какого-то источника квадратов (другого спектра, генератора квадратов одного из типов, левый столбец на картинке во вложении) с последующим его расширением путем хождения по окрестностям квадратов, образующих опорный спектр, путем поворота 1 интеркалята и 1 цикла (средний и правый столбцы). Данный эксперимент занял в общей сложности чуть более 1 года расчетов, в которых WU'шки забрасывались в проект RakeSearch партиями, после обсчета очередной партии и постобработки результатов формировалась новая партия и т.д. до тех пор, пока размер партии после очередной итерации запуска не становился слишком маленьким, время счета не начинало лимитироваться постоянными вычислениями в режиме досчета хвоста, и расчет в итоге переводился в однопоточный режим. Результаты расчетов в графическом виде представлены во вложении, в настоящее время полученные спектры проходят финальную проверку корректности, что выполняется до 10 суток в однопоточном режиме в зависимости от мощности полученного спектра. Необходимость данной проверки продиктована тем, что вычисления в проекте выполнялись с кворумом 1, что с одной стороны позволило выполнить расчеты за год, а не за два, а с другой привело к появлению небольшого числа ошибок среди значений спектров (видимо в проекте есть небольшое количество сбойных машин, у которых либо память, либо разгон/перегрев редко, но приводят к появлению сбойных значений в спектрах). На данный момент таковых сбойных значений уже найдено 3, проверка продолжается. По ее завершению спектры будут объединены в единый интегральный спектр, с помощью него возможно получится немного расширить полученный ранее спектр числа диагональных трансверсалей в ДЛК порядка 14, далее результаты будут анонсированы и выложены в свободный доступ. После этого перейдем к аналогичным экспериментам для порядка 15, который в данном направлении экспериментов является последним, для которого можно построить полный спектр мощностью в несколько миллионов значений. Начиная с порядка 16 это уже весьма проблематично как ввиду очень большой мощности спектра, так и ввиду длительности соответствующих вычислительных экспериментов.
Загруженные файлы:
Цитата: evatutin от 29.09.2024, 18:02Gerasim@Home в настоящее время к расчетам в области латинских квадратов отношения не имеет, вы видимо ошиблись веткой для анонса соревнований
Так ветка-то про Gerasim@home. (посмотрите url ветки).
И про проект, и про вэб-сайт Герасима, и про соревнование в Герасиме тоже.
Что в этой ветке делают квадраты какбэ непонятно.
А где ещё писать о Герасиме как не в ветке про Герасим?