Стандартный алгоритм решения линейного диофантова уравнения

BoBochka

Подскажите, пожалуйста, какой-нибудь стандартный (и эффективный) алгоритм решения линейного диофантова уравнения c произвольным числом неизвестных, чтобы его можно было как можно быстрее запрограммировать, а еще лучше — уже реализованный алгоритм в какой-нибудь открытой библиотечке на C++ или Java. :)
К моему удивлению, трудно найти в инете материалы по решению этой казалось бы тривиальной задачи. :ooo:
P.S. Было бы хорошо, если бы алгоритм легко расширялся на случай системы линейных диофантовых уравнений.

BoBochka

Случайно нашел вроде бы неплохой материал по теме треда:
"О решении уравнений в целых числах" (В. Серпинский, 1961) , глава 2 :)

lenmas

У вас не читали что ли теории чисел? Там на первом же семинаре решают линейные системы. Все сводится к китайской теореме об остатках.

BoBochka

Все сводится к китайской теореме об остатках
Как решение линейного диофантова уравнения с произвольным числом неизвестных сводится к этой теореме ? :ooo: :ooo:

lenmas

Как решение линейного диофантова уравнения с произвольным числом неизвестных сводится к этой теореме ? :ooo: :ooo:
Я про систему. Ты же спрашивал и про систему тоже.

lenmas

Случайно нашел вроде бы неплохой материал по теме треда:
"О решении уравнений в целых числах" (В. Серпинский, 1961) , глава 2 :)
Кстати, да, хорошая книжка. В детстве увлекался ею :D

lenmas

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

BoBochka

А тебе, кстати, нужно общее решение или одно какое-то частное?
На самом деле мне нужны все неотрицательные решения. Но, к сожалению, в книге Серпинского я не нашел как выписать ВСЕ решения :(
Грубо говоря, мне нужно получить удобное представление множества ВСЕХ целых точек, лежащих на данной гиперплоскости. А так целью является максимально эффективный перебор всех целых точек, лежащих внутри симплекса, который высекается положительным квадрантом на этой гиперплоскости.

lenmas

Тогда тебе надо почитать статью http://eprints.isofts.kiev.ua/257/1/D32.DOC
Там целая когорта занимающихся этой проблемой в Киеве, судя по ссылкам.

lenmas

Но, к сожалению, в книге Серпинского я не нашел как выписать ВСЕ решения :(
Вроде у Серпинского в рассуждениях нигде решения не теряются, должны быть все решения :confused:

BoBochka

Потому что в инете пишут, что там какой-то базис существует для общего решения.
Не могли бы Вы дать ссылку ? Хотелось бы понять, о каком базисе идет речь, базис решетки, свободной абелевой группы ...
Вроде у Серпинского в рассуждениях нигде решения не теряются

Но они у Серпинского не выписаны в явном виде.

lenmas

Да нет, базис обыкновенный в пространстве N^q
Вот еще труд, я так понимаю, основоположника этого направления http://www.foibg.com/ibs_isc/ibs-07/IBS-07-p26.pdf
У него там много ссылок, пролопать.

lenmas

Но они у Серпинского не выписаны в явном виде.
А запоминать выражения старых переменных через нововводимые нельзя на каждом шаге?
Я тебе советовал бы самому проделать, может это и полезнее, и лучше для тебя было бы,
чем готовые алгоритмы глотать.

BoBochka

Вот еще труд
Да, пока искал в инете этот труд мне только и попадался, но там, как я понимаю, речь идет о другой задаче (кольцо вычетов Z_m и т.п.). :(

lenmas

Да, пока искал в инете этот труд мне только и попадался, но там, как я понимаю, речь идет о другой задаче (кольцо вычетов Z_m и т.п.). :(
Не, там в начале статьи про натуральные числа. Кстати, посмотри еще другие статьи по гуглу, там вроде все равно
вычеты сводятся к обычным диофантовым уравнениям. Но это я так, мельком видел, лучше сам проверь. Да и
хорошо бы учебник какой нормальный по этой тематике найти в ссылках этих мужиков.
P.S. Эти заразы пишут, что известно, что такой базис существует, но не приводят ссылки на доказательство этого ;)

lenmas

Вот здесь есть ссылка на базис Гильберта http://www.google.ru/url?sa=t&source=web&cd=3&ve...

assasin

Книга Ю.В. Нестеренко «Теория чисел», конец первой главы (только там есть небольшая ошибка, по-моему, так что читай внимательно).

BoBochka

Книга Ю.В. Нестеренко «Теория чисел»
Это как раз то, что я искал! Огромное спасибо и Вам и Юрию Валентиновичу за эту замечательную книгу! :)
На самом деле, промучившись несколько часов, я сам старался переписать то, что написано в книге Серпинского, в терминах матриц. А в книге Нестеренко это все уже есть!
Оставить комментарий
Имя или ник:
Комментарий: