2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Решение системы полиномиальных уравнений
Сообщение09.02.2013, 16:16 


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

 Профиль  
                  
 
 Re: Решение системы полиномиальных уравнений
Сообщение10.02.2013, 08:28 
Заслуженный участник


15/05/05
3445
USA
Вот краткое введение в теорию:
Аржанцев И. В. Базисы Грёбнера и системы алгебраических уравненийю 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 раз....

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

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

 Профиль  
                  
 
 Re: Решение системы полиномиальных уравнений
Сообщение10.02.2013, 16:03 


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

 Профиль  
                  
 
 Re: Решение системы полиномиальных уравнений
Сообщение10.02.2013, 19:17 
Заслуженный участник


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

И поправка:
Вместо
Цитата:
...
Повторить пары шагов "найти-решить" еще 99998 раз....
Должно быть
Цитата:
...
Повторить пары шагов "найти-решить" еще 99997 раз.
Найти последнее неизвестное, подставив все ранее найденные неизвестные в одно из исходных уравнений, в которое это последнее неизвестное входит.

 Профиль  
                  
 
 Re: Решение системы полиномиальных уравнений
Сообщение10.02.2013, 23:30 


09/02/13
31
Yuri Gendelman в сообщении #682220 писал(а):
Дополнительная ссылка:
Bernd Sturmfels. Solving Systems of Polynomial Equations. 2002

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

 Профиль  
                  
 
 Re: Решение системы полиномиальных уравнений
Сообщение13.02.2013, 00:41 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Решение системы полиномиальных уравнений
Сообщение13.02.2013, 19:20 
Заслуженный участник


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

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

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

 Профиль  
                  
 
 Re: Решение системы полиномиальных уравнений
Сообщение13.02.2013, 21:48 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Решение системы полиномиальных уравнений
Сообщение13.02.2013, 22:33 
Заслуженный участник


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

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

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

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

 Профиль  
                  
 
 Re: Решение системы полиномиальных уравнений
Сообщение14.02.2013, 03:59 


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

 Профиль  
                  
 
 Re: Решение системы полиномиальных уравнений
Сообщение14.02.2013, 10:04 


09/02/13
31
Yuri Gendelman в сообщении #682034 писал(а):
Теперь осталось решить это уравнение 8-го(!) порядка, найти возможные значения $y$, подставить их в 1-е исходное уравнение и найти $x$.

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

 Профиль  
                  
 
 Re: Решение системы полиномиальных уравнений
Сообщение14.02.2013, 19:55 
Заслуженный участник


15/05/05
3445
USA
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 писал(а):
Отсюда вопрос: Как определить(оценить) степень уравнений в базисе Грёбнера, получаемом из моей системы?
Не понял вопроса. Как, глядя на уравнение из базиса Грёбнера, определить его степень?

 Профиль  
                  
 
 Re: Решение системы полиномиальных уравнений
Сообщение14.02.2013, 21:00 


09/02/13
31
Yuri Gendelman в сообщении #683952 писал(а):
Не понял вопроса. Как, глядя на уравнение из базиса Грёбнера, определить его степень?

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

 Профиль  
                  
 
 Re: Решение системы полиномиальных уравнений
Сообщение14.02.2013, 21:49 
Заслуженный участник


15/05/05
3445
USA
AndrewSu в сообщении #683980 писал(а):
Я имел в виду - определить степень до построения базиса.
Не знаю. И не уверен, что это проще, чем построить базис.

 Профиль  
                  
 
 Re: Решение системы полиномиальных уравнений
Сообщение19.02.2013, 00:09 


09/02/13
31
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$

:D $ + 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 базис не зависит от порядка следования полиномов, хотя в описании они используют тот же алгоритм Бухбергера.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 23 ]  На страницу 1, 2  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group