Исследование свойств диагональных латинских квадратов в проектах добровольных распределенных вычислений и не только...
Цитата: evatutin от 26.02.2023, 22:53С момента начала вычислительных экспериментов с числовыми рядами, связанными с ДЛК, нами был посчитан и добавлен/обновлен в OEIS в общей сложности 91 числовой ряд. Информация о данных рядах собиралась на моей страничке с небольшим структурированием по категориям, но уже довольно давно стало понятно, что пользоваться ей становится неудобно. В результате, со второй попытки (первая (табличная) в итоге не понравилась), в описании добавленных/обновленных рядов была наведена красота. Кроме того, были добавлены ссылки на известные числовые ряды по ЛК, которые время от времени необходимы для описаний добавляемых рядов по ДЛК. С новой версией можно ознакомиться тут: http://evatutin.narod.ru/oeis.html . На данный момент проделана большая работа, но и многое еще предстоит сделать. Кодим, описываем, считаем дальше...
С момента начала вычислительных экспериментов с числовыми рядами, связанными с ДЛК, нами был посчитан и добавлен/обновлен в OEIS в общей сложности 91 числовой ряд. Информация о данных рядах собиралась на моей страничке с небольшим структурированием по категориям, но уже довольно давно стало понятно, что пользоваться ей становится неудобно. В результате, со второй попытки (первая (табличная) в итоге не понравилась), в описании добавленных/обновленных рядов была наведена красота. Кроме того, были добавлены ссылки на известные числовые ряды по ЛК, которые время от времени необходимы для описаний добавляемых рядов по ДЛК. С новой версией можно ознакомиться тут: http://evatutin.narod.ru/oeis.html . На данный момент проделана большая работа, но и многое еще предстоит сделать. Кодим, описываем, считаем дальше...
Цитата: evatutin от 28.02.2023, 13:25Спектры диагональных 2-трансверсалей в ОДЛК порядка 11
Возьмем имеющуюся в наличии коллекцию КФ ОДЛК порядка 11, полученную ранее в результате серии вычислительных экспериментов, и произведем с ее использованием построение спектра диагональных 2-трансверсалей. Напомню, что коллекция на данный момент состоит из 4 частей: 1-я и 2-я включают в своем составе примерно по миллиону КФ ОДЛК и получены случайным поиском ОДЛК + достройкой соответствующих им комбинаторных структур (в качестве исходного генератора ДЛК были взяты центрально-симметричные квадраты); 3-я включает в своем составе около полумиллиона КФ ОДЛК, полученных аналогичным образом, но за вычетом однушек; 4-я построена отталкиваясь от диагонализации циклических ЛК + достройка соответствующих комбинаторных структур. В результате вычислительного эксперимента, выполнявшегося 9 суток в однопоточном режиме (другие ядра были заняты), получен следующий спектр мощностью 37 (нижнее ограничение на значение члена a(11) соответствующего числового ряда):
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 20, 21, 23, 24, 26, 28, 30, 35, 38, 40, 66, 126, 176, 188, 190, 203, 238, 320}
Максимальное значение спектра 320 получено в следующей паре ОДЛК:
0123456789A23145679A806978A021435789A0213546143567980A29A8021346573546798A20180A21345769A2013456978465798A012357698A02314 0123456789A465798A0123143567980A26978A0214359A802134657A201345697823145679A803546798A201789A021354657698A0231480A21345769
Оба ДЛК являются DSODLS и ESODLS для ряда преобразований кроме двух транспонирований.
Спектры диагональных 2-трансверсалей в ОДЛК порядка 11
Возьмем имеющуюся в наличии коллекцию КФ ОДЛК порядка 11, полученную ранее в результате серии вычислительных экспериментов, и произведем с ее использованием построение спектра диагональных 2-трансверсалей. Напомню, что коллекция на данный момент состоит из 4 частей: 1-я и 2-я включают в своем составе примерно по миллиону КФ ОДЛК и получены случайным поиском ОДЛК + достройкой соответствующих им комбинаторных структур (в качестве исходного генератора ДЛК были взяты центрально-симметричные квадраты); 3-я включает в своем составе около полумиллиона КФ ОДЛК, полученных аналогичным образом, но за вычетом однушек; 4-я построена отталкиваясь от диагонализации циклических ЛК + достройка соответствующих комбинаторных структур. В результате вычислительного эксперимента, выполнявшегося 9 суток в однопоточном режиме (другие ядра были заняты), получен следующий спектр мощностью 37 (нижнее ограничение на значение члена a(11) соответствующего числового ряда):
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 20, 21, 23, 24, 26, 28, 30, 35, 38, 40, 66, 126, 176, 188, 190, 203, 238, 320}
Максимальное значение спектра 320 получено в следующей паре ОДЛК:
0123456789A23145679A806978A021435789A0213546143567980A29A8021346573546798A20180A21345769A2013456978465798A012357698A02314 0123456789A465798A0123143567980A26978A0214359A802134657A201345697823145679A803546798A201789A021354657698A0231480A21345769
Оба ДЛК являются DSODLS и ESODLS для ряда преобразований кроме двух транспонирований.
Цитата: evatutin от 28.02.2023, 22:35На youtube-канале конференции НСКФ, которая проходила в конце ноября — начале декабря 2022 г. в Переславле-Залесском, выложены видео докладов нашей секции по гридам:
https://www.youtube.com/watch?v=0x4SWfkFxsw&list=PLImxsJTJoZMMmvj0KO-CXTRlfKddPRNwHАнонс этого события ранее уже был сделан hoarfrost'ом. Среди них есть два моих доклада по методам построения спектров быстровычислимых числовых характеристик ДЛК и по классификации типов и свойств ДЛК, ознакомиться с которыми можно здесь:https://www.youtube.com/watch?v=-1f9m7UY-CMhttps://www.youtube.com/watch?v=CsSou_imtP0В настоящее время мы завершаем формирование сборника лучших докладов по результатам работы нашей группы секций (фактически маленькая конференция в рамках общей) и скоро отдадим его в печать.
На youtube-канале конференции НСКФ, которая проходила в конце ноября — начале декабря 2022 г. в Переславле-Залесском, выложены видео докладов нашей секции по гридам:
Цитата: evatutin от 08.03.2023, 17:06Спектры 2-трансверсалей в парах ОДЛК порядка 11
Возьмем имеющуюся в наличии коллекцию КФ ОДЛК порядка 11, полученную ранее в результате серии вычислительных экспериментов, и произведем с ее использованием построение спектра 2-трансверсалей. В результате вычислительного эксперимента, выполнявшегося ~11 суток в однопоточном режиме на Core i7 4770, получен спектр мощностью 35 элементов (нижнее ограничение на значение члена a(11) соответствующего числового ряда):
{2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 21, 22, 24, 26, 28, 29, 32, 33, 36, 38, 40, 42, 44, 62, 88, 122, 1782}
Максимальное значение в составе спектра (1782) получено в следующей паре ОДЛК:
0123456789A23145679A806978A021435789A0213546143567980A29A8021346573546798A20180A21345769A2013456978465798A012357698A02314 0123456789A57698A023149A802134657143567980A2A2013456978789A0213546465798A012323145679A806978A02143580A213457693546798A201
Оба ДЛК являются DSODLS и ESODLS для целого множества комбинаций эквивалентных M-преобразований, в том числе включающих отражения от обоих диагоналей.
Спектры 2-трансверсалей в парах ОДЛК порядка 11
Возьмем имеющуюся в наличии коллекцию КФ ОДЛК порядка 11, полученную ранее в результате серии вычислительных экспериментов, и произведем с ее использованием построение спектра 2-трансверсалей. В результате вычислительного эксперимента, выполнявшегося ~11 суток в однопоточном режиме на Core i7 4770, получен спектр мощностью 35 элементов (нижнее ограничение на значение члена a(11) соответствующего числового ряда):
{2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 21, 22, 24, 26, 28, 29, 32, 33, 36, 38, 40, 42, 44, 62, 88, 122, 1782}
Максимальное значение в составе спектра (1782) получено в следующей паре ОДЛК:
0123456789A23145679A806978A021435789A0213546143567980A29A8021346573546798A20180A21345769A2013456978465798A012357698A02314 0123456789A57698A023149A802134657143567980A2A2013456978789A0213546465798A012323145679A806978A02143580A213457693546798A201
Оба ДЛК являются DSODLS и ESODLS для целого множества комбинаций эквивалентных M-преобразований, в том числе включающих отражения от обоих диагоналей.
Цитата: evatutin от 08.03.2023, 18:17В журнале Телекоммуникации, входящем в перечень ВАК, опубликована статья
В ней наиподробнейшим способом рассмотрено устройство генератора СКФ ДЛК, который впоследствии был использован в ряде вычислительных экспериментов, которые без него либо в принципе не реализуемы ввиду необходимости огромных вычислительных затрат, либо выполнялись бы очень долго (месяцами — годами на грид). Напомню вкратце, что использование данного генератора снижает необходимые вычислительные затраты в ряде экспериментов на 3-4 порядка. Теперь самое время взяться за описание вычислительных экспериментов, которые были выполнены с его использованием...
В журнале Телекоммуникации, входящем в перечень ВАК, опубликована статья
В ней наиподробнейшим способом рассмотрено устройство генератора СКФ ДЛК, который впоследствии был использован в ряде вычислительных экспериментов, которые без него либо в принципе не реализуемы ввиду необходимости огромных вычислительных затрат, либо выполнялись бы очень долго (месяцами — годами на грид). Напомню вкратце, что использование данного генератора снижает необходимые вычислительные затраты в ряде экспериментов на 3-4 порядка. Теперь самое время взяться за описание вычислительных экспериментов, которые были выполнены с его использованием...
Цитата: evatutin от 09.03.2023, 19:27Василь Закиев, автор телеграм-канала, посвященного распределенным вычислениям (https://t.me/gridcomputing), попросил пообщаться с ним на предмет того, что такое наши ОДЛК, кому это надо и зачем. Пообщались, с результатам общения в формате подкаста можно ознакомиться здесь: https://t.me/gridcomputing/21. Интересующимся рекомендую к прослушиванию :).
PS. Если остались/появились какие-либо вопросы, которые мы не осветили, пишите, рассмотрим в следующий раз...
Василь Закиев, автор телеграм-канала, посвященного распределенным вычислениям (https://t.me/gridcomputing), попросил пообщаться с ним на предмет того, что такое наши ОДЛК, кому это надо и зачем. Пообщались, с результатам общения в формате подкаста можно ознакомиться здесь: https://t.me/gridcomputing/21. Интересующимся рекомендую к прослушиванию :).
PS. Если остались/появились какие-либо вопросы, которые мы не осветили, пишите, рассмотрим в следующий раз...
Цитата: evatutin от 09.03.2023, 22:40Пока у меня на машине в несколько потоков считаются младшие части спектров числа 2-трансверсалей (диагональных и общего вида) в парах ОДЛК порядка 12 (первые результаты будут завтра), немного схитрим и построим сразу старшие части данных спектров по известной клике из 4 попарно-ортогональных ДЛК (см. числовой ряд A328873 в OEIS). Для этого пришлось немного видоизменить имеющийся в наличии код, результаты ниже.
Спектр диагональных 2-трансверсалей (старшая часть): {32, 34, 36, 38}
Спектр 2-трансверсалей (старшая часть): {72, 108}
Пока у меня на машине в несколько потоков считаются младшие части спектров числа 2-трансверсалей (диагональных и общего вида) в парах ОДЛК порядка 12 (первые результаты будут завтра), немного схитрим и построим сразу старшие части данных спектров по известной клике из 4 попарно-ортогональных ДЛК (см. числовой ряд A328873 в OEIS). Для этого пришлось немного видоизменить имеющийся в наличии код, результаты ниже.
Спектр диагональных 2-трансверсалей (старшая часть): {32, 34, 36, 38}
Спектр 2-трансверсалей (старшая часть): {72, 108}
Цитата: evatutin от 09.03.2023, 23:14Аналогично рассмотренному выше (см. https://vk.com/wall162891802_2242) произведем построение старшей части спектра числа диагональных 2-трансверсалей в парах ОДЛК порядка 13, для чего возьмем известную клику MODLS от циклических ЛК/ДЛК. В результате ее обработки получен следующий спектр (старшая часть):
{108, 147, 193, 277, 304, 328, 397, 506, 522, 596, 714, 720, 834, 992}
мощностью 14 элементов. Для аналогичного спектра числа 2-трансверсалей общего вида так уже сделать не получится, т.к. число трансверсалей велико и не поместится (либо с трудом поместится) в оперативную память. Для этого в перспективе надо будет схитрить: сделать специальную бинарную матрицу покрытия (следуя стратегии, подробно рассмотренной в статье https://ceur-ws.org/Vol-2638/paper26.pdf) и посчитать 2-трансверсали по ней, что скорее всего будет и быстрее, и не настолько требовательно к памяти.
Аналогично рассмотренному выше (см. https://vk.com/wall162891802_2242) произведем построение старшей части спектра числа диагональных 2-трансверсалей в парах ОДЛК порядка 13, для чего возьмем известную клику MODLS от циклических ЛК/ДЛК. В результате ее обработки получен следующий спектр (старшая часть):
{108, 147, 193, 277, 304, 328, 397, 506, 522, 596, 714, 720, 834, 992}
мощностью 14 элементов. Для аналогичного спектра числа 2-трансверсалей общего вида так уже сделать не получится, т.к. число трансверсалей велико и не поместится (либо с трудом поместится) в оперативную память. Для этого в перспективе надо будет схитрить: сделать специальную бинарную матрицу покрытия (следуя стратегии, подробно рассмотренной в статье https://ceur-ws.org/Vol-2638/paper26.pdf) и посчитать 2-трансверсали по ней, что скорее всего будет и быстрее, и не настолько требовательно к памяти.
Цитата: evatutin от 10.03.2023, 11:47Примерно за 20 часов счета в 3 потока завершено предварительное формирование спектров 2-трансверсалей отталкиваясь от ОДЛК порядка 12 имеющейся у нас в распоряжении коллекции. В каждом из них обработано примерно 1500 ОДЛК (где-то чуть меньше, где-то чуть больше, мизерная часть коллекции), результаты ниже.
Спектр диагональных 2-трансверсалей от интересных ОДЛК: {0, 1, 2, 3, 4, 6, 8}, 7 элементов в спектре (столько же было и в ОДЛК общего вида)
Спектр 2-трансверсалей от ОДЛК общего вида: {2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 26, 28, 30, 32, 34, 36, 38, 40, 44, 48}, 33 элемента в спектре
Спектр 2-трансверсалей от интересных ОДЛК: {2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 26, 28, 30, 32, 34, 36, 38, 40, 41, 42, 43, 44, 46, 48, 52, 56, 62}, 40 элементов в спектре
Объединяя все полученные ранее спектры, получаем:
Спектр диагональных 2-трансверсалей: {0, 1, 2, 3, 4, 6, 8, 32, 34, 36, 38}, 11 элементов
Спектр 2-трансверсалей: {2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 26, 28, 30, 32, 34, 36, 38, 40, 41, 42, 43, 44, 46, 48, 52, 56, 62, 72, 108}, 42 элемента
В дальнейшем мощность данных спектров можно попытаться расширить в ходе более масштабных вычислительных экспериментов в проекте.
Примерно за 20 часов счета в 3 потока завершено предварительное формирование спектров 2-трансверсалей отталкиваясь от ОДЛК порядка 12 имеющейся у нас в распоряжении коллекции. В каждом из них обработано примерно 1500 ОДЛК (где-то чуть меньше, где-то чуть больше, мизерная часть коллекции), результаты ниже.
Спектр диагональных 2-трансверсалей от интересных ОДЛК: {0, 1, 2, 3, 4, 6, 8}, 7 элементов в спектре (столько же было и в ОДЛК общего вида)
Спектр 2-трансверсалей от ОДЛК общего вида: {2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 26, 28, 30, 32, 34, 36, 38, 40, 44, 48}, 33 элемента в спектре
Спектр 2-трансверсалей от интересных ОДЛК: {2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 26, 28, 30, 32, 34, 36, 38, 40, 41, 42, 43, 44, 46, 48, 52, 56, 62}, 40 элементов в спектре
Объединяя все полученные ранее спектры, получаем:
Спектр диагональных 2-трансверсалей: {0, 1, 2, 3, 4, 6, 8, 32, 34, 36, 38}, 11 элементов
Спектр 2-трансверсалей: {2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 26, 28, 30, 32, 34, 36, 38, 40, 41, 42, 43, 44, 46, 48, 52, 56, 62, 72, 108}, 42 элемента
В дальнейшем мощность данных спектров можно попытаться расширить в ходе более масштабных вычислительных экспериментов в проекте.
Цитата: AenBleidd от 18.03.2023, 00:49Это Вы немного веткой ошиблись, Вам бы это зарепортить сюдой: https://boinc.ru/forum/topic/numberfieldshome/
Это Вы немного веткой ошиблись, Вам бы это зарепортить сюдой: https://boinc.ru/forum/topic/numberfieldshome/