Здравствуй, Хабрадруг.
Предлагаю принять участие в конкурсе по решению целочисленных СЛУ на скорость. Сразу хочу предупредить, что конкурс любительский и призов не предвидится, поэтому приглашают тех, кому такое соревнование покажется интересным и тем, у кого есть для этого свободное время. Конкурс может оказаться полезным с той точки зрения, что мало кто умеет решать такого рода задачи достаточно эффективно.
Я продолжаю проводить любительские конкурсы по спортивному программированию. Прошлый конкурс многим понравился и я даже обещал, что следующий будет по параллельным вычислениям, однако по техническим причинам такой конкурс я вынужден отодвинуть на неопределённый срок.
Год назад я предлагал задачу по перемножению матриц на скорость. Результаты получились достаточно интересными: мы добились более чем 100-кратного ускорения. Теперь предлагается другая задача линейной алгебры — решение целочисленной системы линейных уравнений Ax=b.
Матрица A и вектор b состоят из целых чисел, умещающихся в 32 бита со знаком (от -231 до 231-1). Ответом к этой задаче будет рациональный вектор x. Поскольку числитель и знаменатель ответа могут быть очень длинными, не запрещается использовать библиотеки с длинной арифметикой.
Максимальная размерность системы предлагается n=200. Но если кто-то из участников напишет слишком быструю программу, данное ограничение будет увеличено. Дело в том, что обычный метод Гаусса в целых числах, написанный «в лоб», при таких ограничениях на случайной матрице работает около 10 минут. Разумеется, что можно написать и быстрее.
Кого заинтересовало, прошу ознакомиться с подробностями конкурса.
К сожалению, я продолжаю проводить конкурсы в одиночку, поэтому возникают серьезные ограничения для участников. У меня есть возможность тестировать программы только под Windows 7 (32 бита), поэтому можно либо присылать EXE файлы, либо CPP исходники, которые будут компилироваться на рабочей машине (в этом случае доступна только библиотека MPIR). У меня нет других способов проводить конкурс. Впрочем, похожее ограничение для конкурса по перемножению матриц участников не остановило.
Хорошим итогом конкурса я вижу реализацию, укладывающуюся в 5-10 секунд.
В процессе поиска информации о точном решении целочисленных систем я обнаружил, что мало кто умеет решать такую задачу. Сам я не являюсь специалистом в этой области, но в своих исследованиях столкнулся с целочисленными СЛУ, решать которые нужно очень быстро. Данный конкурс может помочь понять, каких успехов можно достичь в скорости решения целочисленных систем и чего вообще мы можем ожидать в таком случае. Победитель конкурса мог бы поделиться опытом, написав отдельную статью, которая будет очень полезной для людей, работающих в сфере вычислительной линейной алгебры. В Рунете найти подобного рода статьи не удалось, поэтому и предлагается заполнить данный пробел.
Если окажется (после завершения конкурса), что мои методы быстрее, чем методы участников, то я такую статью напишу сам. До завершения конкурса, я в него не вмешиваюсь.
Разумеется, я не ищу для себя чисто личной выгоды и не собираюсь воровать чужой код и использовать его в своих целях. Я уже не первый раз провожу конкурс и вроде бы пока никто не жаловался. Поэтому комплексующие по этому поводу могут не комплексовать: )
Удачи!
Предлагаю принять участие в конкурсе по решению целочисленных СЛУ на скорость. Сразу хочу предупредить, что конкурс любительский и призов не предвидится, поэтому приглашают тех, кому такое соревнование покажется интересным и тем, у кого есть для этого свободное время. Конкурс может оказаться полезным с той точки зрения, что мало кто умеет решать такого рода задачи достаточно эффективно.
Я продолжаю проводить любительские конкурсы по спортивному программированию. Прошлый конкурс многим понравился и я даже обещал, что следующий будет по параллельным вычислениям, однако по техническим причинам такой конкурс я вынужден отодвинуть на неопределённый срок.
Год назад я предлагал задачу по перемножению матриц на скорость. Результаты получились достаточно интересными: мы добились более чем 100-кратного ускорения. Теперь предлагается другая задача линейной алгебры — решение целочисленной системы линейных уравнений Ax=b.
Матрица A и вектор b состоят из целых чисел, умещающихся в 32 бита со знаком (от -231 до 231-1). Ответом к этой задаче будет рациональный вектор x. Поскольку числитель и знаменатель ответа могут быть очень длинными, не запрещается использовать библиотеки с длинной арифметикой.
Максимальная размерность системы предлагается n=200. Но если кто-то из участников напишет слишком быструю программу, данное ограничение будет увеличено. Дело в том, что обычный метод Гаусса в целых числах, написанный «в лоб», при таких ограничениях на случайной матрице работает около 10 минут. Разумеется, что можно написать и быстрее.
Кого заинтересовало, прошу ознакомиться с подробностями конкурса.
К сожалению, я продолжаю проводить конкурсы в одиночку, поэтому возникают серьезные ограничения для участников. У меня есть возможность тестировать программы только под Windows 7 (32 бита), поэтому можно либо присылать EXE файлы, либо CPP исходники, которые будут компилироваться на рабочей машине (в этом случае доступна только библиотека MPIR). У меня нет других способов проводить конкурс. Впрочем, похожее ограничение для конкурса по перемножению матриц участников не остановило.
Хорошим итогом конкурса я вижу реализацию, укладывающуюся в 5-10 секунд.
Зачем это нужно?
В процессе поиска информации о точном решении целочисленных систем я обнаружил, что мало кто умеет решать такую задачу. Сам я не являюсь специалистом в этой области, но в своих исследованиях столкнулся с целочисленными СЛУ, решать которые нужно очень быстро. Данный конкурс может помочь понять, каких успехов можно достичь в скорости решения целочисленных систем и чего вообще мы можем ожидать в таком случае. Победитель конкурса мог бы поделиться опытом, написав отдельную статью, которая будет очень полезной для людей, работающих в сфере вычислительной линейной алгебры. В Рунете найти подобного рода статьи не удалось, поэтому и предлагается заполнить данный пробел.
Если окажется (после завершения конкурса), что мои методы быстрее, чем методы участников, то я такую статью напишу сам. До завершения конкурса, я в него не вмешиваюсь.
Разумеется, я не ищу для себя чисто личной выгоды и не собираюсь воровать чужой код и использовать его в своих целях. Я уже не первый раз провожу конкурс и вроде бы пока никто не жаловался. Поэтому комплексующие по этому поводу могут не комплексовать: )
Удачи!
