Решение системы полиномиальных уравнений

[AndrewSu]

Добрый день!
Я занимаюсь решением системы полиномиальных уравнений. Количество уравнений около $10^5-10^6$. Все уравнения имеют степень не выше 4, более того система сильно разреженна. На данный момент она решается итерационными методами, но это долго и более того стоит проблема хорошего начального приближения.
Недавно встретил описание метода Бухбергера, решения подобных систем. Но ни где не видел примеры решения задач подобного размера (все, что удалось найти - это системы с двумя десятками неизвестных). Очень интересны временные оценки для решения.
Если кто-то занимался подобными вопросами, не могли бы вы подсказать литературу/ссылки для ознакомления или библиотеки для пробы.

[Yuri Gendelman]

Вот краткое введение в теорию:
Аржанцев И. В. Базисы Грёбнера и системы алгебраических уравненийю 2003 (~400 КБ)

Меня самого заинтересовало такое применение базисов Гребнера. Первый пример, на который я наткнулся - это решение системы 2-х уравнений 3-го порядка:
$- 6x^2 + 6x - 6y^2 + 6y - 2 = 0$
$4x^3 - 6x^2 - 4y^3 + 6y^2 = 0$

Результат применения алгоритма - полином из базиса Гребнера, в котором исключена переменная $x$:
$3072y^8 - 6144y^7 + 8192y^6 - 15360y^5 + 19968y^4 - 11776y^3 + 5006.22y^2 - 2588.44y + 400.59$

Теперь осталось решить это уравнение 8-го(!) порядка, найти возможные значения $y$, подставить их в 1-е исходное уравнение и найти $x$.

После этого я попытался представить себе применение метода к системе из 100000 уравнений:
а) найти в базисе Гребнера полином невообразимого порядка, в котором исключены все неизвестные, кроме одной;
б) решить соотв. уравнение и найти огромное количество возможных значений оставшейся неизвестной;
в) найти в базисе Гребнера полином, в котором исключены все неизвестные, кроме уже найденой и еще одной;
г) решить соотв. уравнение и найти возможные значений второй неизвестной;
...
Повторить пары шагов "найти-решить" еще 99998 раз....

Боюсь, это очень неэффективный алгоритм.

Думаю, в Вашем случае итерационное решение - вполне разумный вариант.

[AndrewSu]

Спасибо за ответ, особенно за ссылку на книгу. Буду изучать

[Yuri Gendelman]

Дополнительная ссылка:
Bernd Sturmfels. Solving Systems of Polynomial Equations. 2002

И поправка:
Вместо

Цитата:

...
Повторить пары шагов "найти-решить" еще 99998 раз....

Должно быть

Цитата:

...
Повторить пары шагов "найти-решить" еще 99997 раз.
Найти последнее неизвестное, подставив все ранее найденные неизвестные в одно из исходных уравнений, в которое это последнее неизвестное входит.

[AndrewSu]

Yuri Gendelman в сообщении #682220 писал(а):

Дополнительная ссылка:
Bernd Sturmfels. Solving Systems of Polynomial Equations. 2002

Спасибо. Это будет полезно. Хотя, как вы и пишите, наверное не для этой задачи.

[Утундрий]

Подскажите, а вот если уравнения все однотипные: суммы мономов вида $x_i x_j$ ($i \ne j$), равные то ли нулю, то ли некоторой константе, то можно ли надеяться что-то такое нетривиальное руками выкрутить или проще применить грубую вычислительную силу?

[Yuri Gendelman]

Утундрий в сообщении #683156 писал(а):

... можно ли надеяться что-то такое нетривиальное руками выкрутить или проще применить грубую вычислительную силу?

Очень сомневаюсь (хотя и помню про "never say never").
Метод Бухбергера - это не численный, а символьный алгоритм. Реализован он в системах компьютетной алгебры (Maple, Mathematica, Singular и т.п.). Результат алгоритма - не решение системы, а новая система уравнений (минимальный базис Гребнера), более удобная для некоторых задач. Уровень сложности программной реализации - намного выше, чем обычно принятый в численном анализе.
Между прочим, метод Бухбергера для линейных систем сводится к методу Гаусса.

Для Вашего случая с $x_i x_j$ можно было бы попробовать перейти к (переопределенной) линейной системе с неизвестными $z_{i,j} \equiv x_i x_j$ и чего-нибудь из этого извлечь.

P.S. Тут у меня ошибка. Не переопределенной, т.к. число неизвестных увеличивается, а "недоопределенной".

[Утундрий]

Yuri Gendelman
Собственно, я пролистал Аржанцева, перед тем как задавать свой вопрос. Пролистал потому что прочитать, увы, экспириенции не хватило. Больно обсракно. Так вот и хотелось, чтобы знаючие люди или по- или отсоветовали - есть ли золото в Серых Горах и стоит ли туда так сказать углубляться.

[Yuri Gendelman]

Утундрий
Знающих людей где ж нам найти. Специалисты по алгебраической геометрии в Computer Science редко заглядывают.

Посмотрите у Аржанцева Определение 4.19 и Пример 4.22 на стр.32-33.
Что-то вроде продолжения - в Примере 4.30 на стр.34-35.

Все читать и понимать не обязательно. Просто считайте, что систему уравнений $\{f_1(x)=0, f_2()=0, ...\}$ можно рассматривать как идеал $I=(f_1, f_2, ...)$. А дальше - чисто механически.

Повторите пример, а потом попробуйте свою систему уравнений.

[vjung]

Утундрий, как насчет замены:
$ y_i = \log(x_i) $?
тогда уравнения превратяться в :
$ y_i + y_j = \log(c_{ij}) $
Для нулевых или отрицательных $c_{ij}$ -- разбивать на 2 случая.

[AndrewSu]

Yuri Gendelman в сообщении #682034 писал(а):

Теперь осталось решить это уравнение 8-го(!) порядка, найти возможные значения $y$, подставить их в 1-е исходное уравнение и найти $x$.

На сколько я понял, если, в полученном из моей системы, базисе Грёбнера будет $N$ членов, то мне придется решить $N$ алгебраических уравнений.
Для произвольной степени уравнения, мне на ум проходит только построение матрицы, для которой данное уравнение является характеристическим многочленом. Если степень велика, то получить решение не очень просто (с вычислительной точки зрения).
Отсюда вопрос: Как определить(оценить) степень уравнений в базисе Грёбнера, получаемом из моей системы?

[Yuri Gendelman]

vjung в сообщении #683679 писал(а):

Утундрий, как насчет замены:
$y_i = \log(x_i)$?
тогда уравнения превратяться в :
$y_i + y_j = \log(c_{ij})$

Это не подходит. Напомню, что Утундрий говорил про уравнения в виде сумм мономов вида $x_i x_j$ ($i \ne j$)
Пример такого уравнения:
$x_1 x_2 + 2 x_3 x_4 = 6$

-- Чт фев 14, 2013 11:09:07 --

AndrewSu в сообщении #683715 писал(а):

Для произвольной степени уравнения, мне на ум проходит только построение матрицы, для которой ...

Посмотрите программы в Библиотеке численного анализа НИВЦ МГУ:
Решение одного уравнения общего вида

AndrewSu в сообщении #683715 писал(а):

Отсюда вопрос: Как определить(оценить) степень уравнений в базисе Грёбнера, получаемом из моей системы?

Не понял вопроса. Как, глядя на уравнение из базиса Грёбнера, определить его степень?

[AndrewSu]

Yuri Gendelman в сообщении #683952 писал(а):

Не понял вопроса. Как, глядя на уравнение из базиса Грёбнера, определить его степень?

Я имел в виду - определить степень до построения базиса.

[Yuri Gendelman]

AndrewSu в сообщении #683980 писал(а):

Я имел в виду - определить степень до построения базиса.

Не знаю. И не уверен, что это проще, чем построить базис.

[AndrewSu]

Yuri Gendelman в сообщении #682034 писал(а):

Первый пример, на который я наткнулся - это решение системы 2-х уравнений 3-го порядка:
$- 6x^2 + 6x - 6y^2 + 6y - 2 = 0$
$4x^3 - 6x^2 - 4y^3 + 6y^2 = 0$

Результат применения алгоритма - полином из базиса Гребнера, в котором исключена переменная $x$:
$3072y^8 - 6144y^7 + 8192y^6 - 15360y^5 + 19968y^4 - 11776y^3 + 5006.22y^2 - 2588.44y + 400.59$

Я на выходных набросал программу, для построения базиса Грёбнера.
И увидел, что на этих данных результирующий базис зависит от порядка следования исходных полиномов.
У меня базис получился:
$- 24 x y ^ 2 + 24 x y - 20 x - 24 y ^ 3 + 48 y ^ 2 - 12 y + 4$
$+ 192 x y - 96 x + 288 y ^ 4 - 576 y ^ 3 + 384 y ^ 2 - 192 y + 40$
$+ 672 x - 1728 y ^ 5 + 4320 y ^ 4 - 2880 y ^ 3 - 240 y - 72 $
$+ 10368 y ^ 6 - 31104 y ^ 5 + 36288 y ^ 4 - 20736 y ^ 3 + 9504 y ^ 2 - 4320 y + 624 $
Т.е. все свелось к полиному степени 6.
В WolframAlpha базис получается такой же, как и у меня, но с точностью до константы:Базис

Если поменять порядок полиномов, то базис получается другой, включающий, цитированный в начале, полином восьмой степени:
$+ 24 x y ^ 2 - 24 x y + 20 x + 24 y ^ 3 - 48 y ^ 2 + 12 y - 4$

$+ 128 x y - 64 x + 192 y ^ 4 - 384 y ^ 3 + 256 y ^ 2 - 128 y + 26.6667$

$ - 298.667 x + 768 y ^ 6 - 1536 y ^ 5 + 768 y ^ 4 - 256 y ^ 3 + 704 y ^ 2 - 213.333 y + 78.2222$

$ + 3072 y ^ 8 - 6144 y ^ 7 + 8192 y ^ 6 - 15360 y ^ 5 + 19968 y ^ 4 - 11776 y ^ 3 + 5006.22 y ^ 2 - 2588.44 y + 400.593 $

$- 24576 y ^ 7 + 94208 y ^ 6 - 147456 y ^ 5 + 120832 y ^ 4 - 63488 y ^ 3 + 29013.3 y ^ 2 - 10012.4 y + 1232.59$

$ - 403685 y ^ 6 + 1.21105e+06 y ^ 5 - 1.41289e+06 y ^ 4 + 807367 y ^ 3 - 370043 y ^ 2 + 168201 y - 24295.7$

$- 136 y ^ 5 + 180 y ^ 4 - 126 y ^ 3 + 57 y ^ 2 - 30.5 y + 5.75 $

$+ 1002.35 y ^ 4 - 494.535 y ^ 3 + 195.096 y ^ 2 - 133.578 y + 13.8353 $

$ - 1735.48 y ^ 3 + 394.459 y ^ 2 - 481.804 y + 145.985 $

$+ 486.356 y ^ 2 - 84.8564 y + 62.1695 $

$+ 107.13 y - 27.9311 $

В данном базисе меня смушают полиномы относительно $y$, но степени ниже 8.
Некоторые из них и корней действительных не имеют.
Это неравильный базис, или так и должно быть?
И кстати в WolframAlpha базис не зависит от порядка следования полиномов, хотя в описании они используют тот же алгоритм Бухбергера.