Быстрый алгоритм проверки вырожденности ганкелевых матриц

ЧЕБЫШЕВСКИЙ СБОРНИК Том 12 Выпуск 2

Труды VIII Международной конференции Алгебра и теория чисел: современные проблемы и приложения, посвященной 190-летию Пафнутия Львовича Чебышева и 120-летию Ивана Матвеевича Виноградова

УДК 510.52

БЫСТРЫЙ АЛГОРИТМ ПРОВЕРКИ ВЫРОЖДЕННОСТИ ГАНКЕЛЕВЫХ МАТРИЦ*

Кузнецов Ю.В., Петрунин М.М. (г. Москва) ykuz@niisi.ras.ru,

petrunin@niisi.ras.ru

Аннотация

Из результатов работ 2009-2010 годов Платонова В.П. (совместно с Беняш-Кривецем В.В.) следует, что в случае эллиптических полей эффективность алгоритмов вычисления нетривиальных единиц напрямую определяется эффективностью алгоритмов проверки вырожденности соответствующих ганкелевых матриц. В этой связи был разработан асимптотически наилучший рекурсивный алгоритм проверки вырожденности ганкелевых матриц сложности O(n log2 n), который не накладывает ограничений на невырожденность ведущих подматриц и для этого алгоритма вычислена мультипликативная константа 468.

Интерес к построению и изучению быстрых алгоритмов проверки вырожденности ганкелевых или теплицевых матриц объясняется следующими обстоятельствами. В серии работ [1]-[3] 2009-2010 годов Платоновым В.П. (совместно с Беняш-Кривецом В.В.) была обнаружена глубокая связь между проблемой существования нетривиальных единиц в гиперэллиптичееких полях с произвольным полем констант, формальными рядами Лорана и ганкелевыми матрицами. При этом выяснилось, что в случае эллиптических полей существенную роль играет эффективность алгоритмов для проверки вырожденности ганкелевых (или теплицевых) матриц.

В такой постановке подобная проблема ранее не ставилась. Как правило требовалось эффективно найти решение системы с тёплицевой матрицей над

* Работа выполнена при финансовой поддержке Российского Фонда Фундаментальных Исследований, гранты 09-01-00287-а и 11-01-12002-офи-м-2011

комплексным полем С или действительным полем R при условии невырожденности самой матрицы. Первоначально на матрицы накладывались также дополнительные условия: требовалась невырожденность всех её ведущих подматриц. Именно для этого случая были построены наиболее эффективные алгоритмы решения соответствующих систем [4].

Первым асимптотически наилучшим алгоритмом решения указанных систем (со сложностью O(nlog2 n)), который не накладывал ограничений на невырожденность ведущих подматриц стал рекурсивный алгоритм Брента, Густав-сона и Юна [6].

У казанная работа фактически содержит алгоритм проверки вырожденное™ тёплицевых матриц над полем С с асимптотической еложноетыо O(nlog2 и). Возник вопрос о вычислении мультипликативной константы для этого алго-

С

и составляет 468, Предполагается, что вычисления производятся в модели с использованием дискретного преобразования Фурье (см, [8]),

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

Напомним понятие расширенного алгоритма Евклида для многочленов. Пусть даны многочлены а и b, deg a > deg b, Положим

где ^ - частное, полученное от деления Мг_1 на щ, а, щ+\ - соответствующий остаток.

Как известно, для всех г > 0 выполняется

при этом алгоритм остановится на шаге і = к, при котором пк+1 = 0, т.е. пк делит пк-1, В этом случае пк - это НОД(а,Ь), а wk и Ук - это такая пара многочленов, что Wки0 + Укп1 = НОД(а, Ь).

Если у нас имеются 2 соседних члена и* и пі+і последовательности остатков {•и^}, то переход к следующей паре пі+1, щ+2 можно представить в виде

по = а,щ = b, v0 = 0, v\ = 1, w0 = 1, w\ = 0,

її определим

Пі+1 = Пі-1 - QiUi,

vi+i = Vi-1 - qiVi,

Wi+1 = Wi-1 - qiWi,

WiU о + ViU1 = Пі,

HOfl(Vi,Wi) = 1,

Ui+1

Ui+2

01

1 —qi+1

Ui

Ui+1

или

Щ

«і+1

5і+і 1 1 0

Матрицу вида

Я 1 I

1 д ), вде deg д > 0 будем называть элементарной, а про-

изведение конечного числа пхоизвоаьных элементарных матриц - регулярной

последовательности остатков, т.е. для некоторого га! = щи Ь' = Иг+1 [7].

Напомним понятие ПолуНОД-алгоритмов для многочленов [5]. Эти алгоритмы по паре многочленов а и Ь, deg(a) > deg(b), строят матрицу перехода Q

ПолуНОД-алгорптмы в первую очередь служат для построения соответствующих рекурсивных алгоритмов поиска НОД, но помимо этого часто используются как независимые процедуры в других алгоритмах.

История создания и изучения ПолуНОД-алгоритмов для многочленов недостаточно широко известна и носит, на наш взгляд, драматический характер. Первый такой алгоритм в 1973 году предложил Моенк, Однако его алгоритм корректно работал не для любой пары входных многочленов, а только для пары многочленов, которые порождают так называемую “нормальную” последовательность остатков, В широкоизвестной и цитируемой почти всеми специалистами по алгоритмам монографии Ахо, Хопкрофта и Ульмана [5] в 8-й главе приводится доказательство корректности алгоритма Моенка для всех входных пар многочленов, которое, ввиду указанных выше причин, ошибочно, В 1980ом году в вышеуказанной работе Брента, Густавсона и Юна [6], также широко цитируемой специалистами по тёплицевым матрицам, был предложен модифицированный алгоритм Моенка, который действительно корректно работал для всех входов. Однако, корректность своего алгоритма Брент, Густавсон и Юн доказать не смогли. Вместо этого они отсылали читателей к вышеупомянутой монографии Ахо и др, [5] и пообещали представить полное доказательство корректности в последующей работе. Наконец, только спустя 10 лет появился манускрипт К,Тула и Ч, К, Япа [7], в котором была полностью доказана корректность алгоритма Брента, Густавсона и Юна, При этом Туп и Яп утверждали, что они разработали тот же самый алгоритм независимо.

Приведём описание ПолуНОД-алгоритма из работы Тула и Япа [7], который авторы в этой работе называют НССГ). Отметим, что КЖХ'П из работы [6]

, для некоторого г, то Q - регулярная

Примечательно, что верно и обратное утверждение, а именно, если

, ^ ^ матрица и deg(a') > deg(Ь'), то а' и Ь' - соседние члены

такую, что

Брента и др, фактически совпадает с ИСК'!), но дополнительно на каждом шаге вычисляет пару многочленов щ,щ+1, что для наших целей является лишней операцией.

Вход: многочлены a, b, для шторых deg b < deg а = n.

Выход: регулярная матрица Q такая, что deg(C) > n/2 > deg(d), где

Известно, что асимптотическая сложность вышеуказанного ПолуНОД-ал-горитма составляет O(n log2 n), Наша дальнейшая цель - подсчитать мультипликативную константу для этого алгоритма.

Утверждение 1. Сложность полуНОД-алгоритма HGCD для двух много-

п = 2к и 234п к^2<п) + 0<п к^(п)) для всех п.

Доказательство. Через Т<п) обозначим сложность алгоритма НССБ для многочленов а, Ь, при условии, что п = deg а > deg Ь, а через М<п) - сложность

п

Рассмотрим случай п = 2к,

Алгоритм HGCD

Описание алгоритма HGCD(a,b):

1. m := Г1;

если deg(b) < т, алгоритм закапчивает работу и возвращает единичную матрицу Е;

2, ао := а div xm; b0 := b div xm; R := HGCD(ao,bo);

3, если deg(b;) < m, алгоритм заканчивает работу и возвращает R

5, l := deg(c); k := 2m — l;

6, c0 := c div xk; d0 := d div xk;

S := HGCD(co, do);

членов степени не более n не превосходит 117nlog^n) + O(nlog(n)) в случае

Будем оценивать Т(п) в соответствии с шагами алгоритма НССБ,

На шаге 2 вычисление а0 и Ь0, очевидно, не требует арифметических операций, При рекурсивном вызове алгоритма для пары а0, Ь0 число операций не будет превосходить Т(п), т.к. deg(Ь0) < deg(a0) = п — т = |-

Далее заметим, что обращения матрицы К можно избежать, если договориться, что выходом алгоритма является не вышеуказанная матрица Q, а обратная к ней. При этом шаг 7 необходимо изменить следующим образом:

Теперь необходимо оценить степени многочленов, входящих в матрицу Я, Можно показать, что матрица Я состоит из тех же элементов (с точностью до знака), что и матрица Я-1, Для оценки степеней этих элементов необходимо воспользоваться леммой 1 и так называемым “свойством порядка” регулярной матрицы из вышеуказанной работы Тула и Япа [7], В результате удается показать, что степени всех элементов матрицы Я те превосходят deg(ao) < П-

Таким образом, число дополнительных операций на шаге 2 составляет не более 4М(п) + 0(п),

На шаге 4 необходимо вычислить частное а/ йт Ь/ и остаток a/modb/, Обозначим через О(п) сложность деления с остатком многочлена f на многочлен д, где deg<g) = п и deg f < 2п — 1, Учитывая, что т < deg(b/) < deg(a/) < п, получаем, что число операций па шаге 4 не превосходит О(п).

На шаге 6 происходит рекурсивное обращение к алгоритму НССБ для пары многочленов с0 и й0, Оценим deg<c0), Имеем deg<c0) = I — к = 2(1 — т) = 2(deg(b/) — т) < п.

Наконец, оценим число необходимых операций па шаге 7, Запишем Б-1 в

потребуется те бол ее 2М < п) от ерцций. Полученную матрицу обозначим че-

и 4М(п) операций.

Таким образом, имеет место неравенство

п п п

Т

Про М(п) а О(п) известно, что М(п) > 2М(п/2) и Д(п) > 2Д(п/2)(см, [5], глава 8),

Получаем:

Т

Таким образом, T(n) < (11M(n) + D(n))log2(n) + O(n),

Учитывая, что M(n) < 9nlogn + O(n), a D(n) < 18nlogn + O(n) [8], [10], получаем неравенство

T

Теперь вернёмся к общему случаю. Учитывая, что для произвольного п 2[1og2(n)] < n < а также, что T(n) те убывает с ростом n, получаем

T(n) < T(2[1ofl2(n)]+1) = T(2 • 2[1ofl2(n)]) <

117 • 2 • 2[1og2(n)] log2(2 • 2[1og2(n)]) + O(nlog2(n)) =

234 • 21og2(n)(1 + log2(2[1og2(n)]))2 + O(nlog2(n)) <

234 • n • (1 + log2(n))2 + O(nlog2(n)) <

234 • n • log2

Напомним, что тёплицевой матрицей, называется матрица вида,

an-1 a n i to . «2 a1 ao

an+1 an an-1 . . «3 «2 a1

an+2 an+1 an . . a4 «3 a2

a2n-2 a2n-3 a2n-4 . . an an-1 a n i to

a2n-1 a2n-2 a2n-3 . . an+1 an an-1

^ a2n a2n-1 a2n-2 . . an+2 an+1 an

Напомним также понятие аппроксимации Паде, Пусть а(ж) = а0 + +

а2ж2 + ... - степенной ряд с а0 = 0, Рациональная функция вида, м(ж)/^(ж) называется (т, п) аппроксимантом Паде для ряда а(ж), если

deg(м) < т, deg(v) < п,

а(ж)г>(ж) — и (ж) = 0(жт+га+1).

Элементарное изложение основных результатов теории Паде доступно в [9], Известно, что существует тесная связь между тёплицевой матрицей и аппроксимацией Паде, а именно, при нахождении коэффициентов многочленов •и(ж) и и(ж) возникает система линейных уравнений с тёплицевой матрицей. Рассмотрим многочлен Ь = ^2=!0 а^жг, где а^ коэффициенты пашей тёплицевой матрицы, и многочлен а = ж2га+1, В работе [6] показано, что на каждом шаге расширенного алгоритма Евклида, применённого к многочленам а и Ь, вычисляется, в частности, некоторый аппроксимант Паде, Можно показать, что

вырожденноеть тёплицевой матрицы определется расположением аппроксиман-та Паде, полученного на заключительном шаге ПолуНОД алгоритма, в таблице Паде, С использованием указанного факта в работе [6] показано, что тёплицева T

ент при n-й степени полинома Uj в последовательности остатков расширенного алгоритма Евклида uo = a, u1 = b, u2 ..., где deg(uj-1) > deg(a,) > deg(uj),

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

Теорема 1. Сложность алгоритма проверки вырожденности тёплицевой матрицы n х n не превосходит 234n log2(n) + O(n log2(n)) в случае n = 2k и не превосходит 468n log2(n) + O(n log2(n)) e общем случае

Доказательство. Проверка вырожденности тёплицевой матрицы сводится к построению многочленов a и b, применению к ним алгоритма HGCD и ерав-n uj

образом, совпадает со сложностью алгоритма HGCD применённого к многочленам степени не более 2n+1 и те превосходит 468n log2

СПИСОК ЦИТИРОВАННОЙ ЛИТЕРАТУРЫ

[1] В, П, Платонов, В, В, Беняш-Кривец, Группы S-единиц в гиперэллиптиче-ских полях и непрерывные дроби, Матем, сб., 200, 11, 2009, 15-44

[2] В, П, Платонов, Арифметика квадратичных полей и кручение в якобианах, Доклады Академии Наук, 430, 3, 2010, 318-320

[3] В, П, Платонов, В, В, Беняш-Кривец, О новом локально-глобальном принципе для квадратичных функциональных полей, Доклады Академии Наук, 433, 2, 2010, 154-157

[4] Tyrtvshnikov Е.Е. Fast algorithms for toeplitz and quasi-toeplitz systems, J, Numer, Anal, Math, Modelling, 4, 5, 1989, 419-430,

[5] Aho A, V,, Hopcroft J, E,, Ullman J, D,, The design and analysis of computer algorithms, Addison-Wesley, Reading, Mass., 1976,

[6] Richard P. Brent, Fred G, Gustavson, David Y, Y, Yun, Fast solution of Toeplitz systems of equations and computation of Pade approximants, Journal of Algorithms 1, 1980, 259-295. ISSN 0196-6774. MR 82d:65033. URL: http://web,eomlab,ox,ae,uk/ouel/work/riehard,brent/pub/pub059,html,

[7] K. Thull and C. Yap. A unified approach to HGCD algorithms for polynomials and integers. Manuscript, 1990, http://cs.nyu.edu/cs/faculty/vap /allpapers.html/.

[8] И, С, Сергеев, Быстрые алгоритмы для элементарных операций с комплексными степенными рядами, Дискретная математика, 22, 1, 2010, 17-49

[9] Тыртышников К.К.. Метод скачков и аппроксимации Паде, Численные ме-

тоды, параллельные вычисления и информационные технологии, 2008, 277289, Imp: parallel.П1 info YYY 18.pdf

[10] Bernstein D. J,, Fast multiplication and its applications. In: Algorithmic Number Theory, Lattices, Number Fields, Curves and Cryptography (Mathematical Sciences Research Institute Publications), 44 (Buhler J, P, et al,, eds,), Cambridge, 2008, pp. 325-384,

НИИСИ PAH Поступило 17,10,2011