Конкурс для программистов - решение целочисленной СЛУ

[Zealint]

Предлагаю принять участие в очередном конкурсе для программистов.

Предлагается написать программу, решающую целочисленную систему линейных уравнений

$$ Ax=b. $$

Матрица системы и вектор правой части - целочисленные. Числа в них умещаются в 32 бита со знаком (от $-2^{31}$ до $2^{31}-1$). Ответом будет вектор рациональных чисел $x$. Числа в ответе могут получиться очень длинными, поэтому НЕ запрещается использовать библиотеки длинной арифметики (GMP, MPIR).

Предлагается ограничиться системами порядка $n=200$, но если участник предложат слишком быструю реализацию, можно увеличить это ограничение.

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

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

К сожалению, у меня нет возможности тестировать задачу НЕ в системе Windows 7, поэтому предлагается два варианта участия: можно присылать либо EXE файлы, либо CPP, которые будут компилироваться на нашей рабочей машине. Понимаю, что не пишущих на CPP или не под Windows обижаю, но ничего не поделаешь. Конкурс любительский.

Модераторам: форум dxdy.ru указан в качестве информационного спонсора на странице конкурса.

[Zealint]

Конкурс завершился. Вот грустные итоги, а вот схема моего решения.

Было удивительно то, что я в советской / российской литературе никаких быстрых алгоритмов для точного решения целочисленных систем не нашёл. И на тех русскоязычных форумах, где я искал, нет никаких намёков на то, что задача может быть решена на порядки быстрее, чем методом Гаусса и его целочисленными аналогами.

Может я плохо искал? Или всё действительно так печально?

[Pavia]

Скорее всего плохо искали.
Есть замечательная книжка. Правда автор не русский. Но переведена.
Р. Блейхут Быстрые алгоритмы цифровой обработки сигналов.

Там есть ряд алгоритмов. А еще там много идей, но я их еще плохо воспринимаю.

А возможно что и нет. И вся хвалёная Российская наука отстала лет на 20.
Я специализируюсь на обработки сигналов. Есть хорошо известный алгоритм Гаусовского размытия. Так вот вопрос в быстрой реализации. Везде описан через КИХ. Но это медленный алгоритм гораздо быстрее работает через БИХ. Но негде толкового описания на Русском не удалось. Оно отсутствовало. Когда как пришлось разбираться с английским текстами от 1994 года. Нашёл, реализовал. Проверил на простых вариантах всё работало. Спустя время руки дошли до того чтобы сделать 2D вариант. И выяснилось что в алгоритме ошибка. В результате сейчас полез разбираться. Нашел еще пару статей. А да алгоритм известен давно еще в 60-годах и ранее. А публикации американские 85,94,96 года. А русской ни одной.
Есть известный проект OpneCV так вот там до сих пор не реализован быстрый алгоритм. А да на первых порах его развивали Русский коллектив.

Есть ещё много алгоритмов о которых не написано в Русской литературе.

[Zealint]

Цитата:

Р. Блейхут Быстрые алгоритмы цифровой обработки сигналов.

Мне почему-то казалось, что я внимательно листал эту книгу. Но не могли бы вы указать её раздел, в котором есть что-то про быстрое решение целочисленной СЛАУ?

Кстати, в этой же книге есть забавные алгоритмы решения теплицевых систем. Они всего-то в несколько миллионов раз медленнее, чем алгоритмы решение обычной системы, которая не имеет специального вида. Представляете как здорово? Мне всегда казалось, что алгоритмы для задачи специального вида должны работать быстрее. Но нет...

[crab2]

Разве обязательно на Спп?
Можно на других ЯП писать? а то я с большими числами в си ни разу не сталкивался:)

[Zealint]

crab2 в сообщении #413157 писал(а):

Разве обязательно на Спп?
Можно на других ЯП писать? а то я с большими числами в си ни разу не сталкивался:)

Вы знаете, конкурс уже давно закончился.

[cepesh]

Тема перемещена из форума «Программирование» в форум «Олимпиадные задачи (CS)»
Причина переноса: не указана.