Pull to refresh

Конкурс на решение целочисленной системы линейных уравнений

Reading time2 min
Views2.6K
Здравствуй, Хабрадруг.

Предлагаю принять участие в конкурсе по решению целочисленных СЛУ на скорость. Сразу хочу предупредить, что конкурс любительский и призов не предвидится, поэтому приглашают тех, кому такое соревнование покажется интересным и тем, у кого есть для этого свободное время. Конкурс может оказаться полезным с той точки зрения, что мало кто умеет решать такого рода задачи достаточно эффективно.



Я продолжаю проводить любительские конкурсы по спортивному программированию. Прошлый конкурс многим понравился и я даже обещал, что следующий будет по параллельным вычислениям, однако по техническим причинам такой конкурс я вынужден отодвинуть на неопределённый срок.

Год назад я предлагал задачу по перемножению матриц на скорость. Результаты получились достаточно интересными: мы добились более чем 100-кратного ускорения. Теперь предлагается другая задача линейной алгебры — решение целочисленной системы линейных уравнений Ax=b.

Матрица A и вектор b состоят из целых чисел, умещающихся в 32 бита со знаком (от -231 до 231-1). Ответом к этой задаче будет рациональный вектор x. Поскольку числитель и знаменатель ответа могут быть очень длинными, не запрещается использовать библиотеки с длинной арифметикой.

Максимальная размерность системы предлагается n=200. Но если кто-то из участников напишет слишком быструю программу, данное ограничение будет увеличено. Дело в том, что обычный метод Гаусса в целых числах, написанный «в лоб», при таких ограничениях на случайной матрице работает около 10 минут. Разумеется, что можно написать и быстрее.

Кого заинтересовало, прошу ознакомиться с подробностями конкурса.

К сожалению, я продолжаю проводить конкурсы в одиночку, поэтому возникают серьезные ограничения для участников. У меня есть возможность тестировать программы только под Windows 7 (32 бита), поэтому можно либо присылать EXE файлы, либо CPP исходники, которые будут компилироваться на рабочей машине (в этом случае доступна только библиотека MPIR). У меня нет других способов проводить конкурс. Впрочем, похожее ограничение для конкурса по перемножению матриц участников не остановило.

Хорошим итогом конкурса я вижу реализацию, укладывающуюся в 5-10 секунд.

Зачем это нужно?



В процессе поиска информации о точном решении целочисленных систем я обнаружил, что мало кто умеет решать такую задачу. Сам я не являюсь специалистом в этой области, но в своих исследованиях столкнулся с целочисленными СЛУ, решать которые нужно очень быстро. Данный конкурс может помочь понять, каких успехов можно достичь в скорости решения целочисленных систем и чего вообще мы можем ожидать в таком случае. Победитель конкурса мог бы поделиться опытом, написав отдельную статью, которая будет очень полезной для людей, работающих в сфере вычислительной линейной алгебры. В Рунете найти подобного рода статьи не удалось, поэтому и предлагается заполнить данный пробел.

Если окажется (после завершения конкурса), что мои методы быстрее, чем методы участников, то я такую статью напишу сам. До завершения конкурса, я в него не вмешиваюсь.

Разумеется, я не ищу для себя чисто личной выгоды и не собираюсь воровать чужой код и использовать его в своих целях. Я уже не первый раз провожу конкурс и вроде бы пока никто не жаловался. Поэтому комплексующие по этому поводу могут не комплексовать: )

Удачи!
Tags:
Hubs:
Total votes 41: ↑37 and ↓4+33
Comments25

Articles