Исследование свойств диагональных латинских квадратов в проектах добровольных распределенных вычислений и не только...
Цитата: SerVal от 13.06.2021, 07:45С этим мы и в Герасиме справимся.
Тем не менее, рабочая база Герасима - это не самое подходящее место для хранения миллионов ВУшек.
Например, ВУшки приложения test_separator так и кочуют из бэкапа в бэкап в неизменном состоянии и производительность проекта явно не повышают. Желательно их досчитать, и задания для test_separator просто не добавлять, чтобы не замедлять приём и выдачу заданий для других приложений.
С этим мы и в Герасиме справимся.
Тем не менее, рабочая база Герасима - это не самое подходящее место для хранения миллионов ВУшек.
Например, ВУшки приложения test_separator так и кочуют из бэкапа в бэкап в неизменном состоянии и производительность проекта явно не повышают. Желательно их досчитать, и задания для test_separator просто не добавлять, чтобы не замедлять приём и выдачу заданий для других приложений.
Цитата: evatutin от 13.06.2021, 16:18В описание числовых рядов в OEIS, связанных с числовыми характеристиками ДЛК, добавлены подтверждающие списки. Например, для минимального числа трансверсалей в ДЛК (ряд https://oeis.org/A287645) подтверждающий список (http://evatutin.narod.ru/A287645_proving_list.txt) выглядит следующим образом (привожу фрагмент):
...n=5, a(5)=3
Article: E. I. Vatutin, S. E. Kochemazov, O. S. Zaikin, S. Yu. Valyaev, Enumerating the Transversals for Diagonal Latin Squares of Small Order. CEUR Workshop Proceedings. Proceedings of the Third International Conference BOINC-based High Performance Computing: Fundamental Research and Development (BOINC:FAST 2017). Vol. 1973. Technical University of Aachen, Germany, 2017. pp. 6-14. urn:nbn:de:0074-1973-0. http://ceur-ws.org/Vol-1973/paper01.pdf
Way of finding: brute force
0 1 2 3 4
4 2 0 1 3
1 4 3 2 0
3 0 1 4 2
2 3 4 0 1n=6, a(6)=32
Article: E. I. Vatutin, S. E. Kochemazov, O. S. Zaikin, S. Yu. Valyaev, Enumerating the Transversals for Diagonal Latin Squares of Small Order. CEUR Workshop Proceedings. Proceedings of the Third International Conference BOINC-based High Performance Computing: Fundamental Research and Development (BOINC:FAST 2017). Vol. 1973. Technical University of Aachen, Germany, 2017. pp. 6-14. urn:nbn:de:0074-1973-0. http://ceur-ws.org/Vol-1973/paper01.pdf
Way of finding: brute force
0 1 2 3 4 5
4 2 5 0 3 1
3 5 1 2 0 4
5 3 0 4 1 2
2 4 3 1 5 0
1 0 4 5 2 3...В нем указан один из ДЛК, имеющий рекордно малое число трансверсалей для выбранной размерности n, кем, когда и где он был найден с указанием дат и ссылок на соответствующий анонс и научную статью, если она на данный момент написана и опубликована, и метода нахождения.Подтверждающие списки добавлены в следующие числовые ряды:* https://oeis.org/A287645
* https://oeis.org/A287644
* https://oeis.org/A287647
* https://oeis.org/A287648
* https://oeis.org/A287695
* https://oeis.org/A299783
* https://oeis.org/A299784
* https://oeis.org/A299785
* https://oeis.org/A299787
* https://oeis.org/A307163
* https://oeis.org/A307164
* https://oeis.org/A307166
* https://oeis.org/A307167
* https://oeis.org/A307170
* https://oeis.org/A307171
* https://oeis.org/A307839
* https://oeis.org/A307840
* https://oeis.org/A307841
* https://oeis.org/A307842
* https://oeis.org/A328873
* https://oeis.org/A341585
* https://oeis.org/A342998
* https://oeis.org/A342997На эту работу ушло несколько месяцев с учетом того, что правки в OEIS подтверждаются далеко не сразу. Я искренне рад, что идея в целом редакторам OEIS понравилась и была принята.PS. Если я что-то где-то упустил или указал неверно, прошу дать мне об этом знать
В описание числовых рядов в OEIS, связанных с числовыми характеристиками ДЛК, добавлены подтверждающие списки. Например, для минимального числа трансверсалей в ДЛК (ряд https://oeis.org/A287645) подтверждающий список (http://evatutin.narod.ru/A287645_proving_list.txt) выглядит следующим образом (привожу фрагмент):
Article: E. I. Vatutin, S. E. Kochemazov, O. S. Zaikin, S. Yu. Valyaev, Enumerating the Transversals for Diagonal Latin Squares of Small Order. CEUR Workshop Proceedings. Proceedings of the Third International Conference BOINC-based High Performance Computing: Fundamental Research and Development (BOINC:FAST 2017). Vol. 1973. Technical University of Aachen, Germany, 2017. pp. 6-14. urn:nbn:de:0074-1973-0. http://ceur-ws.org/Vol-1973/paper01.pdf
Way of finding: brute force
0 1 2 3 4
4 2 0 1 3
1 4 3 2 0
3 0 1 4 2
2 3 4 0 1
n=6, a(6)=32
Article: E. I. Vatutin, S. E. Kochemazov, O. S. Zaikin, S. Yu. Valyaev, Enumerating the Transversals for Diagonal Latin Squares of Small Order. CEUR Workshop Proceedings. Proceedings of the Third International Conference BOINC-based High Performance Computing: Fundamental Research and Development (BOINC:FAST 2017). Vol. 1973. Technical University of Aachen, Germany, 2017. pp. 6-14. urn:nbn:de:0074-1973-0. http://ceur-ws.org/Vol-1973/paper01.pdf
Way of finding: brute force
0 1 2 3 4 5
4 2 5 0 3 1
3 5 1 2 0 4
5 3 0 4 1 2
2 4 3 1 5 0
1 0 4 5 2 3
* https://oeis.org/A287644
* https://oeis.org/A287647
* https://oeis.org/A287648
* https://oeis.org/A287695
* https://oeis.org/A299783
* https://oeis.org/A299784
* https://oeis.org/A299785
* https://oeis.org/A299787
* https://oeis.org/A307163
* https://oeis.org/A307164
* https://oeis.org/A307166
* https://oeis.org/A307167
* https://oeis.org/A307170
* https://oeis.org/A307171
* https://oeis.org/A307839
* https://oeis.org/A307840
* https://oeis.org/A307841
* https://oeis.org/A307842
* https://oeis.org/A328873
* https://oeis.org/A341585
* https://oeis.org/A342998
* https://oeis.org/A342997
Цитата: evatutin от 13.06.2021, 16:22Тем не менее, рабочая база Герасима - это не самое подходящее место для хранения миллионов ВУшек.
Согласен
Например, ВУшки приложения test_separator так и кочуют из бэкапа в бэкап в неизменном состоянии и производительность проекта явно не повышают. Желательно их досчитать, и задания для test_separator просто не добавлять, чтобы не замедлять приём и выдачу заданий для других приложений.
Этот подпроект был приостановлен для того, чтобы быстрее досчитался подпроект Graph Coloring по подсчету ОДЛК для ДЛК порядка 12. Этот процесс и так растянулся...
Как часто делается backup? И в какое время? У меня есть подозрение, что по утрам, т.к. иногда в это время процесс добавления WU'шек и слива результатов идет очень медленно...
Тем не менее, рабочая база Герасима - это не самое подходящее место для хранения миллионов ВУшек.
Согласен
Например, ВУшки приложения test_separator так и кочуют из бэкапа в бэкап в неизменном состоянии и производительность проекта явно не повышают. Желательно их досчитать, и задания для test_separator просто не добавлять, чтобы не замедлять приём и выдачу заданий для других приложений.
Этот подпроект был приостановлен для того, чтобы быстрее досчитался подпроект Graph Coloring по подсчету ОДЛК для ДЛК порядка 12. Этот процесс и так растянулся...
Как часто делается backup? И в какое время? У меня есть подозрение, что по утрам, т.к. иногда в это время процесс добавления WU'шек и слива результатов идет очень медленно...
Цитата: SerVal от 14.06.2021, 10:02Как часто делается backup? И в какое время?
Бэкап делаю вручную утром с 8 до 9 утра. Потом копирую его на саташный диск.
процесс добавления WU'шек и слива результатов идет очень медленно...
Так и должно быть. А если закатать в рабочую базу 10 миллионов ВУшек для любого приложения и не считать их, то Герасим и задания будет выдавать по одной штуке в час во всех приложениях(таблица ВУшек и результатов для всех приложений одна).
- бэкап научной базы длится 10-15 минут. Рабочей базы - 20-25 минут.
Как часто делается backup? И в какое время?
Бэкап делаю вручную утром с 8 до 9 утра. Потом копирую его на саташный диск.
процесс добавления WU'шек и слива результатов идет очень медленно...
Так и должно быть. А если закатать в рабочую базу 10 миллионов ВУшек для любого приложения и не считать их, то Герасим и задания будет выдавать по одной штуке в час во всех приложениях(таблица ВУшек и результатов для всех приложений одна).
- бэкап научной базы длится 10-15 минут. Рабочей базы - 20-25 минут.
Цитата: evatutin от 14.06.2021, 10:59Тогда делаем по другому: для поиска по линейкам (подпроект test_separator) досчитываем текущую партию WU'шек (400 тыс.) и ждем, новых не добавляю; аналогично поступаем с быстровычислимыми числовыми характеристиками для N=12 (подпроект ODLS BS), там завершается эксперимент, осталось 200 тыс. WU'шек, новых тоже пока добавлять не буду, размерность N=13 немного подождет; разведка окрестностей обобщенных симметрий в парастрофических срезах (подпроект spstarter) имеет короткие WU'шки, которые не мешают счету ОДЛК для ДЛК порядка 12 в подпроекте Graph Coloring, буду добавлять партиями, как и раньше; ну и собственно ОДЛК к интересному ДЛК порядка 12 — WU'шек там еще много впереди, добавлять буду дозировано, не все сразу. Тут дело в том, что добавление WU'шек занимает достаточно много времени и за процессом надо следить, т.к. он иногда прерывается и не все WU'шки архива добавляются, на это нужно время, а оно у меня есть не всегда, семестр заканчивается, хвосты, экзамены, защиты, комиссии, бумажки... Забор результатов стараюсь делать ежедневно, иногда с перерывами по тем же причинам
Тогда делаем по другому: для поиска по линейкам (подпроект test_separator) досчитываем текущую партию WU'шек (400 тыс.) и ждем, новых не добавляю; аналогично поступаем с быстровычислимыми числовыми характеристиками для N=12 (подпроект ODLS BS), там завершается эксперимент, осталось 200 тыс. WU'шек, новых тоже пока добавлять не буду, размерность N=13 немного подождет; разведка окрестностей обобщенных симметрий в парастрофических срезах (подпроект spstarter) имеет короткие WU'шки, которые не мешают счету ОДЛК для ДЛК порядка 12 в подпроекте Graph Coloring, буду добавлять партиями, как и раньше; ну и собственно ОДЛК к интересному ДЛК порядка 12 — WU'шек там еще много впереди, добавлять буду дозировано, не все сразу. Тут дело в том, что добавление WU'шек занимает достаточно много времени и за процессом надо следить, т.к. он иногда прерывается и не все WU'шки архива добавляются, на это нужно время, а оно у меня есть не всегда, семестр заканчивается, хвосты, экзамены, защиты, комиссии, бумажки... Забор результатов стараюсь делать ежедневно, иногда с перерывами по тем же причинам
Цитата: evatutin от 15.06.2021, 00:36Спектры числовых характеристик ДЛК
Возьмем множество всех ДЛК заданного порядка N и проделаем с ним следующую нехитрую операцию: для каждого ДЛК L[i] рассчитаем значение выбранной числовой характеристики x(L[i]) и из полученных значений составим множество X = {x(L[1]), x(L[2]), ..., x(L[M])}, которое называется спектром. Далее найдем мощности множеств |X| в зависимости от размерности решаемой задачи (размера квадрата) N и получим числовой ряд, который... Тут я думаю и ежу понятно, что с ним надо дальше сделать
Пример уже известного ряда: https://oeis.org/A309344 — число трансверсалей в ЛК (ряд свеженький, был добавлен в OEIS в июле 2019).
1. Для трансверсалей в ДЛК получается следующий числовой ряд: 1, 0, 0, 1, 2, 1, 32. Например, для N=7 спектр образован следующими значениями: {7, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 37, 41, 43, 45, 47, 55, 133} (несложно заметить, что он является подмножеством спектра в примере в ряду A309344, т.к. ДЛК — подмножество ЛК, соответственно a(i) <= A309344(i)).
2. Для диагональных трансверсалей в ДЛК: 1, 0, 0, 1, 2, 2, 14, для N=7 спектр представлен следующими значениями: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 27}.
3. Для интеркалятов в ДЛК: 0, 0, 0, 1, 2, 1, 21, для N=7 спектр представлен следующими значениями: {0, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 18, 20, 22, 26, 30}.
4. Для числа ОДЛК к одному ДЛК: 1, 0, 0, 1, 2, 1, 3, для N=7 спектр представлен следующими значениями: {0, 1, 3}. В качестве примера ниже приведен подтверждающий список:
0 ОДЛК
0 1 2 3 4 5 6
3 2 4 6 5 0 1
4 6 1 5 2 3 0
2 5 6 4 0 1 3
6 0 5 1 3 4 2
5 3 0 2 1 6 4
1 4 3 0 6 2 51 ОДЛК
0 1 2 3 4 5 6
4 2 0 6 3 1 5
5 6 1 2 0 3 4
1 3 5 4 6 2 0
6 4 3 1 5 0 2
3 5 4 0 2 6 1
2 0 6 5 1 4 33 ОДЛК
0 1 2 3 4 5 6
4 2 6 0 5 1 3
3 5 1 6 0 4 2
5 6 3 4 1 2 0
6 4 5 2 3 0 1
1 3 0 5 2 6 4
2 0 4 1 6 3 5Спектры в перспективе можно посчитать и для других числовых характеристик...
Приведенные выше спектры посчитаны полным перебором по всем ДЛК для размерностей N<8 за несколько секунд в 1 поток на Core i7 4770. Их вполне можно продлить на размерности N=8 и N=9 путем перехода к более сложному эксперименту с генерацией КФов и расчету спектров по ним (возможно, с использованием грид). Для бОльших размерностей спектры можно аппроксимировать и наложить нижние ограничения, для чего можно будет организовать серию дополнительных экспериментов в проекте...
Несложно заметить, что минимальное значение в множестве X для выбранной размерности N соответствует минимальному значению выбранной числовой характеристики, а максимальное — соответственно максимальному. Например, для числа трансверсалей в ДЛК порядка N=7 получаем, что inf(X) = 7 = A287645(7), sup(X) = 133 = A287644(7), где inf(X) и sup(X) соответственно инфимум и супремум для множества (не было у нас еще до этого таких умных слов :).
Некоторые участки спектров состоят из сплошных значений (для приведенного выше примера {..., 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, ...}), в других спектр является дискретным ({..., 37, 41, 43, 45, 47, 55, 133}). Из школьного курса физики известно, что дискретность спектров объясняется перескакиванием электронов между различными энергетическими уровнями в атомах, что может найти применение в дальнейших исследованиях...
Спектры числовых характеристик ДЛК
Возьмем множество всех ДЛК заданного порядка N и проделаем с ним следующую нехитрую операцию: для каждого ДЛК L[i] рассчитаем значение выбранной числовой характеристики x(L[i]) и из полученных значений составим множество X = {x(L[1]), x(L[2]), ..., x(L[M])}, которое называется спектром. Далее найдем мощности множеств |X| в зависимости от размерности решаемой задачи (размера квадрата) N и получим числовой ряд, который... Тут я думаю и ежу понятно, что с ним надо дальше сделать
Пример уже известного ряда: https://oeis.org/A309344 — число трансверсалей в ЛК (ряд свеженький, был добавлен в OEIS в июле 2019).
1. Для трансверсалей в ДЛК получается следующий числовой ряд: 1, 0, 0, 1, 2, 1, 32. Например, для N=7 спектр образован следующими значениями: {7, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 37, 41, 43, 45, 47, 55, 133} (несложно заметить, что он является подмножеством спектра в примере в ряду A309344, т.к. ДЛК — подмножество ЛК, соответственно a(i) <= A309344(i)).
2. Для диагональных трансверсалей в ДЛК: 1, 0, 0, 1, 2, 2, 14, для N=7 спектр представлен следующими значениями: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 27}.
3. Для интеркалятов в ДЛК: 0, 0, 0, 1, 2, 1, 21, для N=7 спектр представлен следующими значениями: {0, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 18, 20, 22, 26, 30}.
4. Для числа ОДЛК к одному ДЛК: 1, 0, 0, 1, 2, 1, 3, для N=7 спектр представлен следующими значениями: {0, 1, 3}. В качестве примера ниже приведен подтверждающий список:
0 ОДЛК
0 1 2 3 4 5 6
3 2 4 6 5 0 1
4 6 1 5 2 3 0
2 5 6 4 0 1 3
6 0 5 1 3 4 2
5 3 0 2 1 6 4
1 4 3 0 6 2 5
1 ОДЛК
0 1 2 3 4 5 6
4 2 0 6 3 1 5
5 6 1 2 0 3 4
1 3 5 4 6 2 0
6 4 3 1 5 0 2
3 5 4 0 2 6 1
2 0 6 5 1 4 3
3 ОДЛК
0 1 2 3 4 5 6
4 2 6 0 5 1 3
3 5 1 6 0 4 2
5 6 3 4 1 2 0
6 4 5 2 3 0 1
1 3 0 5 2 6 4
2 0 4 1 6 3 5
Спектры в перспективе можно посчитать и для других числовых характеристик...
Приведенные выше спектры посчитаны полным перебором по всем ДЛК для размерностей N<8 за несколько секунд в 1 поток на Core i7 4770. Их вполне можно продлить на размерности N=8 и N=9 путем перехода к более сложному эксперименту с генерацией КФов и расчету спектров по ним (возможно, с использованием грид). Для бОльших размерностей спектры можно аппроксимировать и наложить нижние ограничения, для чего можно будет организовать серию дополнительных экспериментов в проекте...
Несложно заметить, что минимальное значение в множестве X для выбранной размерности N соответствует минимальному значению выбранной числовой характеристики, а максимальное — соответственно максимальному. Например, для числа трансверсалей в ДЛК порядка N=7 получаем, что inf(X) = 7 = A287645(7), sup(X) = 133 = A287644(7), где inf(X) и sup(X) соответственно инфимум и супремум для множества (не было у нас еще до этого таких умных слов :).
Некоторые участки спектров состоят из сплошных значений (для приведенного выше примера {..., 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, ...}), в других спектр является дискретным ({..., 37, 41, 43, 45, 47, 55, 133}). Из школьного курса физики известно, что дискретность спектров объясняется перескакиванием электронов между различными энергетическими уровнями в атомах, что может найти применение в дальнейших исследованиях...
Цитата: kotenok2000 от 16.06.2021, 15:25После дня вычислений graph coloring программы перестают открываться с ошибкой 0x0000142.
эффект проявляется на windows 10 и свежеустановленной и обновлённой на vmware windows server 2019.
После дня вычислений graph coloring программы перестают открываться с ошибкой 0x0000142.
эффект проявляется на windows 10 и свежеустановленной и обновлённой на vmware windows server 2019.
Цитата: SerVal от 16.06.2021, 17:14Цитата: kotenok2000 от 16.06.2021, 15:25После дня вычислений graph coloring программы перестают открываться с ошибкой 0x0000142.
эффект проявляется на windows 10 и свежеустановленной и обновлённой на vmware windows server 2019.
У меня тоже вылезает эта ошибка. Сам Боинк менеджер работает, и задания считаются(принимаются и возвращаются). Одни программы можно запустить, другие - нет. Браузеры Хроме и ИЕ - просто перестают запускаться, не выдавая никакой ошибки. У Герасима - такая же хрень. На рабочей машинке - тоже. В общем - ХЗЧ какое-то.
Правда, я не уверен, что ошибка как-то связана с graph coloring.
/// если выйти из системы и войти обратно, ошибка исчезает: иногда на час, иногда на день.
p.s.
kotenok2000, а где Вы брали драйверы чипсета для Windows Server 2019 ? У меня с диска драйверы не устанавливаются - ругаются, что они не для этой операционной системы. От этого и в Device Manager-е какая-то хрень. - все PCI-device с восклицательными знаками.
Цитата: kotenok2000 от 16.06.2021, 15:25После дня вычислений graph coloring программы перестают открываться с ошибкой 0x0000142.
эффект проявляется на windows 10 и свежеустановленной и обновлённой на vmware windows server 2019.
У меня тоже вылезает эта ошибка. Сам Боинк менеджер работает, и задания считаются(принимаются и возвращаются). Одни программы можно запустить, другие - нет. Браузеры Хроме и ИЕ - просто перестают запускаться, не выдавая никакой ошибки. У Герасима - такая же хрень. На рабочей машинке - тоже. В общем - ХЗЧ какое-то.
Правда, я не уверен, что ошибка как-то связана с graph coloring.
/// если выйти из системы и войти обратно, ошибка исчезает: иногда на час, иногда на день.
p.s.
kotenok2000, а где Вы брали драйверы чипсета для Windows Server 2019 ? У меня с диска драйверы не устанавливаются - ругаются, что они не для этой операционной системы. От этого и в Device Manager-е какая-то хрень. - все PCI-device с восклицательными знаками.
Цитата: Yura12 от 16.06.2021, 17:38
И у меня такая же ситуация. Я наблюдаю её уже больше года. На компьютере с Windows Server 2012 и на компьютере с Windows 7 Professional после дней пяти непрерывной работы BOINC
Ошибка не связана с Graph Coloring - ошибка давняя.
И у меня такая же ситуация. Я наблюдаю её уже больше года. На компьютере с Windows Server 2012 и на компьютере с Windows 7 Professional после дней пяти непрерывной работы BOINC
Ошибка не связана с Graph Coloring - ошибка давняя.
Цитата: PinkFloyd от 17.06.2021, 13:36Во как. У меня тоже есть этот глюк. Когда начался не помню.
При том на рабочей машинке (FX-8350) всё нормально, а на домашней (3900X) стабильно вылазит раз в несколько дней беспрерывной работы. На обеих машинах одинаковый Windows 10 Pro. Я думал у меня на домашнем компе система глючит, собрался переустанавливать. Ну или железо колупать.
Во как. У меня тоже есть этот глюк. Когда начался не помню.
При том на рабочей машинке (FX-8350) всё нормально, а на домашней (3900X) стабильно вылазит раз в несколько дней беспрерывной работы. На обеих машинах одинаковый Windows 10 Pro. Я думал у меня на домашнем компе система глючит, собрался переустанавливать. Ну или железо колупать.