Форум

Пожалуйста или Регистрация для создания записей и тем.

Исследование свойств диагональных латинских квадратов в проектах добровольных распределенных вычислений и не только...

НазадСтраница 167 из 191Далее

Спектры числа обобщенных симметрий в ОДЛК

Ранее нами была составлена коллекция типов обобщенных симметрий в ДЛК и ОДЛК, в результате чего в OEIS было добавлено 4 новых числовых ряда и сейчас в проекте RakeSearch один из подпроектов ищет ОДЛК порядка 10 как раз во 2-м парастрофическом срезе обобщенных симметрий. Между тем открытым остался вопрос о том, сколькими симметриями может обладать конкретный квадрат и ряд связанных с ним смежных вопросов (например, вопрос, поднятый в свое время whitefox'ом и связанный с вложенностью обобщенных симметрий, где частично его выводы подтвердились, а частично — нет). Изначально было принято решение ограничиться вычислением членов числового ряда, соответствующего квадратам с максимально возможным числом обобщенных симметрий, однако в процессе счета стало понятно, что и спектры тоже получаются достаточно интересными, а это значит, что попутно стоит посчитать и их (тем более, что это не сильно сложнее в вычислительном плане). Для этого была взята построенная ранее коллекция ОДЛК, по ней был осуществлен поиск, в результате которого получены следующие новые числовые ряды, не представленные в OEIS.

1, 0, 0, 96, 100, 0, 2, 2, 1, 1, 1, 1 — минимальное число обобщенных симметрий в ОДЛК порядка N (скорее всего далее ряд будет состоять из одних единиц)
1, 0, 0, 96, 100, 0, 294, 10752, 3888, a(10) >= 40, a(11) >= 1210, a(12) >= 16 — максимальное число обобщенных симметрий в ОДЛК порядка N
1, 0, 0, 1, 1, 0, 4, 15, 18, a(10) >= 7, a(11) >= 5, a(12) >= 5 — мощность спектра числа обобщенных симметрий в ОДЛК порядка N

Эксперименты для порядков N <= 7 выполняются мгновенно, для размерности N=8 потребовалось 11 минут в 1 поток на Core i7 4770, для размерности N=9 — 2,5 часа, для размерности N=10 — 113 часов. ОДЛК размерностей N=11 и N=12 обработать на одной машине уже проблематично, ввиду чего соответствующие расчеты были запущены в однопоточном режиме на сутки, полученные предварительные результаты представлены выше, в дальнейшем расчеты могут быть продолжены в проекте.

Ну и в заключении стоит привести пару интересных спектров:

N=9 - {1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 27, 36, 48, 54, 72, 108, 486, 3888}, 18 элементов, полный спектр

N=12 - {1, 2, 4, 8, 16}, 5 элементов, аппроксимация спектра

Видно, что спектр для размерности N=12 образован только степенями двойки, что достаточно интересно и неожиданно (по крайней мере на данный момент, возможно при более детальном анализе ситуация изменится и спектр будет расширен на другие значения, не равные 2^k). Для размерности N=9 в спектре присутствуют вполне определенные значения, для которых возможно существует аналитическая формула...

hoarfrost, prb и Шмяка отреагировали на эту запись.
hoarfrostprbШмяка

Спектры числа обобщенных симметрий в ДЛК порядка 1-8

Вслед за спектрами ОДЛК (см. https://vk.com/wall162891802_2252) произведем построение спектров числа обобщенных симметрий в ДЛК. Для этого при подходе "в лоб" необходимо сформировать все ДЛК заданного порядка N с использованием метода полного перебора, найти число обобщенных симметрий в каждом ДЛК и сформировать соответствующие спектры и числовые ряды. Для порядков N<=6 данная процедура выполняется практически мгновенно, для порядка N=7 на ее выполнение требуется около 1 минуты вычислительного времени процессора Core i7 4770 в 1 поток. Для порядка N=8 такой подход уже не сработает ввиду очень большого числа ДЛК, поэтому потребуется хитрить. Прежде всего, необходимо отметить, что число обобщенных симметрий является инвариантом главного класса ДЛК. Перестановки Px, Py и Pv могут измениться в зависимости от комбинации примененных M-преобразований, а вот число описываемых ими симметрий останется прежним, что позволяет вести обработку по одному квадрату из каждого главного класса с использованием разработанного ранее генератора КФ (см. недавно вышедшую статью про него: http://evatutin.narod.ru/evatutin_dls_scf_gen.pdf). При такой организации вычислительный эксперимент потребовал 1,5 часа вычислительного времени Core i7 4770 в 1 поток и был успешно завершен. В результате получены следующие числовые ряды:

1, 0, 0, 96, 12, 24, 1, 1, 1, 1, 1, 1 — минимальное число обобщенных симметрий в ДЛК порядка N
1, 0, 0, 96, 100, 24, 294, 10752, a(9) >= 3888, a(10) >= 40, a(11) >= 1210, a(12) >= 16 — максимальное число обобщенных симметрий в ДЛК порядка N
1, 0, 0, 1, 2, 1, 9, 22, a(9) >= 18, a(10) >= 7, a(11) >= 5, a(12) >= 5 — мощность спектра числа обобщенных симметрий в ДЛК порядка N

Все числовые ряды являются новыми и не присутствуют в OEIS. Расширение полученных рядов на размерности N=9 в перспективе возможно в проекте. Для порядков N >= 10 формирование верхних и нижних оценок на соответствующие члены в составе полученных числовых рядов возможно в перспективе с использованием генераторов ДЛК с обобщенными симметриями.

 

PS. Члены a(9)-a(12) для первого ряда и нижние ограничения на аналогичные члены двух последующих рядов взяты из предыдущей серии вычислительных экспериментов по ОДЛК ввиду того, что ОДЛК — это подмножество ДЛК. В перспективе данные нижние ограничения могут быть усилены.

hoarfrost и Шмяка отреагировали на эту запись.
hoarfrostШмяка

Ранее при построении спектра числа диагональных трансверсалей в ДЛК порядка 14 в качестве одного из шагов был использован опорный спектр от квадратов Гергели порядка 14, которые, в свою очередь, были получены от циклических ДЛК порядка 7. А что, если попробовать получить все возможные квадраты Гергели порядка 14 и построить спектр от них? Сказано, сделано! Соответствующие вычислительные эксперименты были выполнены в один поток на моей машине, вращение 1 интеркалята заняло 15 суток, последующее вращение 1 цикла — 32 суток, в результате чего были получены спектры со следующими параметрами:

* опорный от квадратов Гергели: 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
* Расширение вращением 1 цикла: Min value = 31014, max value = 87914, width = 56901, cardinality = 48769, density = 0.86

Объединение данных спектров с интегральным новых элементов, к сожалению, не дало. Полученный спектр из 48769 элементов по мощности сильно уступает полученному ранее от циклических квадратов Гергели (219251 элементов) виной чему является то, что для данной размерности расширение спектра производится целиком, а не поквадратно (поквадратно для N=14 очень долго). Этот факт надо будет учесть при построении спектров бОльших порядков.

PS. За время занятия программированием и работы с компами вообще приходится сталкиваться с кучей разных интересных глюков. То у 16-ядерного Xeon'а Windows Server показывает 3 ядра и BOINC Manager считает в 3 потока, то еще что... :) В данном эксперименте во время записи стрима с Василем Закиевым через Zoom (см. https://vk.com/wall162891802_2241 кто еще не видел, а точнее — не слышал :) окно данного расчетного GUI-приложения пропало и отказалось появляться обратно, Process Explorer начал говорить, что у данного приложения вообще окон нет и bring to front для него сделать нельзя, хотя считающие рядом аналогичные оконные приложения остались на месте. При этом однопоточная нагрузка на CPU осталось, было решено подождать и через несколько дней счета без возможности визуального контроля прогресса вычислений искомый результирующий файл со спектром таки был сформирован и появился в нужном месте, что не может не радовать :).

Шмяка отреагировал на эту запись.
Шмяка

перефразируя -- "не глючит только то что вообще не работает" )))

В ходе постобработки очередной партии результатов эксперимента по поиску ОДЛК порядка 10 в окрестностях обобщенных симметрий в парастрофических срезах найден ОДЛК (однушка)

0 1 2 3 4 5 6 7 8 9
1 2 0 4 5 6 7 9 3 8
2 7 8 9 6 1 3 5 0 4
8 4 9 5 7 0 1 3 2 6
9 0 4 8 3 7 5 6 1 2
6 3 1 7 0 9 8 2 4 5
3 6 5 2 9 8 4 0 7 1
7 9 6 0 8 4 2 1 5 3
5 8 7 1 2 3 9 4 6 0
4 5 3 6 1 2 0 8 9 7

у которого всего 652 трансверсали, что является новым рекордом и позволяет усилить соответствующую верхнюю оценку в числовом ряду A357514 с a(10)<=668 до a(10)<=652 и увеличить на единицу мощность соответствующего спектра (член a(10) ряда A350585) со 193 до 194.

Шмяка отреагировал на эту запись.
Шмяка

В проекте RakeSearch завершена обработка 13-го по счету интересного ДЛК порядка 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
5 3 4 2 0 1 7 8 9 10 11 6
11 7 9 8 10 6 5 1 3 2 4 0
7 9 11 10 6 8 3 2 4 0 5 1
6 8 10 9 11 7 1 3 2 4 0 5
2 0 1 5 3 4 10 11 6 7 8 9
10 6 8 7 9 11 0 5 1 3 2 4
3 4 5 0 1 2 9 10 11 6 7 8
9 11 7 6 8 10 4 0 5 1 3 2
4 5 3 1 2 0 11 6 7 8 9 10
8 10 6 11 7 9 2 4 0 5 1 3

с 26992 диагональными трансверсалями, у которого оказалось 740151578 ОДЛК, что позволяет расположиться данному квадрату на 14-м месте в соответствующем спектре:

http://evatutin.narod.ru/spectra/spectrum_dls_odls_n12_xxxx_known_items.txt

который в настоящее время включает в своем составе 5216 элементов. В настоящее время в том же подпроекте в обработке находится следующий по порядку (22-й) интересный ДЛК. Считаем...

hoarfrost и Шмяка отреагировали на эту запись.
hoarfrostШмяка

К предстоящим суперкомпьютерным дням (которые RSD и которые будут проводиться в МГУ в сентябре) нашим коллективом готовится статья с подробным описанием того, что такое диагонализация и где она используется в экспериментах с ДЛК (а используется она весьма неплохо как минимум в составе канонизатора, который дает нам КФ ОДЛК порядка 10 в коллекцию, и при работе со спектрами, что позволяет расширять их мощность там, где она уже не расширяется методами на базе окрестностей). В ходе написания статьи потребовалось уточнить и местами упростить некоторые формулы, ну а далее оказалось, что можно упростить и ряд преобразований! Код был поправлен, проверен и в настоящее время подготовлена новая версия расчетного модуля, которая в ближайшее время будет работать в проекте RakeSearch в эксперименте по распределенной диагонализации (WU'шки с именами *e1067_n13_distr_diag_*), ожидаемое сокращение вычислительных затрат — 2,5-3 раза. Сами WU'шки при этом короче не станут, просто некоторые из них будут отсекаться на ранней стадии обработки. Ждем добавления новой версии в проект и считаем дальше...

citerra, Pavel Kirpichenko и 3 отреагировали на эту запись.
citerraPavel KirpichenkoprbV0d01eyШмяка

Спектры числа обобщенных симметрий в парастрофических срезах в ОДЛК порядка 1-12

Вслед за спектрами числа обобщенных симметрий в ОДЛК (см. https://vk.com/wall162891802_2252) посчитаем аналогичные спектры для симметрий в парастрофических срезах. Для этого был организован вычислительный эксперимент с участием построенных ранее коллекций КФ ОДЛК, которые пригодились нам уже неоднократно. Для порядков 1-7 соответствующие эксперименты выполняются практически мгновенно, для порядка N=8 потребовалось 40 минут работы Core i7 4770 в 1 поток, для порядка N=9 — 10 ч. В результате были получены точные значения для числовых рядов, приведенных ниже.
Для более старших размерностей точные значения получить не представляется возможным ввиду огромной размерности пространства перебора, однако можно обработать (полностью или хотя бы частично) имеющиеся коллекции КФ ОДЛК и по результатам обработки наложить верхние и нижние ограничения на соответствующие члены числовых рядов. Для размерности N=10 была произведена полная обработка всех имеющихся в наличии КФ ОДЛК, на что потребовалось 783,5 ч работы процессора Core i7 4770 в 1 поток (на самом деле расчет был запущен в несколько потоков на всех свободных ядрах, не задействованных в других вычислительных экспериментах и расчетах в RakeSearch). Для размерностей N=11 и N=12 за 160 ч работы в однопоточном режиме (для каждой размерности) была произведена обработка части имеющихся в распоряжении КФ ОДЛК, для обработки всех нужны существенно большие вычислительные ресурсы, что в перспективе можно организовать в проекте. В результате были получены следующие числовые ряды:

6, 0, 0, 576, 600, 6, 2, 1, 1, 1, 1, 1 — минимальное число обобщенных симметрий в парастрофических срезах в ОДЛК порядка N (скорее всего далее ряд будет состоять из одних единиц)
6, 0, 0, 576, 600, 1764, 64512, 23328, a(10) >= 80, a(11) >= 7260, a(12) >= 16 — максимальное число обобщенных симметрий в парастрофических срезах в ОДЛК порядка N
1, 0, 0, 1, 1, 0, 3, 20, 24, a(10) >= 11, a(11) >= 8, a(12) >= 5 — мощность спектра числа обобщенных симметрий в парастрофических срезах в ОДЛК порядка N

Все найденные числовые ряды являются новыми и будут добавляться в OEIS по мере подтверждения серии текущих правок.

hoarfrost, citerra и 3 отреагировали на эту запись.
hoarfrostciterraPavel KirpichenkoprbШмяка

Спектры числа обобщенных симметрий в парастрофических срезах в ДЛК порядка 1-8

Заключительным аккордом с текущей серии вычислительных экспериментов стали эксперименты, направленные на построение спектров числа обобщенных симметрий в парастрофических срезах в ДЛК. Для этого, как и ранее (см. https://vk.com/wall162891802_2253) полным перебором было организовано построение всех ДЛК малых размерностей (N <= 6), по ним впоследствии практически мгновенно были построены спектры. Для размерности N=7 аналогичный эксперимент занял 5 минут при работе в 1 поток на Core i7 4770 без классов изоморфизма и практически мгновенно с их использованием (разумеется результаты совпали с точностью до образующих спектры подтверждающих квадратов). Размерность N=8 потребовала 5,5 ч вычислительного времени в 1 поток с использованием классов изоморфизма. Размерность N=9 аналогичным образом в перспективе может быть обработана в проекте, ну а более старшие размерности — эвристически. На данный момент у нас имеются оценки для ОДЛК порядков 9-12 (см. предыдущий анонс https://vk.com/wall162891802_2293), с учетом того, что ОДЛК — подмножество ДЛК, на начальном этапе они могут быть использованы в качестве грубых аппроксимаций для текущего эксперимента с целью последующего уточнения. Итого, получено 3 новых числовых ряда:

6, 0, 0, 576, 72, 144, 1, 1, 1, 1, 1, 1 — минимальное число обобщенных симметрий в парастрофических срезах в ДЛК порядка N (скорее всего далее ряд будет состоять из одних единиц)
6, 0, 0, 576, 600, 144, 1764, 64512, a(9) >= 23328, a(10) >= 80, a(11) >= 7260, a(12) >= 16 — максимальное число обобщенных симметрий в парастрофических срезах в ДЛК порядка N
1, 0, 0, 1, 2, 1, 12, 32, a(9) >= 24, a(10) >= 11, a(11) >= 8, a(12) >= 5 — мощность спектра числа обобщенных симметрий в парастрофических срезах в ДЛК порядка N

Информация о них будет добавлена в OEIS по мере подтверждения серии текущих правок.

hoarfrost, prb и Шмяка отреагировали на эту запись.
hoarfrostprbШмяка

Аналитическая формула для числа X-образных диагональных заполнений

Ранее мы считали число диагональных X-образных заполнений в ДЛК, для которых впоследствии были построены классы изоморфизма (т.н. линейки), которые используются для быстрого подсчета числа ДЛК заданного порядка и для генерации СКФ ДЛК и подсчета соответствующих им главных классов. Последовательность была получена полным перебором, члены в ее составе достаточно быстро растут, в состав ключевых слов было добавлено слово hard, что вызвало небольшую дискуссию в OEIS, в ходе которой было вспомнено (ранее мы это уже отмечали, но видимо забыли), что данный числовой ряд имеет прямую связь с карточными деками одного из видов, а для их числа известна аналитическая формула, используя которую, можно быстро посчитать члены данного ряда. Формула выражает искомую величину через факториал и биномиальные коэффициенты. Формулу проверил, формула правильная, ключевое слово hard не нужно! Спасибо Andrew Howroyd за наводку! Как получена данная формула даже подумать страшно... :)

b(n) — https://oeis.org/A000459
a(n) — https://oeis.org/A337303

PS. На конференциях и не только меня часто спрашивают: кому нужны ваши числовые ряды? Вот еще один пример того, что они нужны математикам, чтобы немного поломать голову и найти весьма нетривиальную связь между казалось бы совершенно разными математическими объектами.

hoarfrost, citerra и 3 отреагировали на эту запись.
hoarfrostciterraPavel KirpichenkoprbШмяка
НазадСтраница 167 из 191Далее
BOINC.RU