Понкратьев Е. В. - Элементы КА

13. АЛГОРИТМЫ ВЫЧИСЛЕНИЯ РАЗМЕРНОСТНЫХ МНОГОЧЛЕНОВ 135

Теперь можно предложить следующую схему вычисления размерностного многочлена ωE (t) матрицы E = (eij ) 16i6n , основан-

16j6m

ную на формуле (13.9). Сначала, выбрав вектор (a, 0, . . . , 0) Nm,

где a = min16i6n{ei1 | ei1 6= 0}, и применив лемму 13.10, сведем нашу задачу к вычислению размерностного многочлена матри-

цы E1 с (m − 1) столбцом и размерностного многочлена матрицы

H = (hij ) 16i6n , такой, что 0 6 hi1 < ei1 (1 6 i 6 n). Для определе-

16j6m

ния ωH (t) применим формулу (13.9) (с матрицей H вместо E) и продолжим процесс до тех пор, пока не получим представление ωE (t) в виде суммы размерностных многочленов матриц с (m − 1) столбцом и размерностного многочлена ωH1 (t), где H1 — n×m-матрица с нулевым первым столбцом. Для вычисления ωH1 (t) применяем описанную процедуру ко второму столбцу и т. д.

13.11. ПРИМЕР. Вычислим многочлен Гильберта ωE (t) матрицы

Сначала находим a = 2. Применяя (13.9), получаем

ωE (t) = 2 −1ωE1 (t) + ωH (t − 2),

Заметим, что вычисление многочлена Гильберта ωE (t) по одному из алгоритмов А9, А10, А11 или А12 приводит к представлению

ющих в подобном представлении для ωE (t), когда ωE (t) вычисляется по одному из алгоритмов А9, А10, А11 или А12.

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

13.12. ЛЕММА. Пусть E = (eij ) 16i6n — n × m-матрица над N

16j6m

и τ 6 m — неотрицательное целое число. Тогда deg ωE (t) < τ если

итолько если для любого подмножества I, состоящего из m − τ элементов множества {1, . . . , m}, существует строка eI матрицы E, такая, что все элементы этой строки, стоящие в столбцах с индексами из I, равны нулю. В частности, ωE (t) = const тогда

итолько тогда, когда E содержит диагональную подматрицу.

Доказательство леммы проводится индукцией по сумме элементов матрицы E и оставляется читателю в качестве упражнения.

Матрицу E над N назовем нормализованной, если каждый столбец матрицы E содержит нуль. Ниже будет показано, что если E — нормализованная n ×m-матрица, то алгоритм вычисления размерностного многочлена ωE (t), основанный на лемме 13.10, требует меньшего числа операций, чем для произвольной n×m-матрицы. В то же время, для сведения задачи вычисления размерностного многочлена произвольной n×m-матрицы над N к аналогичной задаче для нормализованной n ×m-матрицы можно воспользоваться теоремой 12.8(9).

13.13. ЛЕММА. Пусть E = (eij ) 16i6n — n×m-матрица над N

16j6m

ипредположим, что deg ωE = 0.

(1)Если e1j = 0 при j = 2, . . . , m и ei1 = 0 при i = 2, . . . , n, то

ωE = e11ωE1 , где (n − 1)×(m − 1)-матрица E1 получена из E удалением первой строки и первого столбца.

(2)Если матрица H получена из E посредством обнуления первого столбца, то ωH = 0.

(3)Если a = min16i6n{ei1|ei1 6= 0}, то

где матрица E1 получена из E удалением первого столбца и всех строк, содержащих ненулевые элементы в пер-

вом столбце, а E2 = (e′ij ) 16i6n , где

16j6m

ДОКАЗАТЕЛЬСТВО. (1) Если e11 = 0, то в E имеется нулевая строка, следовательно, ωE = 0 (см. теорему 12.8(6)). Если e11 > 0, то

13. АЛГОРИТМЫ ВЫЧИСЛЕНИЯ РАЗМЕРНОСТНЫХ МНОГОЧЛЕНОВ 137

применяя (12.2) к E и e = (1, 0, . . . , 0) Nm, получаем

Таким образом, индукция по e11 дает требуемый результат.

(2)Лемма 13.12 утверждает, что E содержит строку, в которой ненулевой может быть только первая координата. Значит H содержит нулевую строку, следовательно, ωH = 0.

(3)Соотношение (13.10) следует из (12.2), записанного для E и

Пользуясь леммой 13.13, можно предложить следующий метод вычисления многочлена Гильберта ωE матрицы E в случае, когда deg ωE = 0: применить соотношение (13.10) к ωE (где a — минимальный ненулевой элемент в первом столбце матрицы E), затем выписать аналогичное представление для E2 и т. д. После конечного числа таких шагов получим представление многочлена ωE в виде суммы многочленов Гильберта матриц F1, . . . , Fr (r N, r > 1) с (m − 1) столбцами и многочлена Гильберта ωH , где элементы мат-

рицы H = (hij ) 16i6n равны

16j6m

так что ωH = 0 (см. лемму 13.13(2)). Применяя описанную процедуру к каждой из матриц F1, . . . , Fr , мы сводим вычисление многочлена ωE к вычислению многочленов Гильберта для некоторых матриц с (m −2) столбцами и т. д., пока не получим матрицы, состоящие из единственного столбца. Как мы знаем, многочлен Гильберта такой матрицы совпадает с ее минимальным элементом.

В общем случае (без условия deg ωE = 0) вычисление размерностного многочлена ωE (t) для n ×m-матрицы E = (eij ) 16i6n по

16j6m

описанной схеме (используя (13.9) вместо (13.10)) можно свести к вычислению размерностных многочленов матриц, число столбцов в которых меньше m, и размерностных многочленов некоторых n×m-матриц с нулевым первым столбцом. Более точно: если первый столбец матрицы E содержит ненулевые элементы, то мы полагаем a = min16i6n{ei1|ei1 6= 0} и применяем (13.9). Затем применяем то

же самое соотношение к H (см. лемму 13.10) и т. д. В результате получим разложение многочлена ωE (t) в сумму многочленов вида ωEi (t − ai), где ai N и Ei — либо матрица, число столбцов в которой меньше m, либо n×m-матрица с нулевым первым столбцом. Для вычисления размерностных многочленов матриц второго типа применяем описанный метод ко второму столбцу и т. д., пока не получим представление многочлена ωE (t) в виде суммы размерностных многочленов матриц, число столбцов в которых меньше m, и размерностных многочленов матриц с не более чем двумя ненулевыми столбцами. Размерностный многочлен матрицы последнего типа может быть найден с помощью следующего утверждения.

13.14. ЛЕММА. Пусть

— нормализованная n×m-матрица над N (m > 2). Предположим, что 0 = e11 < e21 < · · · < en1 и e12 > e22 > · · · > en2 = 0. Тогда

i=1

где ei = (ei2, 0, . . . , 0) Nm−1 (i = 1, . . . , n − 1).

ДОКАЗАТЕЛЬСТВО. Воспользуемся индукцией по n. Случай n = 1 тривиален. Пусть n > 1, и предположим, что утверждение леммы доказано для всех матриц, число строк которых меньше n. Для доказательства соотношения (13.11) для n×m-матрицы E = (eij ) 16i6n ,

16j6m

у которой eij = 0 (1 6 i 6 n, 3 6 j 6 m), прежде всего заметим, что если a = min16i6n (ei1 | ei1 6= 0) = e21, то

140 ГЛАВА 4. ЦЕЛОЗНАЧНЫЕ МНОГОЧЛЕНЫ

выбор

Card K = 2, K = {j, p} = сортировать строки по возраста-

нию j-го столбца

удалить лишние строки

Card K > 2 взять k K

переставить k-й столбец с первым

NS := 0

E0 :=

цикл для каждого ненулевого ei1 в возрастающем порядке

NR := ei1

E0: добавить последовательность строк

{(ej2, . . . , ejm)|ej1 = NS }

N0 := число векторов в E0

Алгоритм А13 (E0, N0, m − 1, P0(t))

P0(t) := −1P0(t) ω(t) := ω(t) + P0(t − NS )

NS := NR

конец цикла

E: обнулить первый столбец Алгоритм А13 (E, n, m, P1(t))

ω(t) := ω(t) + P1(t − NS )

конец выбора

Приведенный здесь алгоритм А13 вычисления многочлена Гильберта ωE (t) для n ×m-матрицы E основан на данной выше схеме. В соответствии с ней, воспользуемся (13.8), чтобы представить многочлен ωE (t) в виде суммы многочленов Гильберта матриц, которые содержат менее m столбцов, и многочлена Гильберта n×m-матрицы E′, содержащей не более двух ненулевых столбцов (без потери общности можно считать, что ненулевыми являются два первых столбца матрицы E′). Многочлен ωE′ (t) вычисляется с помощью соотношения (13.10). Сначала переупорядочим строки так, чтобы элементы первого столбца удовлетворяли условию леммы 13.14 (такое переупорядочение требует n log n элементарных операций). Тогда видно, что если второй ненулевой столбец не упорядочен в обратном порядке, то матрица E′ содержит лишние строки (в точности те строки

13. АЛГОРИТМЫ ВЫЧИСЛЕНИЯ РАЗМЕРНОСТНЫХ МНОГОЧЛЕНОВ 143

Из теоремы 12.8(9) и леммы 13.12 легко следует, что

Вычисление коэффициента am−2(E) (при m > 2) может основываться на следующем утверждении.

13.17. ЛЕММА. Пусть E = (eij ) 16i6n — n ×m-матрица над

16j6m

N, такая, что m > 1 и первый столбец матрицы E нулевой.

и 0 < deg ωE 6 τ (τ Nm). Далее, пусть E1 — n×(m −1)-матрица, полученная из E удалением первого (нулевого) столбца. Тогда

где a = min16i6n{ei1|ei1 6= 0}, матрица E1 получена из E удалением первого столбца и всех строк с нулем в первом столбце, а E2 =

144 ГЛАВА 4. ЦЕЛОЗНАЧНЫЕ МНОГОЧЛЕНЫ

(Соотношение (13.14) легко может быть установлено применением (12.2) к E и (a, 0, . . . , 0) Nm.)

Прежде чем вычислять коэффициент am−2(E) многочлена Гильберта (13.13), заметим, что, без потери общности, можно предполагать, что deg ωE 6 m − 2. Действительно, применяя (12.2) к E и

(1 6 i 6 n, 1 6 j 6 m). Пользуясь (11.4), можно переписать последнее представление ωE (t) в виде

не более двух ненулевых столбцов (следует отметить, что если в E имеется единственный ненулевой столбец, то многочлен Гильберта ωE (t) совпадает с минимальным элементом этого столбца). Предполагая, что первый столбец матрицы E ненулевой, упорядочим его элементы и применим (13.14) при τ = m − 2. Поскольку число столбцов в E1 (см. (13.14)) равно (m − 1), вычисление aτ (E1) можно свести к выбору минимальных элементов в столбцах матрицы E1 (см. теорему 12.8(3)). Легко видеть, что такой выбор требует (m −1)b1 элементарных операций, где b1 — число строк матрицы E1.