автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Символьные алгоритмы, связанные с задачами суммирования

На правах рукописи

Поляков Станислав Петрович

Символьные алгоритмы, связанные с задачами суммирования

05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

2 9 МАР Ш1

Москиа - 2012

005020625

005020625

Работа выполнена в Федеральном государстве}том бюджетном учреждении пауки Вычислительном центре им. A.A. Дородницына Российской академии наук.

Научный руководитель: доктор физико-математических наук,

профессор,

Абрамов Сергей Александрович Официальные оппоненты: Гердт Владимир Петрович

доктор физико-математических наук, профессор,

Объединенный институт ядерных исследований, начальник сектора Зобнин Алексей Игоревич кандидат физико-математических наук, Московский Государственный университет, доцент

Ведущая организация: Федеральное государственное бюджетное образо-

вательное учреждение высшего профессионального образования «Российский университет дружбы народов»

Защита состоится « I » _2012 г. в —1_ на заседании диссертационного

совета Д 002.017.02 при Федеральном государственном бюджетном учреждении науки Вычислительном центре им. A.A. Дородницына Российской академии наук, расположенном по адресу: 119333, г.Москва, улица Вавилова, дом 40.

С диссертацией можно ознакомиться в библиотеке Федерального государственного бюджетного учреждения науки Вычислительного центра им. A.A. Дородницына Российской академии наук.

Автореферат разослан «11» 2012 г.

Ученый секретарь

диссертационного совета Д 002.017.02, д. ф.-м. н., профессор

Общая характеристика работы

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

Первая глава посвящена частному случаю суммирования гипергеометрических последовательностей — суммированию рациональных функций. Задача неопределенного суммирования рациональных функций, впервые поставленная С.А. Абрамовым в 1971 г. в |1|, состоит в поиске для заданной рациональной функции f(x) рациональной функции д(х), удовлетворяющей

g(x+l)-g(x) = f(x).

Неопределенное суммирование является дискретным аналогом неопределенного интегрирования. Как и в случае интегрирования, не всякая рациональная функция имеет рациональную неопределенную сумму. Поэтому начиная с опубликованной в 1975 г. статьи С.А. Абрамова |2| изучается задача аддитивной декомпозиции рациональных функций — представления их в виде

f(x) = д{х + 1) - д(х) + г(х),

где г(х) — минимальная в некотором смысле рациональная функция, называемая остатком. Как правило, минимизируется степень знаменателя остатка — в такой постановке задача является аналогом задачи выделения рациональной части неопределенного интеграла рациональных функций, классические методы решения которой были предложены Остроградским [3] и Эрмитом

|4|-

Для задачи аддитивной декомпозиции разными авторами был предложен ряд алгоритмов решения, в частности, |2, 5-9|. Общей чертой этих алгоритмов является использование в том или ином виде дисперсии исходной функции f(x), т.е. максимального целого к такого, что знаменатели f(x) и f(x + k) имеют общие множители. Это позволяет избежать полной факторизации знаменателя J(x), заменив ее частичной факторизацией, основанной

на вычислении наибольших общих делителей. О.шако с появлением эффективных алгоритмом факторизации полиномов необходимость в этом отпала для многих нолей коэффициентов: так, согласно работе |10|. для полиномов из Q[x] основанный на полной факторизации алгоритм оказывается наиболее эффективным уже при вычислении дисперсии. Тем самым стала актуальной задача построения алгоритма, напрямую использующего полную факторизацию знаменателей при суммировании рациональных функций.

В отличие от интегрирования рациональных функций, в случае суммирования условие минимальности степени знаменателя остатка не обеспечивает единственности решения. В [llj Р. Пирасту была предложена задача аддитивной декомпозиции с дополнительной минимизацией степени знаменателя рациональной части неопределенной суммы д(х), пли просуммированной части. Предложешшая им в [7| модификация алгоритма [2| может за счет относительно небольших дополнительных вычислительных затрат значительно сократить просуммированную часть, однако не гарантирует ее минимальности.

Наличие у задачи аддитивной декомпозиции более чем одного решения позволяет предъявить дополнительные требования к остатку.

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

Алгоритм Цейлбергера [12|, которому посвящена вторая глава диссертации, является важным комныотерно-алгебрапческиы инструментом, применяемым для суммирования многомерных гипергеометрических последовательностей и автоматического доказательства тождеств. Для заданной гипергеометрической последовательности F(x,y) алгоритм строит рекурренцию вида

G(x,y+l)-G(x,y) = LrF{x.y), где Lx — свободный от у разностный оператор минимального порядка с по-

лшш.миальпимп коэффициентами, G{x,y) — гипгргсомотричоекая последовательность. Случаи однородной цейлбергеровской рекурренцни, т.е. случаи, когда последовательность F(x, у) обращается оператором LI: н нуль, заслуживает внимания как с теоретической, так и с практической точки зрения. К этому случаю неприменимо доказательство корректности алгоритма Цейл-бергера, предложенное в [12| и впоследствии воспроизведенное в ряде монографии и учебников (например, |13, 14|). Кроме того, однородный случай был исследован в работе [15|, поскольку он вызывал ошибки в работе реализации алгоритма в ряде версии системы компьютерной алгебры Maple |16]. Исходное предположение авторов о некорректности работы самого алгоритма в однородном случае ошибочно, однако некоторые их результаты представляют интерес, поскольку предложенный ими алгоритм в однородных случаях может оказываться намного эффективнее алгоритма Цейлбергера.

Во второй главе диссертации предлагается доказательство корректности алгоритма Цейлбергера в однородном случае. Также демонстрируется, что цейлбергеровская рекурреиция может быть однородной при любом порядке цейлбергеровского оператора, и предлагается алгоритм построения оператора минимального порядка, обращающего гинергеометрическую последовательность в нуль, .г ■

Цель диссертационной работы. Целыо настоящей работы является разработка компыотерпо-алгебраических (символьных) алгоритмов суммирования рациональных функций и многомерных гииергеометрических последовательностей.

Научная новизна.

В диссертационной работе получен ряд результатов, обладающих научной новизной:

• Предложен алгоритм а;1днтавной декомпозиции рациональных функций, основанный па полной факторизации знаменателей. Построено полное описание семейства решений задачи аддитивной декомпозиции. Предложены два алгоритма аддитивной декомпозиции с дополнительной минимизацией степени знаменателя просуммированной части, первый из которых не использует полную факторизацию, а второй основан на ней. Найдена оценка вычислительной сложности основанных на полной фак-

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

• Доказана корректность алгоритма Цейлбергера в случае однородной цейлбергеровской рекурренции; тем самым устранен пробел в доказательстве корректности алгоритма. Показано, что цейлбергеровская ре-курренция может быть однородной при любом порядке цейлбергеров-ского оператора. Предложен алгоритм построения аннулирующего оператора минимального порядка для двумерных гипергеометрических последовательностей. Предложена модификация алгоритма Цейлбергера, в однородном случае использующая алгоритм построения аннулирующего оператора минимального порядка.

• В системе компьютерной алгебры Maple [16| реализована процедура аддитивной декомпозиции рациональных функций с минимизацией степени знаменателя остатка и возможностью дополнительной минимизации степени знаменателя просуммированной части либо степени числителя остатка; пользователю предоставлена возможность выбора между алгоритмами, основанными на полной факторизации знаменателя входной функции (используемыми но умолчанию) и алгоритмами, избегающими ее. Реализованы процедура построения аннулирующего оператора минимального порядка для гипергеометрических последовательностей и модифицированный алгоритм Цейлбергера, использующий построение аннулирующих операторов в однородном случае. Проведено экспериментальное сравнение основанного на полной факторизации алгоритма аддитивной декомпозиции с алгоритмами ¡2, 5. 9], а также алгоритма Цейлбергера с модифицированной версией в однородном случае.

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

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

Реализации алгоритмов неопределенного суммирования рациональных функций встроена в систему компьютерной алгебры Maple [16] и доступна пользователям как напрямую, так и в качестве составной части общего алгоритма вычисления сумм. Реализация алгоритма поиска минимального аннулирующего оператора включена в реализацию алгоритма Ценлбергера и может использоваться для эффективного поиска однородных рекурренций.

На защиту выносятся следующие основные результаты и положения:

1. Разработан алгоритм аддитивной декомпозиции рациональных функций с минимизацией степени знаменателя остатка, основанный на полной факторизации знаменателя, а также модификация алгоритма, дополнительно минимизирующая степень знаменателя просуммированной части. Для обеих модификаций доказана оценка вычислительной сложности. Разработан алгоритм аддитивной декомпозиции с дополнительной минимизацией просуммированной части, не использующий полную факторизацию. Разработан алгоритм аддитивной декомпозиции-рациональных функций с дополнительной минимизацией степени числителя остатка.

2. Предложено полное (включающее однородный случай) обоснование алгоритма Цейлбергера определенного суммирования многомерных гинер-геометрических последовательностей. Разработан алгоритм поиска аннулирующего оператора минимального порядка для двумерных гииер-геометрнческих последовательностей.

3. В системе компьютерной алгебры .Maple |16| созданы процедуры, реализующие основанные на полной факторизации алгоритмы аддитивной декомпозиции рациональных функций, а также алгоритм поиска аннулирующего оператора минимального порядка для гипергеометрп-ческих последовательностей. Выполнен ряд компьютерных эксперимен-

тон, продемонстрировавших практическую ценность предложенных алгоритмом.

Апробация работы. На разных этапах работы основные результаты но теме диссертации были представлены на следующих конференциях и семинарах:

• Семинар МГУ "Компьютерная алгебра", Москва, 2005, 2009 гг.

• Международный семинар по компьютерной алгебре и информатике (посвященный 30-летию ЛВМ МГУ), Москва, 2005 г.

• Совместное заседание семинаров ВМК МГУ, НИИЯФ МГУ и Лаборатории информационных технологий ОИЯИ, Дубна, 2006 г.

• ХЫП всероссийская научная конференция по проблемам математики, информатики, физики и химии, Москва, 2007 г.

Публикации. Материалы диссертации опубликованы в пяти печатных работах, из них четыре публикации в рецензируемых журналах из перечня ВАК (А1, А2, АЗ, А4] и одна публикация в сборнике тезисов докладов конференции [А5|.

Личный вклад автора. Результаты получены автором самостоятельно иод руководством д.ф.-м.н., профессора С.А. Абрамова.

Структура и объем диссертации. Диссертационная работа состоит из введения, трех глав, заключения и списка литературы. Общий объем работы составляет 71 страницу. Список литературы содержит 39 наименований.

Содержание работы

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

В первой главе рассматривается задача неопределенного суммирования (аддитивной декомпозиции) рациональных функций: для /(х) € А'(х),

где К — поле характеристики 0. найти пару рациональных функций д{х), г(х) такую, что

f(x) = g{x+l)-g(x) + r{x)

и степень знаменателя г(х) минимальна (задача 1). Функции д(х) и г(х) называются соответственно просуммированной частью f(x) и остатком.

При помощи удовлетворяющих условиям задачи 1 д(х), г(х) можно упростить вычисление определенных сумм: если f(x), д{х), г(х) не имеют полюсов при х = v, v + 1,..., w и, кроме того, д{х) не имеет полюса в w + 1, то справедлива формула

W W

Y, /М = 9(w + 1) - g{v) + Y, r(x)-

x—v

Задача 1 впервые сформулирована в [2]. Известен ряд алгоритмов ее решения, в частности, [2, 5-9|.

Для простоты предполагается, что f(x) — правильная дробь, и среди решений задачи 1 рассматриваются только те, в которых д{х) и г(х) — правильные дроби.

В отличие от аналогичной задачи выделения рациональной части неопределенного интеграла рациональной функции, задача 1 при ненулевом остатке имеет бесконечно много решеинй, причем степень знаменателя просуммированной части может быть сколь угодно велика. Поэтому представляет интерес задача 2: найти решение задачи 1 с минимальной степенью знаменателя просуммированной части.

Задача 2 сформулирована в |7, 11]. Предложенный в [7] алгоритм во многих случаях строит ее решение, однако не гарантирует минимальности степени просуммированной части.

Также сформулирована задача 3: найти решение задачи 1 с минимальной степенью числителя остатка. Эта задача является новой.

В разделе 1.2 описан ряд подходов к решению задачи 1. Предложен подход, использующий представление функции f(x) в виде суммы дробей со знаменателями вида где qt(x) — неприводимые полиномы и сч — целые числа. Подход назван прямым, поскольку он напрямую использует полную факторизацию знаменателя f{x).

Также дано краткое описание подходов, лежащих и основе ряда известных алгоритмов решения задачи 1. Рекурсивный подход (использован в алгоритмах [2, 7|) состоит в пошаговом отделении от функции суммируемых слагаемых. В линейно-алгебраическом подходе (алгоритмы [5, С, 8|) сначала строятся знаменатели искомых функций д{х), г{х), после чего коэффициенты числителей могут быть получены пз системы линейных уравнений. Алгоритм [9] использует подход, близкий к прямому: для построения д{х), г(х) используется представление /(:г) в виде суммы слагаемых с попарно взаимно простыми знаменателями, свободными от сдвигов (т.е. gcd(<7j(.r),gi(x-t-A')) = 1 для всех целых к > 0). Для построения соответствующего разложения знаменателя f(x) полной факторизации не требуется.

Общей чертой существующих алгоритмов решения задачи 1 является использование в том или ином виде дисперсии исходной функции }{х), т.е. максимального целого А" такого, что знаменатели /(.г) и f(x+k} имеют общие множители. Это позволяет избежать полной факторизации знаменателя f(x), заменяя ее разложением, основанным на вычислении наибольших общих делителей. Однако с разработкой эффективных алгоритмов подпой факторизации полиномов (например, '17-19! для рациональных функций) появились данные за то, что это стало ненужным: так, для полиномов с рациональными коэффициентами статья [10| демонстрирует, что собственно дисперсию наиболее эффективно вычислять с: использованием полной факторизации рассматриваемого полинома. В системе компьютерной алгебры Maple [16| такой алгоритм вычисления дисперсии применяется уже независимо от поля коэффициентов. Поэтому представляет интерес разработка алгоритма неопределенного суммирования рациональных функции в рамках прямого подхода: если полная факторизация знаменателя / при решении задачи 1 вычисляется в любом случае, то использование ее результатов напрямую может дать выигрыш в эффективности.

Введено понятие левостороннего алгоритма решения задачи 1: алгоритм называется левосторонним, если для любой f(x) знаменатель найденного остака в освобожденном от квадратов виде делит знаменатель /. Таким свойством обладают алгоритмы [2|, |9|. а также предлагаемый вариант прямого алгоритма.

В разделе 1.3 приведено подробное изложение прямого алгоритма неопределенной) суммирования рациональных функций (алгоритм 1.1). Алгоритм находит полную факторизацию знаменателя /(х), затем представляет ее в виде суммы

,(х) = ЪМ , ЪМ

п) СЗоЫ^СЭЛхУ где щ^у имее т пулевую дисперсию и gcd(Q()(x), (х+к)) = 1 для всех целых к. После этого строится разложение на простейшие дроби, из которого вычисляются д(.с), г{х).

Доказана

Теорема 1.1. Найденные алгоритмом 1.1 д{х), г(х) являются решением задачи 1 для ¡{х). Без учета затрат на факторизацию знаменателя /(х) для выполнения алгоритма достаточно 0(т2) операций над элементами поля, где т степень знаменателя /(х).

В разделе 1.4 построено полное описание множества решений задачи 1: Теорема 1.2. Пусть д(х),г(х) — решение задачи 1 для некоторой /(х),

ф.) = г(1 > + ... + гМ=Л. + ...+ А,

41 Чп

где ..., неприводимые полиномы, сц,...,а„ натуральные числа.

Тогда пара правильных дробей д'(х),г'(х) будет решением задачи 1 для }{х) если и только если

п тах(- 1,А:,-1)

э'М = 9к,.....к„ = д{х) - г(г}(х + Д

¡=1 ;=шт(0,*,\)

г'(х) = П,.....= г{1)(х + Ал) + ■ - • + г(">(х + к„),

где А'1,..., к„ целые числа.

В разделе 1.5 описан модифицированный алгоритм [2|, предложенный в (7| для решения задачи 2. Приведены условия, при выполнении которых, согласно |11|, алгоритм гарантированно строит решение задачи 2. Приведен

пример не удовлетворяющей этим условиям функции, для которой в найденном алгоритмом [7| решении задачи 1 степень знаменателя просуммированной части не минимальна.

В разделе 1.6 предложен алгоритм 1.2, являющийся модификацией алгоритма 1.1. Доказана

Теорема 1.3. Прямой алгоритм суммирования с минимизацией просуммированной части (алгоритм 1.2} строит решение задачи 2. Без учета затрат на факторизацию знаменателя }{х) для выполнения алгоритма достаточно 0{т2) операций над элементами поля, где т - степень знаменателя f{x).

В разделе 1.7 предлагается алгоритм 1.3 решения задачи 2, не использующий полную факторизацию полиномов. Алгоритм использует решение задачи 1, построенное каким-либо левосторонним алгоритмом (например, [2|, (9|), а также дисперсию исходной функции, вычисленную при решении задачи 1. При помощи вычисления наибольших общих делителей алгоритм 1.3 строит предварительное разложение остатка на компоненты, которое затем уточняется в ходе поиска сдвигов компонент остатка, минимизирующих степень знаменателя просуммированной части. Для уточнения разложения используется "расщепление" компонент посредством вычисления наибольших общих делителей, поэтому алгоритм 1.3 назван расщепляющим.

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

В разделе 1.8 рассматривается задача 3. Она сведена к задаче поиска целочисленных решений систем алгебраических уравнений с коэффициентами из К. Предложен алгоритм (алгоритм 1.4), использующий для решения таких систем '"оракул" — алгоритм, в некоторых случаях находящий какое-то решение системы. Для построения систем используется полная факторизация знаменателя остатка в каком-то решении задачи 1, однако само решение задачи 1 при этом может быть получено с помощью любого алгоритма. Доказано, что алгоритм 1.4 строит решение с минимальной степенью числителя остатка, если и решении задачи 1 знаменатель остатка содержит не более

трех различных неприводимых множителей.

Результаты первой главы опубликованы в работах [А1, A3, А4|.

Во второй главе рассматривается известный алгоритм Цейлбергера ¡12|, применяемый для суммирования многомерных пшергеометрических ио-следователыкхггеП и доказательства комбинаторных тождеств, в случае однородных цейлбергеровских рекурренций.

Ненулевая последовательность F{x) называется гипергеометрической, если для ее элементов выполняется

p{x)F(x) = q(x)F(x+l),

где p(x),q(x) € К[х], p(x),q{x) ф 0, gcd(p{x),q(x)) = 1.

Операторы Es и Еу, под действием которых двумерная последовательность F(x,y) переходит в F(x+l,y) и F(x, у+1) соответственно, называются операторами сдвига но х и но у.

Двумерная ненулевая последовательность F(x, у) называется гипергеометрической, если найдутся две нары взаимно простых ненулевых полиномов Рх[х,у), qx(x, у) и ру{х,у), qy{x,y) такие, что

Рх(х, y)F{x, у) = qx(x, y)ExF(x, у),

Ру(х, y)F{x, у) = qy{x, y)EyF(x, у).

Отношения и называются соответственно х-сертификатом и

у-сертификатом F(x, у).

Для гипергеометрической последовательности Т(х,у) алгоритм Цейлбергера [12] строит пшергеометрпческую последовательность

в(х,у)=ф(т,у)Т(х,у), ф{х,у) 6 К(х,у), и разностный оператор

L = ad{x)Edx + ... + ах{х)Ех + а0(х) со свободными от у коэффициентами n,i{x),..., ап(х) £ К[х\, для которых С(.т, у + 1) - G(x, у) = LT(x, у), 13

если такие G(x, у)-, L существуют. Алгоритм обеспечивает минимальность порядка оператора L. Оператор L называется цейлбергеровским оператором для Т(х,у), соответствующая рекурренцня — цейлбергеровской рекурренци-ей.

Во второй главе рассматриваются однородные рекуррепции вида G{x, у+ 1) — G{x,y) = LT{x,y), т.е. такие, в которых оператор L обращает Т(х,у) в нуль. К однородному случаю неприменимо доказательство корректности алгоритма Цейлбергера, предложенное в |12| и впоследствии воспроизведенное в ряде монографий и учебников (например, [13, 14]). Также известны проблемы с реализацией алгоритма Цейлбергера в однородном случае в системе Maple [16); при этом поиск операторов, обращающих в нуль гипергеометрические последовательности, для которых в реализации алгоритма возникали ошибки, может быть осуществлен с помощью эффективного алгоритма [15|.

В разделе 2.2 описана работа алгоритма Цейлбергера. Доказана корректность алгоритма в однородном случае. Описана модификация алгоритма Цейлбергера, предложенная в |15| для исправления реализации алгоритма.

В разделе 2.3 исследуются минимальные аннулирующие операторы, т.е. операторы вида L = a(i{x)E^ 4- ... 4- ai^E* + ао(х) со свободными от у коэффициентами a(i{x),... ,ао(х) € А'[д-], обращающие гипергеометрические последовательности в нуль и имеющие минимальный порядок.

Доказано, что для любого целого d > 0 найдется гипергеометрическая последовательность, цейлбергеровский оператор которой является аннулирующим и имеет порядок d. Приведен пример таких последовательностей.

Согласно [15|, последовательность Т(х, у) имеет аннулирующий оператор тогда и только тогда, когда ее х-сертификат может быть представлен в виде

САП,,^;

р(х,у)

Кроме того, в этой работе описано множество последовательностей S, для которого Мар1е-реализация алгоритма Цейлбергера работала некорректно. Для последовательностей из S цейлбергеровская рекурренция заведомо однородна. В [15| для таких последовательностей авторами предложен алгоритм поиска цейлбергеровского оператора, отличный от алгоритма Цейлбергера (и

более эффективный для этих последовательностей).

В разделе 2.3 предлагается способ вычисления порядка г минимального аннулирующего оператора: если Ст(Т(х,у)) = ,

I

то порядок г равен размерности Сц(со(х),... , с;(:с)), т.е. линейной оболочки с0(а;),...,с/(х).

Предложен алгоритм вычисления минимального аннулирующего оператора (алгоритм 2.1). Задача сводится к поиску нетривиального полиномиального решения однородной системы г линейных уравнений с полиномиальными коэффициентами и г + 1 неизвестной.

Предложена модификация алгоритма Цейлбергера, использующая алгоритм вычисления минимального аннулирующего оператора (алгоритм 2.2). Порядок минимального аннулирующего оператора вычисляется заранее, и если алгоритм не находит цейлбергеровских операторов более низкого порядка, то вычисляется минимальный аннулирующий оператор. Это позволяет получить выигрыш в эффективности для всех последовательностей, имеющих однородные цейлбергеровские рекурренции, а не только для последовательностей из 5.

Также можно использовать алгоритм поиска минимальных аннулирующих операторов в качестве "последней надежды'" в случаях, когда алгоритм Цейлбергера не находит рекурренции высоких порядков и дальнейший поиск, например, превосходит возможности вычислительной техника.

Результаты второй главы опубликованы в работе [А2].

В третьей главе описаны реализации предложенных алгоритмов, выполненные в системе Мар1е [1С], и приведены результаты их экспериментального сравнения.

Реализации алгоритмов решения задач неопределенного суммирования рациональных функций (задачи 1-3) доступны через общий интерфейс — процедуру ЛаНопяШиш. Обязательные аргументы процедуры — рациональная функция / 6 К(х) и имя переменной х, возвращается пара рациональных функции, являющаяся решением задачи 1 для /(х). Необязательные аргумен-

ты позволяют пользователю выбирать между алгоритмами решения задачи 1 (помимо прямого алгоритма 1.1 доступны линейно-алгебраический алгоритм [5|, рекурсивный алгоритм [2\ и алгоритм вСЭЕ |9|) и запрещать или разрешать факторизацию знаменателя /(х) при вычислении ее дисперсии. Есть возможность потребовать использовать модификацию (7| либо дополнительную минимизацию степени просуммированной части (в зависимости от используемого алгоритма решения задачи 1 применяется прямой алгоритм 1.2 или расщепляющий алгоритм 1.3) или степени числителя остатка. При использовании прямого алгоритма имеется возможность выбирать меж;1у представлениями результата: по умолчанию просуммированная часть и остаток представляются в том виде, в котором они постороены алгоритмом, и можно потребовать приведения их к виду пары дробей со взаимно простыми числителем и знаменателем.

Алгоритм 2.1 построения минимального аннулирующего оператора реализован в процедуре Мнпта1АцшЫ1а!;ог. Модифицированный алгоритм Цейл-бергера 2.2, использующий поиск аннулирующих операторов в однородном случае, реализован как часть процедуры 2еПЬе^ег, применяющей алгоритм Цейлбергера.

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

Разница в затратах на выполнение алгоритма 1.1, модификации |7| этого алгоритма и алгоритма 1.2 оказалось незначительной, т.е. для прямого алгоритма затраты на дополнительную минимизацию просуммированной части невелики. Расщепляющий алгоритм минимизации просуммированной части требует заметных затрат для небольших значениях дисперсии исходной функции, при больших значениях дисперсии затраты па его применение могут намного превосходить затраты па решение задачи 1.

Сравнение, реализаций алгоритма Цейдбергера и модифицированной версии 2.2 для однородных случаев показывает, что алгоритм 2.2 может быть во много раз эффективнее в случаях, когда об однородности цейлбергеровской рекурренцин известно априорно. В случаях, когда априорно об -этом не известно, он оказывается эффективнее в 2-6 раз. При этом для рациональных функций алгоритм |20| прямого вычисления цейлбергеровского оператора может оказаться эффективнее, однако его время работы сильно зависит от множителей, не влияющих существенно на время работы алгоритма Цейлбергера и алгоритма построения минимального аннулирующего оператора.

В Заключении сформулированы основные результаты диссертационной работы.

Список публикаций

А1. Поляков С. П. Символьная аддитивная декомпозиция рациональных функций / Программирование. 2005. № 2. С. 15-21.

А2. Polyakov S. P. Он homogeneous Zeilberger recurrences // Advances in Applied Mathematics. 2008. Vol. 40, no. 1. Pp. 1-7.

A3. Поляков С. П. Неопределенное суммирование рациональных функций с дополнительной минимизацией просуммированной части /'/' Программирование. 2008. .V- 2. С. 48-53.

А4. Поляков С. П. Неопределенное суммирование рациональных функции с факторизацией знаменателей /; Программирование. 2011. Л'-°4. С. 23 27.

А5. Поляков С. П. Неопределенное суммирование рациональных функций с дополнительной минимизацией просуммированной части // XLIII всероссийская конференция по проблемам математики, информатики, физики и химии: Тезисы докладов. Секции физики. Москва: РУДН. 2007. С. 30.

Цитированная литература

1. Абрамов С. А. О суммировании рациональных функций // Журнал вычислительной математики и математической физики. 1971. Т. 11. С. 1071-1075.

2. Абрамов С. А. Рациональная компонента решения линейного рекуррентного соотношения первого порядка с рациональной правой частью // Журнал вычислительной математики и математической физики. 1975. Т. 15. С. 1035-1039.

3. Ostrogradsky M. De l'intégration des fractions rationnelles // Bull, de la Classe Physico-Mathématique de l'Académie Impériale des Sciences de Saint-Petersburg. 1845. Vol. IV. Pp. 145 -167, 286 -300.

4. Hermite Ch. Sur l'intégration des fractions rationnelles / ' Annales de Mathématiques, 2ème série. 1872. Vol. 11. Pp. 145-148.

5. Abramov S. A. Indefinite sums of rational functions // Proceedings of IS-SAC'95. 1995. Pp. 303-308.

6. Paule P. Greatest factorial factorization and symbolic summation // Journal of Symbolic Computation. 1995. Vol. 20. Pp. 235-268.

7. Pirastu R. Algorithms for indefinite summation of rational functions in Maple / The Maple Technical Newsletter. 1995. Vol. 2, no. 1. Pp. 1-12.

8. Pirastu R., Strolil V. Rational summation and Gosper-Petkovsek representation / Journal of Symbolic Computation. 1995. Vol. 20. Pp. G17-G35.

9. Gerhard .].. Gie.sbrecht M., Storjohann A., Zima E. V. Shiftless decomposition and polynomial-time rational summation // Proceedings of ISSAC'03. 2003. Pp. 119-12G.

10. Man Y.-K., Wright F. J. Fast polynomial dispersion computation and its application to indefinite summation // Proceedings of ISSAC'94. 1991 Pp. 175-180.

11. Pirastn R. A nolo on the minimality problem in indefinite summat ion of rational functions // Actes du Seminaire Lotharingien de Combinatoire, 31 session, Saint-Nabor, Ottrot, October 1993, Publications de 1'I.R.M.A. Vol. 21. 1994. Pp. 95-101.

12. Zeilberger D. The method of creative telescoping // Journal of Symbolic Computation. 1991. Vol. 11. Pp. 195-204.

13. Pctkovsck M., Wilf H. S., Zeilberger D. A-B. Natick, MA: A K Peters, 199G.

14. Graham R. L., Knuth D. E., Patashnik O. Concrete Mathematics. Reading, MA: Addison Wesley, 1989.

15. Le H. Q., Li Z. On a set of hyperexponential elements and the fast versions of Zeilberger's algorithm: Preprint 23: Key Laboratory of Mathematics-Mechanization, 2004. URL: http://www.mmrc.iss.ac.cn/pub/mm23.pdf/LeLi. pdf.

16. Maple online help. URL: http://www.maplesoft.com/support/help/.

17. Lenstra A. K., Lenstra H. W., Lovasz L. Factoring polynomials with rational coefficients // Mathcmatische Aimalen. 1982. Vol. 261, no. 4. Pp. 515-534.

18. Schonhage A. Factorization of univariate integer polynomials by diophantiue approximation and by an improved basis reduction algorithm // Proceedings of ICALP '84. Vol. 172 of Lecture Notes in Computer Science. Springer, 1984. Pp. 436-447.

19. van Hoeij M. Factoring polynomials and the knapsack problem // Journal of Number Theory. 1975. Vol. 95. Pp. 167-189.

20. Le H. Q. A direct algorithm to construct the minimal Z-pairs for rational functions / Advances in Applied Mathematics. 2003. Vol. 30, no. 1-2. Pp. 137-159.

Подписано в печать: 27.02.12

Объем: 1,5 усл.п.л. Тираж: 100 экз. Заказ № 76 Отпечатано в типографии «Реглет» 105005, г. Москва, ул. Бауманская д.ЗЗ (495) 979-96-99; wu-w.reglet.ru

61 12-1/1017

Федеральное государственное бюджетное учреждение науки

Вычислительный центр им. A.A. Дородницына Российской академии наук

На правах рукописи

Поляков Станислав Петрович

Символьные алгоритмы, связанные с задачами

суммирования

05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

ДИССЕРТАЦИЯ на соискание ученой степени кандидата физико-математических наук

Научный руководитель д. ф.-м. н., проф. Абрамов С.А.

Москва - 2012

Содержание

Введение ............................... ... 4

Глава 1. Неопределенное суммирование рациональных функций с дополнительной минимизацией...................11

1.1. Варианты постановки задачи................:• • • • И

1.2. Алгоритмы неопределенного суммирования ...............16

1.3. Прямой алгоритм суммирования с разложением на простейшие дроби ..............................21

1.4. Множество решений задачи неопределенного суммирования . . 24

1.5. Подходы к минимизации просуммированной части.......26

1.6. Прямой алгоритм с минимизацией просуммированной части . . 28

1.7. Расщепляющий алгоритм минимизации степени знаменателя просуммированной части..........................31

1.8. Минимизация степени числителя остатка................37

Глава 2. Однородные цейлбергеровские рекурренции ...... 43

2.1. Предварительные сведения.................;. . . . 43

2.2. Алгоритм Цейлбергера в однородном случае..............47

2.3. Минимальные аннулирующие операторы ............50

Глава 3. Реализация и экспериментальное сравнение алгоритмов .....................................58

3.1. Реализация..................................58

3.2. Экспериментальное сравнение алгоритмов........: . . . . 60

Заключение...................................67

Литература.............................. . . . 68

Введение

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

Первая глава посвящена частному случаю суммирования гипергеометрических последовательностей — суммированию рациональных функций. Задача неопределенного суммирования рациональных функций, впервые поставленная С.А. Абрамовым в 1971 г. в [1], состоит в поиске для заданной рациональной функции /(ж) рациональной функции д(х), удовлетворяющей

д(х + 1)-д(х)=/{х).

Неопределенное суммирование является дискретным аналогом неопределенного интегрирования. Как и в случае интегрирования, не всякая рациональная функция имеет рациональную неопределенную сумму. Поэтому начиная с опубликованной в 1975 г. статьи С.А. Абрамова [2] изучается задача аддитивной декомпозиции рациональных функций — представления их в виде

¡(х) = д(х + 1) - д{х) + г(х),

где г(х) — минимальная в некотором смысле рациональная функция, называемая остатком. Как правило, минимизируется степень знаменателя остатка — в такой постановке задача является аналогом задачи выделения рациональной части неопределенного интеграла рациональных функций, классические методы решения которой были предложены Остроградским [3] и Эрмитом

М-

Для задачи аддитивной декомпозиции разными авторами был предложен ряд алгоритмов решения, в частности, [2, 5-9]. Общей чертой этих ал-

горитмов является использование в том или ином виде дисперсии исходной функции /(ж), т.е. максимального целого к такого, что знаменатели /(х) и /(ж + к) имеют общие множители. Это позволяет избежать полной факторизации знаменателя /(ж), заменив ее частичной факторизацией, основанной на вычислении наибольших общих делителей. Однако с появлением эффективных алгоритмов факторизации полиномов необходимость в этом отпала для многих полей коэффициентов: так, согласно работе [10], для полиномов из (^[ж] основанный на полной факторизации алгоритм оказывается наиболее эффективным уже при вычислении дисперсии. Тем самым стала актуальной задача построения алгоритма, напрямую использующего полную факторизацию знаменателей при суммировании рациональных функций.

В отличие от интегрирования рациональных функций, в случае суммирования условие минимальности степени знаменателя остатка не обеспечивает единственности решения. В [11] Р. Пирасту была предложена задача аддитивной декомпозиции с дополнительной минимизацией степени знаменателя рациональной части неопределенной суммы д(х), или просуммированной части. Предложеннная им в [7] модификация алгоритма [2] может за счет относительно небольших дополнительных вычислительных затрат значительно сократить просуммированную часть, однако не гарантирует ее минимальности.

Наличие у задачи аддитивной декомпозиции более чем одного решения позволяет предъявить дополнительные требования к остатку.

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

Алгоритм Цейлбергера [12], которому посвящена вторая глава диссертации, является важным компьютерно-алгебраическим инструментом, применяемым для суммирования многомерных гипергеометрических последовательностей и автоматического доказательства тождеств. Для заданной гипергеометрической последовательности F(x,y) алгоритм строит рекурренцию вида

G{x, у + 1) - G(x, у) = LxF{x, у),

где Ьх — свободный от у разностный оператор минимального порядка с полиномиальными коэффициентами, G(x, у) — гипергеометрическая последовательность. Случай однородной цейлбергеровской рекурренции, т.е. случай, когда последовательность F(x,y) обращается оператором Lx в нуль, заслуживает внимания как с теоретической, так и с практической точки зрения. К этому случаю неприменимо доказательство корректности алгоритма Цейлбергера, предложенное в [12] и впоследствии воспроизведенное в ряде монографий и учебников (например, [13, 14]). Кроме того, однородный случай был исследован в работе [15], поскольку он вызывал ошибки в работе реализации алгоритма в ряде версий системы компьютерной алгебры Maple [16]. Исходное предположение авторов о некорректности работы самого алгоритма в однородном случае ошибочно, однако некоторые их результаты представляют интерес, поскольку предложенный ими алгоритм в однородных случаях может оказываться намного эффективнее алгоритма Цейлбергера.

Во второй главе диссертации предлагается доказательство корректности алгоритма Цейлбергера в однородном случае. Также демонстрируется, что цейлбергеровская рекурренция может быть однородной при любом порядке цейлбергеровского оператора, и предлагается алгоритм построения оператора минимального порядка, обращающего гипергеометрическую последовательность в нуль.

Цель диссертационной работы. Целью настоящей работы является разработка компьютерно-алгебраических (символьных) алгоритмов суммирования рациональных функций и многомерных гипергеометрических последовательностей.

Научная новизна.

В диссертационной работе получен ряд результатов, обладающих научной новизной:

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

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

• Доказана корректность алгоритма Цейлбергера в случае однородной цейлбергеровской рекурренции; тем самым устранен пробел в доказательстве корректности алгоритма. Показано, что цейлбергеровская ре-курренция может быть однородной при любом порядке цейлбергеров-ского оператора. Предложен алгоритм построения аннулирующего оператора минимального порядка для двумерных гипергеометрических последовательностей. Предложена модификация алгоритма Цейлбергера, в однородном случае использующая алгоритм построения аннулирующего оператора минимального порядка.

• В системе компьютерной алгебры Maple [16] реализована процедура аддитивной декомпозиции рациональных функций с минимизацией степени знаменателя остатка и возможностью дополнительной минимизации степени знаменателя просуммированной части либо степени числителя остатка; пользователю предоставлена возможность выбора между алгоритмами, основанными на полной факторизации знаменателя входной функции (используемыми по умолчанию) и алгоритмами, избегающими ее. Реализованы процедура построения аннулирующего оператора минимального порядка для гипергеометрических последовательностей и модифицированный алгоритм Цейлбергера, использующий построение аннулирующих операторов в однородном случае. Проведено экспериментальное сравнение основанного на полной факторизации алгоритма аддитивной декомпозиции с алгоритмами [2, 5, 9], а также алгоритма Цейлбергера с модифицированной версией в однородном случае.

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

Реализация алгоритмов неопределенного суммирования рациональных функций встроена в систему компьютерной алгебры Maple [16] и доступна пользователям как напрямую, так и в качестве составной части общего алгоритма вычисления сумм. Реализация алгоритма поиска минимального аннулирующего оператора включена в реализацию алгоритма Цейлбергера и может использоваться для эффективного поиска однородных рекурренций.

На защиту выносятся следующие основные результаты и положения:

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

2. Предложено полное (включающее однородный случай) обоснование алгоритма Цейлбергера определенного суммирования многомерных гипергеометрических последовательностей. Разработан алгоритм поиска аннулирующего оператора минимального порядка для двумерных гипергеометрических последовательностей.

3. В системе компьютерной алгебры Maple [16] созданы процедуры, реализующие основанные на полной факторизации алгоритмы аддитивной декомпозиции рациональных функций, а также алгоритм поиска аннулирующего оператора минимального порядка для гипергеометрических последовательностей. Выполнен ряд компьютерных экспериментов, продемонстрировавших практическую ценность предложенных алгоритмов.

Апробация работы. На разных этапах работы основные результаты

по теме диссертации были представлены на следующих конференциях и семинарах:

• Семинар МГУ "Компьютерная алгебра", Москва, 2005, 2009 гг.

• Международный семинар по компьютерной алгебре и информатике (посвященный 30-летию ЛВМ МГУ), Москва, 2005 г.

• Совместное заседание семинаров ВМК МГУ, НИИЯФ МГУ и Лаборатории информационных технологий ОИЯИ, Дубна, 2006 г.

• ХЬШ всероссийская научная конференция по проблемам математики, информатики, физики и химии, Москва, 2007 г.

Публикации. Материалы диссертации опубликованы в пяти печатных работах, из них четыре публикации в рецензируемых журналах из перечня ВАК [17-20] и одна публикация в сборнике тезисов докладов конференции [21].

Личный вклад автора. Результаты получены автором самостоятельно под руководством д.ф.-м.н., профессора С.А. Абрамова.

Структура и объем диссертации. Диссертационная работа состоит из введения, трех глав, заключения и списка литературы. Общий объем работы составляет 71 страницу. Список литературы содержит 39 наименований.

Глава 1

Неопределенное суммирование рациональных функций с дополнительной минимизацией

1.1. Варианты постановки задачи

Пусть К — поле характеристики 0. Рациональную функцию f(x) Е К(х) будем называть рационально суммируемой или просто суммируемой, если найдется рациональная функция д(х), для которой

g(x + l)-g{x) = f{x). (1.1)

Функция д{х) называется неопределенной суммой f(x).

Полиномы р(х) и q(x) называются соответственно числителем и знаменателем рациональной функции /(ж), если они взаимно просты, q(x) имеет единичный старший коэффициент и

fix) = ^

п) 9W

Знаменатель /(ж) будем обозначать den(/(a:)), числитель — num(|/(х)).

Неопределенная сумма может использоваться для вычисления определенных сумм: если знаменатели f(x) и ^(ж) отличны от нуля при ж = v,v + 1,..., ги и, кроме того, den(g(u> + 1)) ф 0, то из (1.1) следует справедливость дискретной формулы Ньютона-Лейбница

W

Yf(x)=g(w + l)-g(v). (1.2)

x=v

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

— выяснить, является ли функция суммируемой, и найти ее неопределенную сумму в этом случае (Абрамов [1], Госпер [22]);

— найти решение (1.1) на множестве J7, где J7 представляет собой некоторое расширение К(х), содержащее иррациональные решения (1.1) для всех несуммируемых f(x) £ К{х) (Монк [23], Kapp [24, 25]);

— выделить максимальную в некотором смысле рациональную суммируемую часть исходной функции и найти ее сумму (Абрамов [2, 5], Пауле [6])-

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

Задача 1. Для данной рациональной функции f(x) найти пару рациональных функций д(х), г(х) таких, что для них выполняется

g(x+l)-g(x) + r(x) = f(x) (1.3)

и г(х) имеет знаменатель минимальной степени.

Функции д{х) и г(х) будем называть соответственно просуммированной частью f(x) и остатком.

Вместо формулы (1.2) для удовлетворяющих условиям задачи 1 д(х), г(х) будет справедлива формула

W W

^2f(x) = g(w + l)-g(v) + J2r(x). (1.4)

x—v x=v

Замечание 1. Нетрудно убедиться, что все полиномы суммируемы. Если f(x) — неправильная рациональная дробь, т.е.

degnum(/(ж)) > degden(/(ж)),

то ее легко представить в виде суммы полинома и правильной рациональной дроби и суммировать их независимо, начиная с полинома. Далее будем полагать f(x) правильной дробью и рассматривать только такие решения задачи 1, в которых д{х) и г(х) также являются правильными рациональными дробями.

Задача аддитивной декомпозиции с минимизацией степени знаменателя остатка (задача 1) рассмотрена в ряде работ, например, [2, 5, 6, 8], известно несколько алгоритмов решения [2, 5-9]. Краткое описание подходов к решению задачи 1, лежащих в основе этих алгоритмов, дано в разделе 1.2.

Дисперсией полинома р(х) называется максимальное целое h такое, что

deggcd(р(х), р(х + h)) > О,

либо 0, если р(х) = const. Дисперсия рациональной функции f(x) определяется как дисперсия ее знаменателя и обозначается Dis(/(x)).

Общим для известных алгоритмов решения задачи 1 является использование в том или ином виде дисперсии f(x) для вычисления некоторого разложения знаменателя. Разложение вычисляется при помощи наибольших общих делителей, что позволяет избежать вычислительных затрат на полную факторизацию знаменателя. Однако с момента появления первых алгоритмов суммирования рациональных функций (1971, 1975 гг.) был достигнут значительный прогресс в области факторизации полиномов. В частности, для полиномов с рациональными коэффициентами были предложены алгоритмы полной факторизации [26-28], для конечных полей коэффициентов — алгоритм [29]. В работе [10] (1994 г.) продемонстрировано, что для полинома с рациональными коэффициентами наиболее эффективным для вычисления дисперсии оказывается способ, основанный на полной факторизации этого полинома.

Если при решении задачи 1 полная факторизация знаменателя /(ж) вычисляется при поиске дисперсии, нет причин отказываться от ее использования на последующих этапах. В разделе 1.3 предложен алгоритм решен�