Матричный алгоритм решения целочисленной системы уравнений

[Tuzembobel]

Добрый день. Хотелось бы узнать про матричный алгоритм, который дает весьма простой способ решения целочисленной системы уравнений:

$$ \begin{cases} a_{11}x_1+\ldots + a_{1m}x_m & = b_1 \\ \ldots & \\ a_{m1}x_1+\ldots + a_{mm}x_m & = b_m \end{cases} $$

где все коэффициенты - целые числа.
Был бы весьма признателен за ответ!

[venja]

Tuzembobel писал(а):

Добрый день. Хотелось бы узнать про матричный алгоритм, который дает весьма простой способ решения целочисленной системы уравнений:

$$ \begin{cases} a_{11}x_1+\ldots + a_{1m}x_m & = b_1 \\ \ldots & \\ a_{m1}x_1+\ldots + a_{mm}x_m & = b_m \end{cases} $$

где все коэффициенты - целые числа.
Был бы весьма признателен за ответ!

Я не думаю, что существует упрощенный алгоритм, использующий целочисленность коэффициентов. Поэтому, думаю, это обычный матричный метод, основанный на формуле
$ X=A^{-1}\cdot B $

[PAV]

Ну или можно использовать формулу через отношение определителей (если $m$ не слишком велико). Определители будут целыми числами. Используя целочисленность коэффициентов, можно также без погрешностей исключать неизвестные последовательно, но это уже не матричный метод.

[Someone]

Простейшее, что можно предложить - выписываете расширенную матрицу системы и целочисленными преобразованиями строк приводите её к ступенчатому виду. Своего рода, целочисленный вариант метода Гаусса. Наверняка это где-нибудь есть.

[Zai]

Tuzembobel писал(а):

способ решения целочисленной системы уравнений

Вполне возможно, что этот алгоритм даже не матричный может быть востребован на практике. Скажем в алгоритмах видеокарт встречается обращение матриц. Требования к коэффициентам там не такие жесткие.

Существенное преимущество - отсутствие операций с плавающей точкой - заметное ускорение (можно при гауссовом прямом и обратном проходе использовать только операцию умножения). Правда число решаемых уравнений относительно невелико, так как мантисса целых чисел ограничена. Здесь может быть интересен алгоритм поиска общих делителей, который будет уменьшать множители.
Алгоритм также может быть интересен и при точных вычислениях, когда необходима полная уверенность в отсутствии округлений.

[Mixser]

Решение целочисленных систем линейных алгебраических уравнений с диагональным преобладанием можно найти по этой ссылке: Алгоритм Сергеева

[iig]

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

[Ninja]

есть несложные методы решения: обратной матрицы, метод Крамера и Гаусса

[Ales]

С точки зрения компьютера все числа целые. Поэтому нет никакого такого особого алгоритма.

[Утундрий]

Если чтоб поменьше делений было, так можно через первые $n-1$ степеней матрицы обратную выразить. Умножение да сложение сплошное, ну а в конце - на определитель поделить один раз.

[Zealint]

Если тема еще актуальна.

Существует быстрый алгоритм решения целочисленной системы, описанный в статье

Dixon J. D. Exact solution of linear equations using P-adic expansions.
Журнал Numer. Math., 40, 1982 г. с 137-141.

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

[Zealint]

Zealint в сообщении #397098 писал(а):

Существует быстрый алгоритм решения целочисленной системы, описанный в статье

Dixon J. D. Exact solution of linear equations using P-adic expansions.
Журнал Numer. Math., 40, 1982 г. с 137-141.

Популярное описание этого метода с примером можно прочитать здесь.