Исследование свойств диагональных латинских квадратов в проектах добровольных распределенных вычислений и не только...
Цитата: AenBleidd от 21.01.2023, 00:28Вообще, моё личное мнение таково: на ассемблер имело смысл переписывать критические учатки кода лет эдак 15-20 назад. Сейчас написанный вручную код крайне редко значительно быстрее кода сгененированного (но при этом очень серьезно экономится время самого программиста, который заместо выдавливания еще +1% производительности будет писать что-то полезное (новый алгоритм например)).
Это иногда бывает весьма эффективно для каких-нить специфических алгоритмов работы с битами, для векторизации вычислений, когда компилятор этого сделать не может и т.п. тонких ситуаций. В последнем случае, опять таки, на чистом асме писать уже смысла нет, т.к. есть интринсики...
PS. На что-либо катастрофически не хватает времени. Необходимо следить за текущими экспериментами (3 в проекте и 2 в однопоточном режиме у меня на машине), подбрасывать новые WU'шки, анализировать результаты (тут нагрузка на меня и на hoarfrost'а, который помогает с этим). В последнее время в университете наметилась следующая тенденция: мы выбираемся из демографической ямы 90-х, студентов стало поступать больше, вроде бы хорошо, т.к. это ставки (они считаются как раз от числа зачисленных на обучение). Но есть и оборотная сторона: работы свалилось сильно больше, т.к. работа считается по числу учебных групп в независимости от их численности (а она выросла). Если считать грубо, то на мне висит около 150 студентов разных курсов (помножьте это, например, на 5 лабораторных работ в семестре в среднем и поймете, сколько это возни), с десяток учебных групп, обучения по 2 профилям в бакалавриате и по 2 направленностям в магистратуре (не путать! :), около 30 УМК, заочка, аспиранты/магистранты, китайцы и всякие разовые поручения... Сейчас мы с Argut'ом завершаем верстку сборника материалов с прошедшего НСКФ, надеюсь скоро отдадим в печать. На кафедре мы начали подготовку к нашей осенней конференции (см. https://vk.com/wall-176831783_20 ), что тоже требует ряда усилий. Когда наконец появится время, в приоритете я вижу доделку приложения под Linux, а там посмотрим. Ну и разумеется текущую работу по поддержанию проекта в рабочем состоянии, которую я бросить не могу, как и преподавание, поэтому ждем и надеемся, что завтра будет легче...
Ранее нами была построена аппроксимация спектра числа диагональных трансверсалей в ДЛК порядка 14 путем следования уже ставшений традиционной стратегии: формирование опорного с последующим его расширением путем вращения 1 интеркалята, а затем 1 цикла (подробнее об этом можно почитать, а точнее — посмотреть в картинках, здесь: http://evatutin.narod.ru/evatutin_dls_spectra_m1_m2_d.pdf, соответствующая публикация готова, сборник находится на этапе издания, ждем). В качестве опорных спектров ранее были использованы следующие типы ДЛК:
* случайные
* случайные Брауны
* квадраты Гергели от циклических ДЛК
Попытаемся расширить данный спектр путем построения еще одного опорного спектра от квадратов Гергели, получаемых от всех возможных ДЛК порядка 7 (до этого были взяты только циклические). В результате соответствующего вычислительного эксперимента была сформирована коллекция квадратов Гергели, включающая в своем составе 1488 ДЛК. Далее по ней был построен спектр числа диагональных трансверсалей со следующими параметрами:
Min value = 52056, max value = 55356, width = 3301, cardinality = 482, density = 0.15
Затем было получено его расширение путем вращения 1 интеркалята, в результате чего мощность спектра увеличилась:
Min value = 36549, max value = 87914, width = 51366, cardinality = 41335, density = 0,80
На выполнение данной процедуры ушло 15,5 суток вычислительного времени процессора Core i7 4770 в 1 поток, новых элементов в интегральный спектр это не дало. В настоящее время в однопоточном режиме выполняется расширение полученного спектра путем вращения 1 цикла. Данный эксперимент теоретически можно было бы запустить и в проекте, а хвост потом досчитать в однопоточном режиме, но в проекте и так сейчас работает 3 эксперимента, конкретно по спектрам — диагонализация представителей спектров ДЛК порядка 13, в рамках которой на данный момент обработано около 21k ДЛК из 80k с небольшим.
2-трансверсали
Введем в рассмотрение новое понятие — 2-трансверсали, которые будем искать в парах ОДЛК и которыми будем считать такое множество из N ячеек ДЛК, которое является трансверсалью и в одном, и в другом квадрате пары. Аналогичным образом введем понятие диагональных 2-трансверсалей — все то же самое, только в множестве ячеек одна лежит на главной диагонали квадрата и одна — на побочной (как и ранее, ячейки могут совпадать в центре квадрата для квадратов нечетного порядка). Пример пары ОДЛК порядка 9 и одной из возможных диагональных 2-трансверсалей приведен на рисунке. Всего у данной пары ОДЛК
00 11 22 33 44 55 66 77 88
82 53 36 08 27 60 41 15 74
46 04 17 20 65 78 52 83 31
35 87 58 61 13 24 70 06 42
28 45 64 12 76 81 37 50 03
14 68 73 47 80 32 05 21 56
57 26 01 75 38 43 84 62 10
71 30 85 54 02 16 23 48 67
63 72 40 86 51 07 18 34 25
4 различных диагональных 2-трансверсали:
Transversal 1: 1 0 3 2 4 6 5 8 7
Transversal 2: 2 6 7 0 4 1 8 3 5
Transversal 3: 3 5 1 8 4 7 0 2 6
Transversal 4: 5 3 8 1 4 0 7 6 2
Зачем нам такой наворот над классическим определением (диагональной) трансверсали? Мотивация проста: для того, чтобы у данной пары ОДЛК существовал ДЛК, переводящий пару в тройку ВОДЛК, необходимо наличие у нее N не пересекающихся диагональных 2-трансверсалей (для перевода пары ОЛК в ВОЛК — N не пересекающихся 2-трансверсалей общего вида).
Проанализируем, как ведут себя 2-трансверсали в соотнесении с числовыми рядами, для чего необходимо реализовать их подсчет для заданной пары ОДЛК. Его будем осуществлять следующим образом: брать исходный ОДЛК, строить для него множество нужных трансверсалей (диагональных или общего вида), по очереди строить ортогональные соквадраты и для каждой из трансверсалей исходного ОДЛК проверять, является ли она трансверсалью в текущем рассматриваемом соквадрате. Можно поступить иначе: построить множества трансверсалей для каждого из квадратов пары по отдельности и затем найти их пересечение, но в данном случае для хранения трансверсалей потребуется в два раза больше памяти, что может быть критично для "тяжелых" квадратов с большим числом трансверсалей. Еще одним вариантом является построение специальной бинарной матрицы и поиск соответствующего покрытия DLX'ом напрямую по ней, однако данный подход более сложен в реализации, его пока оставим на сладкое (подробнее про подобные матрицы, покрытия к ним и задачи, которые можно решать подобным образом, тут: http://ceur-ws.org/Vol-2638/paper26.pdf).
Полные списки КФ ОДЛК у нас есть для порядков N<10, приступим к анализу 2-трансверсалей в них.
Для 2-трансверсалей общего вида получаются следующие числовые ряды:
1, 0, 0, 4, 10, 0, 2, 2, 2 — минимальное число 2-трансверсалей в парах ОДЛК порядка N
1, 0, 0, 4, 10, 0, 28, 96, 648 — максимальное число 2-трансверсалей в парах ОДЛК порядка N
1, 0, 0, 1, 1, 0, 3, 7, 66 — мощность спектра числа 2-трансверсалей в парах ОДЛК порядка N
Несложно заметить, что нижним ограничением на число 2-трансверсалей в ОДЛК, как и на число трансверсалей в ДЛК, является 2<=a(N) для всех N>1 ввиду того, что у каждого ДЛК есть как минимум 2 диагонали, являющиеся трансверсалями по определению (исключения: для N=1 они совпадают, для N=2 и N=3 ДЛК не существуют, а для N=6 не существуют ОДЛК). Аналогичным образом можно построить числовые ряды для диагональных 2-трансверсалей:
1, 0, 0, 0, 0, 0, 0, 0, 0 — минимальное число диагональных 2-трансверсалей в парах ОДЛК порядка N
1, 0, 0, 0, 0, 0, 14, 32, 140 — максимальное число диагональных 2-трансверсалей в парах ОДЛК порядка N
1, 0, 0, 1, 1, 0, 3, 4, 53 — мощность спектра числа диагональных 2-трансверсалей в парах ОДЛК порядка N
Ряд с минимальным числом диагональных 2-трансверсалей не особо интересен, т.к. состоит из одних нулей (скорее всего так же будет и для N>9).
Полученные числовые ряды являются новыми и будут добавлены в OEIS по мере подтверждения текущих правок.
PS. Для N=9 построение соответствующих спектров производится за время около 5 минут каждый, для бОльших размерностей затраты времени будут уже существенно больше.
Сегодня GERASIM@HOME начал выдавать задания Get Decic Fields. Что за зверь такой?
Полученные спектры числа 2-трансверсалей (диагональных и общего вида) для пар ОДЛК можно соотнести со спектрами числа трансверсалей (опять таки диагональных и общего вида соответственно) в ОДЛК (см. рисунки). Наглядно видно, что для фиксированного N одни значения, образующие один спектр, не являются подмножеством другого. Это можно очень просто пояснить теоретически. Допустим, в спектре ОДЛК присутствует квадрат A с числом трансверсалей X. По определению A имеет ортогональные соквадраты (т.к. он ОДЛК), а значит для него можно расчитать соответствующие элементы спектра 2-трансверсалей. В лучшем случае, если повезет, все X трансверсалей квадрата A будут трансверсалями одного из его соквадратов. Если же часть трансверсалей для выбранного соквадрата окажется некорректными, то число 2-трансверсалей пары ОДЛК будет меньше X. Отсюда следует, что если в спектре трансверсалей в ОДЛК есть значение X, то в спектре 2-трансверсалей в парах ОДЛК ему могут соответствовать несколько значений, меньших либо равных X и соответствующих разным соквадратам. Т.е. соотношение "меньше или равно" между мощностями спектров так установить не получится, в отличие от множества других пар числовых рядов, в которых похожие соотношения устанавливаются на базе того, что одно множество является подмножеством другого (например, ДЛК — это подмножество ЛК). То же самое касается и диагональных 2-трансверсалей по той же причине.
Однако при этом можно установить соотношения между минимальными и максимальными значениями спектров:
min_2-dt_odls_pairs(N) <= min_dt_odls(N)
max_2-dt_odls_pairs(N) <= max_dt_odls(N)
min_2-t_odls_pairs(N) <= min_t_odls(N)
max_2-t_odls_pairs(N) <= max_t_odls(N)
Цитата: Pavel Kirpichenko от 18.02.2023, 10:32Цитата: JjjJ от 16.02.2023, 21:09Сегодня GERASIM@HOME начал выдавать задания Get Decic Fields. Что за зверь такой?
Это приложение раньше проект NumberFields@home считал вообще-то... Хм..
чет подозрительно...
Сейчас действительно Gerasim считает приложение GetDecics_4.00_windows_x86_64.exe (оно из NumberFields).
Так вот вопрос, а потом результаты расчётов будут переданы авторам проекта NumberFields для объединения?
Или цель счёта - только тесты и отладка серверной части?
Спектры 2-трансверсалей в парах ОДЛК порядка 10
Возьмем имеющуюся у нас в распоряжении коллекцию из приблизительно 20 млн. КФ ОДЛК порядка 10 и посмотрим на нее на предмет наличия пар ОДЛК с 2-трансверсалями (диагональным и общего вида). Соответствующие вычислительные эксперименты, запущенные в однопоточном режиме каждый в 5 потоков, заняли около полутора суток, в результате получены следующие спектры:
* диагональные 2-трансверсали — {0, 1, 2, 3, 4, 8}, мощность 6;
* 2-трансверсали — {2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 16, 17, 19, 28}, мощность 17.
Рекордсменом (не единственным) по числу общих 2-трансверсалей является почти обыкновенная однушка
0123456789120478936537185902466987205134904637851284591620732570634891563284190778619234504395017628 0123456789741926503896523048715248971360836714920538016279546795083142497051862310847325962536890417
правда являющаяся ESODLS (КФы образующих ее квадратов совпадают), не SODLS, трансверсалей у ОДЛК в ее составе сравнительно немного (124/932), и тем не менее у нее рекордные 28 общих 2-трансверсалей. При этом общих диагональных 2-трансверсалей у нее нет.
Рекордсменом числу общих диагональных 2-трансверсалей также является однушка
0123456789123469085789507243619548062173586134790263098712453476189520471520369820975384167682915034 0123456789679503814230145976284269785031763280159494572638105841972306297831046513806249578506149273
У нее так же не много трансверсалей (128/932), она является SODLS для транспонирования от побочной диагонали, кроме 8 диагональных 2-трансверсалей имеет 28 2-трансверсалей общего вида, как и приведенная выше пара ОДЛК.
Результаты эксперимента позволяют сделать вывод о том, что наличие общих трансверсалей для пар ОДЛК порядка 10 является довольно редкой ситуацией, что в том числе объясняет сложности в поисках тройки ВОЛК/ВОДЛК, которую пока никому не удалось найти (если она существует в принципе). Чтобы из однушки получилась тройка необходимо, чтобы у ОДЛК в составе однушки было не менее N=10 общих трансверсалей (а лучше — сильно больше, как для других размерностей), да еще и чтобы среди них нашлось подмножество из N=10 попарно не пересекающихся. Будем искать...