Journal influence
Bookmark
Next issue
Solution of simultaneous polynomial equations on a computer
The article was published in issue no. № 3, 2012 [ pp. 22-25 ]Abstract:The article offers the accelerated algorithm of Groebner bases search used in the course of solution of simultaneous polynomial equations. The proposed algorithm considers the issue of word size overflow and incorrect computations in the course of calculating on the computer. The classical Buchberger's algorithm and the updated Faugere's algorithm require a lot of steps; meanwhile they do not contain any additional actions on correction of floating point numbers computations that causes some errors and incorrect computation of simultaneous equations roots and irrational factors. The new algorithm by several times reduces the number of operations of polynom quantity reduction, does not store all possible pairs of polynoms and does not check them for the fact that one can be expressed in terms of the other. The algorithm proposed in the article operates only with that number of polynoms which are now a basis. The basis is expanded if none of the polynoms represented in it can be represented in the form of combination of the other polynoms of this basis. Otherwise, the extra polynom shall be removed from the basis that helps avoid overgrowth of the basis and excess operations with this polynom. In order to avoid the problem of incorrect computations because of the word size of the computer the algorithm envisages post-check. If any of the polynoms is reduced, then the initial polynom should be represented by the combination of the reduced polynom and the rest of the basis polynoms. If the values of coefficients of the equal monoms do not coincide after that, then the coefficients of the reduced polynom require correction by the error size.
Аннотация:Предложен ускоренный алгоритм поиска базисов Грёбнера, используемых при решении систем полиномиальных уравнений. Данный алгоритм рассматривает проблему переполнения разрядной сетки и некорректных вычислений при проведении расчетов на ЭВМ. Классический алгоритм Бухбергера и обновленный алгоритм Фужера требуют большего числа шагов, при этом не содержат дополнительных действий по коррекции вычислений чисел с плавающей запятой, что приводит к ошибкам и неверному вычислению корней системы уравнений для иррациональных коэффициентов. Новый алгоритм в несколько раз уменьшает количество операций редукции числа полиномов, не хранит все возможные пары полиномов и не проверяет их на то, что один может быть выражен через другой. Предложенный в статье алгоритм оперирует только тем количеством полиномов, которые в данный момент представляют собой базис. Базис расширяется, если ни один из его полиномов не может быть представлен в виде комбинации других полиномов базиса. В противном случае лишний полином удаляется из базиса, что позволяет избежать чрезмерного разрастания базиса и лишних операций с этим полиномом. Чтобы избежать проблем некорректных вычислений из-за разрядной сетки компьютера, алгоритм предусматривает постпроверку. Если какой-либо полином редуцируется, то исходный полином должен быть представлен комбинацией редуцированного полинома и остальных полиномов базиса. Если значения коэффициентов одинаковых мономов после этого не совпадают, коэффициенты редуцированного полинома требуют коррекции на величину ошибки.
Authors: ( ilyozin@yandex.ru) - , Ph.D | |
Keywords: Buchberger algorithm, Faugere algorithm, Grobner basis, systems of polynomial equations |
|
Page views: 10240 |
Print version Full issue in PDF (7.64Mb) Download the cover in PDF (1.33Мб) |
Системы полиномиальных уравнений в общем случае решаются построением базиса Грёбнера из базиса, составленного многочленами рассматриваемой системы, и решением системы уравнений, левые части которых являются многочленами, составляющими базис Грёбнера [1]. В числе самых широко распространенных методов для построения базиса Грёбнера – алгоритм Бухбергера и алгоритм Фужера [2–4]. Однако оба они при относительной простоте выполняемых преобразований имеют очень высокую операционную сложность, что затрудняет, а зачастую делает невозможным вычисление базиса. Следует также учитывать дополнительный фактор, усложняющий задачу и делающий невозможным применение имеющихся подходов в чистом виде: поскольку коэффициенты полиномов в системе являются иррациональными числами, представленными в памяти ЭВМ с некоторой степенью точности, при выполнении арифметических операций погрешность будет накапливаться, что в конечном итоге неизбежно приведет к ошибкам и сбою алгоритма. Следовательно, требуется найти алгоритм, позволяющий строить базис Грёбнера с меньшей вычислительной сложностью, чем имеющиеся алгоритмы, а также работать с иррациональными коэффициентами. За основу данного метода можно взять некоторые приемы из уже упомянутых алгоритмов Бухбергера и Фужера. Итак, пусть K – поле вещественных чисел, K[x, y] – кольцо многочленов от двух переменных с коэффициентами из K. Рассмотрим некоторый идеал I над кольцом многочленов, в который входят полиномы из системы. Множество H={g, h} является базисом идеала I. Зададим лексикографическое упорядочение мономов в многочленах:
Используя операции сложения и умножения над многочленами, входящими в базис H, необходимо редуцировать его так, чтобы построить базис Грёбнера идеала I. Введем понятие S-полинома [2]:
Здесь LT(fi) представляет старший терм многочлена fi(x, y), а LCM(fi, fj) равен наименьшему моному, который делится на старшие мономы многочленов fi(x, y) и fj(x, y). Операцией редуцирования произвольного полинома f(x, y) из K[x, y] относительно H является нахождение такого минимального многочлена r(x, y), который выражается в виде
где ai(x, y)ÎK[x, y] и fi(x, y)ÎH. Базис H можно назвать базисом Грёбнера, если для любых двух полиномов fi(x, y) и fi(x, y) из H выполняется условие
При заданном лексикографическом упорядочении (1) базис Грёбнера будет составлен парой многочленов, удовлетворяющих условию (4), вида
Множество решений системы, составленной из полиномов (5), будет соответствовать множеству решений системы. Алгоритм нахождения базиса Грёбнера представлен в виде блок-схемы (см. рис.). На вход алгоритма редукции подается базис H идеала I, составленный из множества полиномов исходной системы уравнений. Каждая итерация алгоритма редуцирования базиса начинается с того, что в базисе H ищется полином fi(x, y) с минимальным старшим мономом, который может быть редуцирован относительно множества полиномов, состоящего из всех полиномов базиса, кроме выбранного полинома. Дальнейшее выполнение алгоритма разбивается на две ветви. Если такой полином найден, он исключается из базиса и находится остаток r(x, y) от редукции этого полинома. Произвольный полином является редуцируемым относительно некоторого множества полиномов, если в этом множестве есть многочлены, старшие мономы которых являются делителями старшего монома редуцируемого полинома. Редукция полинома – итеративный процесс. Если перед редукцией остаток r(x, y) принять равным исходному редуцируемому полиному fi(x, y), то на каждом шаге уменьшения остатка осуществляется поиск максимального полинома fj(x, y) в множестве H, который может редуцировать остаток r(x, y), и выполняется редукция
где LC(r) – коэффициент перед старшим мономом многочлена r(x, y).
Перед добавлением остатка в базис следует провести корректировку коэффициентов для r(x, y). В кольце K[x, y] необходимо найти такие многочлены ag,i(x, y), ah,i(x, y), ag,r(x, y) и ah,r(x, y), чтобы можно было представить полиномы g(x, y) и h(x, y) в базисе H+{r}:
Если решение системы (7) не находится, значит, при вычислениях в коэффициентах остатка накопилась методическая погрешность из-за способа представления вещественных чисел в памяти ЭВМ. Так как уже имеющиеся в базисе полиномы имеют правильные значения коэффициентов, необходимо откорректировать коэффициенты остатка r(x, y) в соответствии со значениями погрешности для каждого из коэффициентов в системе (7). Эта задача решается подобно задаче редуцирования: сначала определяются значения коэффициентов для полиномов ag,i(x, y) и ah,i(x, y), затем вычисляются разности:
Если разности представляют собой нулевые полиномы, то одну или несколько базисных функций fj(x, y) нужно исключить из суммы и повторить операцию. По оставшимся разностям вычисляются коэффициенты полиномов ag,r(x, y) и ah,r(x, y) и корректируются (при необходимости) коэффициенты r(x, y). После этого r(x, y) добавляется в базис H и алгоритм редуцирования базиса идет на очередную итерацию. По второй ветви алгоритм редуцирования базиса развивается, если в базисе H не найден полином, который может быть редуцирован. В таком случае набор базисных функций должен быть расширен для продолжения редукции. Из всех возможных пар полиномов базиса fi(x, y) и fj(x, y), для которых не выполняется условие (4), нужно найти пару с минимальным LCM(fi, fj). Если такая пара найдена, редуцированный остаток S-полинома этой пары включается в базис H, предварительно пройдя корректировку коэффициентов, как это было описано ранее. Если же такой пары многочленов в базисе H нет, значит, этот базис полностью редуцирован и является базисом Грёбнера. Таким образом, в результате работы алгоритма получим базис, составленный из пары многочленов (5). Теперь для решения исходной системы нужно вычислить все корни Сравнительный анализ на конкретных примерах показал, что новый алгоритм в несколько раз быстрее существующих, что с учетом его адаптации к вычислениям на ЭВМ делает данный алгоритм более предпочтительным при решении задач нахождения базисов Грёбнера и, как следствие, отыскания корней систем полиномиальных уравнений. Литература 1. Прасолов В.В. Многочлены. М.: МЦНМО, 2001. 2. Buchberger B. Grobner Bases: an Algorithmic Method in Polynomial Ideal Theory / Recent trends in multidimensional system theory, U. Reidel Publishing Company, 1985. 3. Buchberger's algorithm. URL: http://www.geocities.com/ famancin/buchberger.html (дата обращения: 01.06.12). 4. Faugere J.C. A new efficient algorithm for computing Grobner bases (F4) // Journal of Pure and Applied Algebra, 1999, no. 139, pp. 61–88. |
Permanent link: http://swsys.ru/index.php?id=3205&lang=en&page=article |
Print version Full issue in PDF (7.64Mb) Download the cover in PDF (1.33Мб) |
The article was published in issue no. № 3, 2012 [ pp. 22-25 ] |
Back to the list of articles