научная статья по теме ОСТАНОВКА АЛГОРИТМА F5 Математика

Текст научной статьи на тему «ОСТАНОВКА АЛГОРИТМА F5»

ПРОГРАММИРОВАНИЕ, 2014, No 2, с. 12-26

КОМПЬЮТЕРНАЯ АЛГЕБРА -

УДК 512

ОСТАНОВКА АЛГОРИТМА F5

© 2014 г. В.В. Галкин МГУ им. М.В. Ломоносова, механико-математический факультет 119991 Москва, ГСП-1, Ленинские горы, МГУ, д. 1 E-mail: galkin-vv@ya.ru Поступила в редакцию 20.06.2013

Алгоритм F5, вычисляющий базис Грёбнера порождённого однородными многочленами идеала, был предложен в 2002г. Фожером одновременно с обоснованием его корректности при условии остановки. Но сама остановка была показана только для регулярной последовательности многочленов. В этой работе будет доказано, что алгоритм останавливается на любых входных данных. Вначале выводится, что если алгоритм не остановится, то он получит пару многочленов, в которой первый может редуцировать второй. При этом не утверждается, что такая редукция будет разрешена всеми критериями из F5. Далее показывается, что при существовании такой пары найдётся и пара, в которой редукция разрешена критериями, что невозможно.

1. ВВЕДЕНИЕ

Алгоритм Фожера Е5 является эффективным алгоритмом вычисления базисов Грёбнера, но обладает рядом проблем, связанных с его обоснованием. Корректность его работы при условии остановки показана в первоисточнике [6] и в работах [17, 16, 15], предложивших другие способы её доказательства. Но остановка алгоритма, как в [6], так и в детальных исследованиях [14], показана только для случая регулярной последовательности на входе. Один из подходов к решению проблемы — добавление в алгоритм дополнительных проверок и критериев, гарантирующих остановку. Это даёт строгое доказательство остановки для модифицированной версии Е5, содержащей дополнительные проверки, работа которой может отличаться от базовой. Этот подход применяется в работах [4, 1, 9, 10, 18].

Другой подход состоит в доказательстве остановки семейства алгоритмов, основанных на идеях Е5, с последующей попыткой переформулировать Е5 так, чтобы он являлся представителем этого семейства. Основная проблема этого подхода появляется в процессе переформулировки: описание Е5 в других терминах может привести к неявному внесению различий в поведение алгоритма. К примеру, [12] доказывает останов-

ку алгоритма F5GEN, который отличается от F5 отсутствием проверки критериев при выборе редуктора. Работа [11] даёт доказательство остановки алгоритма TRB-F5, который имеет два отличия от F5. Первое - другая схема построения правил, приводящая к тому, что в TRB-F5 правила в массивах Rule оказываются отсортированными по возрастанию сигнатуры. Второе - отсутствие применения перед редукцией оператора р, редуцирующего многочлен по базису Грёбнера предыдущего шага, из-за чего TRB-F5 при выборе редуктора проверяет критерии для элементов, которые в F5 используются внутри р неявно.

Предположительно, эти алгоритмы могут быть изменены таким образом, чтобы в точности повторять поведение алгоритма F5, а доказательство остановки может быть перенесено на изменённые версии. Однако такой подход будет иметь недостаток: он усложнит понимание того, как используемые для доказательства остановки теоремы отражают поведение исходного алгоритма F5.

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

идее цепей S-nap. Второй шаг основывается на методе, использованном в теореме 21 работы [5] для доказательства корректности алгоритма F5C: представление S-многочлена в виде суммы вычисленных ранее многочленов, домноженных на мономы, может быть модифицировано конечной последовательностью некоторых замен, и приведено к состоянию, когда выполняются определённые «хорошие» свойства.

Работа оформлена как доказательство остановки алгоритма, описанного в первоисточнике [6], построенное от противного. Рассматривается кольцо многочленов от нескольких переменных V = K[xi,..., xn] и многочлены fi,..., fm е V. Предполагается, что применение F5 для вычисления базиса Грёбнера идеала (f1,..., fm) относительно мономиального порядка < зацикливается при обработке последнего рассматриваемо-

fi

так как F5 рассматривает многочлены поочерёдно, начиная с последнего. Многие используемые обозначения, включая названия процедур, взяты из статьи [6], поэтому читатель предполагается достаточно глубоко знакомым с ней. Множество мономов, образуемых переменными x1,..., xn, будет обозначаться символом T (как и в [6]). Единичный моном выделяется жирным: 1 е T.

Определение 1. Сигнатурой называется пара (t. г), состоящая из монома t е T, и натурального числа г е N, называемого её индексом.

Множество сигнатур мы будем обозначать символом Т (как и в [6]). Индекс сиг натуры s будем записывать как index (s) .

Определение 2. Отмеченным, многочленом называется пара (s,f), состоящая из

s е Т f е V

зультатом умножения отмеченного многочлена h = (s, f) =((t. г), f) на моном m е T является снова отмеченный многочлен:

m ■ ((t. г), f) =f ((mt. г), mf).

Перечислим основные обозначения, примени-

h

S (h) — сигнатура отмеченного многочлена h;

poly (h) — многочлен f е V — вторая часть h;

HM (h), HC (h) — старшие моном и коэффици-f

index(h) — индекс сигнатуры S(h).

Определение отмеченного многочлена, данное в таком виде, формально связывает сигнатуру с V

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

(ti. г1) - (t2 . г2)

г1 > г2

г1 = г^ t1 < t2

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

Определение 3. При фиксированных многочленах f 1,..., fm будем называть отмеченный многочлен ((t. г), f) допустимым, если f представляется в виде суммы f = gjfj + gi+1fi+1 + ■ ■ ■ + gmfm в которой gk е V и HM (gi) = t, а также не существует представлений такого вида для (t'. г') — (t. г).

В дальнейшем, все рассматриваемые отмеченные многочлены будут допустимы, поскольку Предложение 2 работы [6] доказывает, что все отмеченные многочлены, порождаемые алгоритмом F5, допустимы. Термин "signature-safe" переведён как «сигнатурный».

Определение 4. Редукция отмеченного много-fg

ся сигнатурной редукцией, если S(f) >- t ■ S(g),

t=

HM(f)

HM(g) — моном, на который умножается

редуктор. Редуктор, соответствующий такой редукции, называется сигнатурным, редуктором.

2. ПСЕВДОКОД Р5

Для удобства дальнейших рассуждений об остановке алгоритма, приведём здесь полный псевдокод Е5, основанный на исходной формулировке. Отличия приводимого псевдокода от первоисточника выражаются лишь в небольших упрощениях символики и записи псевдокода, но не никак не изменяют сам алгоритм.

2.1. Глобальные переменные

2.3. Rewritten?

m R

#R

Rule

Вход:

Число входных многочленов.

Пополняемый массив отмеченных многочленов, нумеруемый натуральными числами, начинающимися с единицы. Числа, нумерующие элементы в нём, мы будем называть позициями, оставляя слово индекс для понятия «индекс сигнатуры». Большая часть процедур оперирует не с отмеченными многочленами, а с их позициями в этом массиве. Многочлен h, однажды добавленный в R, может мен ять poly (h) при редукции, но сигнатура всех элементов R

R

многочленами, которые навсегда ста-

m

и в процессе работы пополняется с конца.

Обозначает число отмеченных много-R

R

R

мента.

Массив правил перезаписи, содержа-m

соответствует ровно одному индексу сигнатуры и в свою очередь является пополняемым массивом чисел, являющихся позициями отмеченных R

лучается, что Rule содержит только «ссылки» на многочлены. Изначаль-m

вов, которые в процессе работы пополняются со стороны начала.

2.2. AddRule

k — позиция в R отмеченного многочлена, добавляемого в качестве правила.

Вход: u — моном, на который происходит

к

R

Результат: булево значение, равное True, если произведение u■ R[k] отбрасывается «критерием перезаписи».

1. L ^ Rule[index(R[k])]

2. r ^ число элементов L

3. for i = 1,..., r do:

(a) if uS(R[k]) делится на S(R[L[i]]): i. return к = L[i]

4. return false

2.4. Increment alF5

Данная процедура является основной точкой входа в алгоритм.

Вход:

F = [/i,...,/m] — упорядоченный массив однородных многочленов.

1. Добавить к

Rule[index(R[k])]

начало

массива

Переменные: i — номер этапа алгоритма, убывающий в процессе работы; Gi — множество позиций отмеченных много-R

нера идеала (/m-i+i,..., /m)

Результат: множество многочленов, образующее базис Грёбнера идеала

(/i , . . . , /m)

1. R ^ [((1. 1) ,/i), ((1. 2) ,/2),..., ((1. m) ,/m)]

2. Gm ^ {m}

3. for i = m — 1,..., 1 do:

(a) Gi ^ AlgorithmF5(((1. i) , /¿), Gi+i)

4. return {poly(R[r])|r e Gi}

2.5. AlgorithmF5

Вход: ((1. г) , fi) — отмеченный много-

член; Gi+1 — множество позиций отмеченных многочленов в R, образующих ранее вычисленный базис Грёбнера некоторого идеала. Многочлены, стоящие на этих позициях имеют индексы сигнатур, г

Переменные: ^ — оператор редукции; d — число, соответствующее минимальной степени оставшихся S-пар; P — упорядоченный список S-nap отмеченных многочленов; Pd — подмножество S-nap фиксированной степени; Fd, Rd — некоторые множества позиций в R, соответствующие многочленам фиксированной степени; r, p

R

зуемые при итерировании.

Результат: Gi — множество позиций от-

R

образующих базис Грёбнера идеала ({poly(R[r])|r е Gi+1}U fi) — то есть идеала порождённого многочленами fi,..., fm.

1. Gi = Gi+1 U {г}

2. ^ ^ оператор, производящий полную редукцию по множеству многочленов {poly(R[r])|r е Gi+1}

3. P ^ отсортированный по возрастанию сокращаемого монома список

{CritPair^, r, г, <^)|r е Gi+1}

4. while P = 0 do:

(a) d ^ deg^^^^^^^^^brn моном P[1])

(b) Pd ^ {p е P|deg(coKpaLnaeMbrn моном

p) = d}

(c) P ^ P \ Pd

(d) Fd ^ Spol(Pd)

(e) Rd ^ Reduction(Fd, Gi,

(f) for r е Rd do:

i. P ^ PUpeGiCritPair(r,p, г,^)

ii. Gi ^ Gi U {r} P

щаемого монома

Gi

2.6. CritPair

r1 , r2

гочленов в R; k — число — индекс сигнатур, для которого проверяется редуцированность; ^ — оператор редукции.

Перемен ные: t, t1, t2, U1, U2 — мономы.

Результат: множество S-nap отмеченных многочленов, с не

Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.

Показать целиком