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

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

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

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

05.13.11 – Математическое и программное обеспечение вычислительных

машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ

диссертации на соискание ученой степени

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

Москва – 2012

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

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

Научный руководитель:

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

Официальные оппоненты:

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

Ведущая организация:

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

Защита состоится «12» апреля 2012 г. в 15 часов на заседании диссертационного совета Д 002.017.02 при Федеральном государственном бюджетном учреждении науки Вычис­ лительном центре им. А.А. Дородницына Российской академии наук, расположенном по адресу: 119333, г.Москва, улица Вавилова, дом 40.

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

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

Ученый секретарь диссертационного совета Д 002.017.02, д. ф.-м. н., профессор В.В. Рязанов

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

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

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

Неопределенное суммирование является дискретным аналогом неопределен­ ного интегрирования. Как и в случае интегрирования, не всякая рациональ­ ная функция имеет рациональную неопределенную сумму. Поэтому начиная с опубликованной в 1975 г. статьи С.А. Абрамова [2] изучается задача адди­ тивной декомпозиции рациональных функций — представления их в виде () = ( + 1) () + (), где () — минимальная в некотором смысле рациональная функция, называ­ емая остатком. Как правило, минимизируется степень знаменателя остатка — в такой постановке задача является аналогом задачи выделения рациональ­ ной части неопределенного интеграла рациональных функций, классические методы решения которой были предложены Остроградским [3] и Эрмитом [4].

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

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

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

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

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

К этому случаю неприменимо доказательство корректности алгоритма Цейл­ бергера, предложенное в [12] и впоследствии воспроизведенное в ряде моно­ графий и учебников (например, [13, 14]). Кроме того, однородный случай был исследован в работе [15], поскольку он вызывал ошибки в работе реали­ зации алгоритма в ряде версий системы компьютерной алгебры Maple [16].

Исходное предположение авторов о некорректности работы самого алгоритма в однородном случае ошибочно, однако некоторые их результаты представля­ ют интерес, поскольку предложенный ими алгоритм в однородных случаях может оказываться намного эффективнее алгоритма Цейлбергера.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Публикации. Материалы диссертации опубликованы в пяти печатных работах, из них четыре публикации в рецензируемых журналах из перечня ВАК [A1, A2, A3, A4] и одна публикация в сборнике тезисов докладов кон­ ференции [A5].

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

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

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

В первой главе рассматривается задача неопределенного суммирова­ ния (аддитивной декомпозиции) рациональных функций: для () (), где — поле характеристики 0, найти пару рациональных функций (), () такую, что и степень знаменателя () минимальна (задача 1). Функции () и () на­ зываются соответственно просуммированной частью () и остатком.

При помощи удовлетворяющих условиям задачи 1 (), () можно упро­ стить вычисление определенных сумм: если (), (), () не имеют полю­ сов при =, + 1,..., и, кроме того, () не имеет полюса в + 1, то справедлива формула Задача 1 впервые сформулирована в [2]. Известен ряд алгоритмов ее решения, в частности, [2, 5–9].

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

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

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

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

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

Также дано краткое описание подходов, лежащих в основе ряда извест­ ных алгоритмов решения задачи 1. Рекурсивный подход (использован в ал­ горитмах [2, 7]) состоит в пошаговом отделении от функции суммируемых слагаемых. В линейно-алгебраическом подходе (алгоритмы [5, 6, 8]) сначала строятся знаменатели искомых функций (), (), после чего коэффициен­ ты числителей могут быть получены из системы линейных уравнений. Алго­ ритм [9] использует подход, близкий к прямому: для построения (), () используется представление () в виде суммы слагаемых с попарно взаимно простыми знаменателями, свободными от сдвигов (т.е. gcd( (), (+)) = для всех целых > 0). Для построения соответствующего разложения зна­ менателя () полной факторизации не требуется.

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

максимального целого такого, что знаменатели () и (+) имеют общие множители. Это позволяет избежать полной факторизации знаменателя (), заменяя ее разложением, основанным на вычислении наибольших общих де­ лителей. Однако с разработкой эффективных алгоритмов полной фактори­ зации полиномов (например, [17–19] для рациональных функций) появились данные за то, что это стало ненужным: так, для полиномов с рациональными коэффициентами статья [10] демонстрирует, что собственно дисперсию наи­ более эффективно вычислять с использованием полной факторизации рас­ сматриваемого полинома. В системе компьютерной алгебры Maple [16] такой алгоритм вычисления дисперсии применяется уже независимо от поля коэф­ фициентов. Поэтому представляет интерес разработка алгоритма неопреде­ ленного суммирования рациональных функций в рамках прямого подхода:

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

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

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

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

В разделе 1.4 построено полное описание множества решений задачи 1:

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

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

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

В разделе 1.6 предложен алгоритм 1.2, являющийся модификацией алго­ ритма 1.1. Доказана Теорема 1.3. Прямой алгоритм суммирования с минимизацией просум­ мированной части (алгоритм 1.2) строит решение задачи 2. Без учета затрат на факторизацию знаменателя () для выполнения алгоритма до­ статочно (2 ) операций над элементами поля, где — степень знаме­ нателя ().

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

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

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

Результаты первой главы опубликованы в работах [A1, A3, A4].

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

Ненулевая последовательность () называется гипергеометрической, если для ее элементов выполняется где (), () [], (), () = 0, gcd((), ()) = 1.

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

Двумерная ненулевая последовательность (, ) называется гипергео­ метрической, если найдутся две пары взаимно простых ненулевых полиномов Отношения (,) и (,) называются соответственно -сертификатом и -сертификатом (, ).

Для гипергеометрической последовательности (, ) алгоритм Цейлбер­ гера [12] строит гипергеометрическую последовательность (, ) (, ), и разностный оператор со свободными от коэффициентами (),..., 0 () [], для которых если такие (, ), существуют. Алгоритм обеспечивает минимальность порядка оператора. Оператор называется цейлбергеровским оператором для (, ), соответствующая рекурренция — цейлбергеровской рекурренци­ ей.

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

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

В разделе 2.3 исследуются минимальные аннулирующие операторы, т.е.

операторы вида = () +... + 1 () + 0 () со свободными от коэффициентами (),..., 0 () [], обращающие гипергеометрические последовательности в нуль и имеющие минимальный порядок.

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

Согласно [15], последовательность (, ) имеет аннулирующий опера­ тор тогда и только тогда, когда ее -сертификат может быть представлен в виде Кроме того, в этой работе описано множество последовательностей, для ко­ торого Maple-реализация алгоритма Цейлбергера работала некорректно. Для последовательностей из цейлбергеровская рекурренция заведомо однород­ на. В [15] для таких последовательностей авторами предложен алгоритм по­ иска цейлбергеровского оператора, отличный от алгоритма Цейлбергера (и более эффективный для этих последовательностей).

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

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

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

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

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

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

Реализации алгоритмов решения задач неопределенного суммирования рациональных функций (задачи 1–3) доступны через общий интерфейс — про­ цедуру RationalSum. Обязательные аргументы процедуры — рациональная функция () и имя переменной, возвращается пара рациональных функций, являющаяся решением задачи 1 для (). Необязательные аргумен­ ты позволяют пользователю выбирать между алгоритмами решения задачи 1 (помимо прямого алгоритма 1.1 доступны линейно-алгебраический алго­ ритм [5], рекурсивный алгоритм [2] и алгоритм GGSZ [9]) и запрещать или разрешать факторизацию знаменателя () при вычислении ее дисперсии.

Есть возможность потребовать использовать модификацию [7] либо дополни­ тельную минимизацию степени просуммированной части (в зависимости от используемого алгоритма решения задачи 1 применяется прямой алгоритм 1.2 или расщепляющий алгоритм 1.3) или степени числителя остатка. При ис­ пользовании прямого алгоритма имеется возможность выбирать между пред­ ставлениями результата: по умолчанию просуммированная часть и остаток представляются в том виде, в котором они постороены алгоритмом, и можно потребовать приведения их к виду пары дробей со взаимно простыми числи­ телем и знаменателем.

Алгоритм 2.1 построения минимального аннулирующего оператора реа­ лизован в процедуре MinimalAnnihilator. Модифицированный алгоритм Цейл­ бергера 2.2, использующий поиск аннулирующих операторов в однородном случае, реализован как часть процедуры Zeilberger, применяющей алгоритм Цейлбергера.

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

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

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

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

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

A2. Polyakov S. P. On homogeneous Zeilberger recurrences // Advances in Ap­ plied Mathematics. 2008. Vol. 40, no. 1. Pp. 1–7.

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

A4. Поляков С. П. Неопределенное суммирование рациональных функций с факторизацией знаменателей // Программирование. 2011. № 4. С. 23–27.

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

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

С. 1071–1075.

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

Т. 15. С. 1035–1039.

3. Ostrogradsky M. De l’integration des fractions rationnelles // Bull. de la Classe Physico-Mathmatique de l’Acadmie Imperiale des Sciences de Sain­ t-Petersburg. 1845. Vol. IV. Pp. 145–167, 286–300.

4. Hermite Ch. Sur l’intgration des fractions rationnelles // Annales de Mathmatiques, 2`me srie. 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., Strehl V. Rational summation and Gosper–Petkovek representa­ tion // Journal of Symbolic Computation. 1995. Vol. 20. Pp. 617–635.

9. Gerhard J., Giesbrecht M., Storjohann A., Zima E. V. Shiftless decomposition and polynomial-time rational summation // Proceedings of ISSAC’03. 2003.

Pp. 119–126.

10. Man Y.-K., Wright F. J. Fast polynomial dispersion computation and its application to indefinite summation // Proceedings of ISSAC’94. 1994.

Pp. 175–180.

11. Pirastu R. A note on the minimality problem in indefinite summation of ratio­ nal functions // Actes du Seminaire Lotharingien de Combinatoire, 31 session, Saint-Nabor, Ottrot, October 1993, Publications de l’I.R.M.A. Vol. 21. 1994.

Pp. 95–101.

12. Zeilberger D. The method of creative telescoping // Journal of Symbolic Com­ putation. 1991. Vol. 11. Pp. 195–204.

13. Petkovek M., Wilf H. S., Zeilberger D. A=B. Natick, MA: A K Peters, 1996.

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-Mech­ anization, 2004. URL: http://www.mmrc.iss.ac.cn/pub/mm23.pdf/LeLi.

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

17. Lenstra A. K., Lenstra H. W., Lovsz L. Factoring polynomials with rational coefficients // Mathematische Annalen. 1982. Vol. 261, no. 4. Pp. 515–534.

18. Schnhage A. Factorization of univariate integer polynomials by diophantine 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.