WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


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

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

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

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

АВТОРЕФЕРАТ

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

Москва – 2012

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

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

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

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

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

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

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

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

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



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

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

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

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

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

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

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

Алгоритм Цейлбергера [12], которому посвящена вторая глава диссер­ тации, является важным компьютерно-алгебраическим инструментом, при­ меняемым для суммирования многомерных гипергеометрических последова­ тельностей и автоматического доказательства тождеств. Для заданной гипер­ геометрической последовательности F (x, y) алгоритм строит рекурренцию вида G(x, y + 1) - G(x, y) = LxF (x, y), где Lx — свободный от y разностный оператор минимального порядка с по­ линомиальными коэффициентами, G(x, y) — гипергеометрическая последо­ вательность. Случай однородной цейлбергеровской рекурренции, т.е. случай, когда последовательность 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 г.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В разделе 1.3 приведено подробное изложение прямого алгоритма неопре­ деленного суммирования рациональных функций (алгоритм 1.1). Алгоритм находит полную факторизацию знаменателя f(x), затем представляет ее в виде суммы P0(x) P1(x) f(x) = +, Q0(x) Q1(x) P0(x) где имеет нулевую дисперсию и gcd(Q0(x), Q1(x+k)) = 1 для всех целых Q0(x) P1(x) k. После этого строится разложение на простейшие дроби, из которого Q1(x) вычисляются g(x), r(x).

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

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

Теорема 1.2. Пусть g(x), r(x) — решение задачи 1 для некоторой f(x), p1 pn r(x) = r(1) + · · · + r(n) = + · · · +, 1 n q1 qn где q1,..., qn, — неприводимые полиномы, 1,..., n — натуральные числа.

Тогда пара правильных дробей g(x), r(x) будет решением задачи 1 для f(x) если и только если max(-1,ki-1) n g(x) = gk,...,kn = g(x) - sign(ki) r(i)(x + j), i=j=min(0,ki) r(x) = rk,...,kn = r(1)(x + k1) + · · · + r(n)(x + kn), где k1,..., kn — целые числа.

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

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

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

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

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

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

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

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

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

Двумерная ненулевая последовательность F (x, y) называется гипергео­ метрической, если найдутся две пары взаимно простых ненулевых полиномов px(x, y), qx(x, y) и py(x, y), qy(x, y) такие, что px(x, y)F (x, y) = qx(x, y)ExF (x, y), py(x, y)F (x, y) = qy(x, y)EyF (x, y).

px(x,y) py(x,y) Отношения и называются соответственно x-сертификатом и qx(x,y) qy(x,y) y-сертификатом F (x, y).

Для гипергеометрической последовательности T (x, y) алгоритм Цейлбер­ гера [12] строит гипергеометрическую последовательность G(x, y) = (x, y)T (x, y), (x, y) K(x, y), и разностный оператор d L = ad(x)Ex +... + a1(x)Ex + a0(x) со свободными от y коэффициентами ad(x),..., a0(x) K[x], для которых G(x, y + 1) - G(x, y) = LT (x, y), если такие G(x, y), L существуют. Алгоритм обеспечивает минимальность порядка оператора L. Оператор L называется цейлбергеровским оператором для T (x, y), соответствующая рекурренция — цейлбергеровской рекурренци­ ей.

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

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

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

d операторы вида L = ad(x)Ex +... + a1(x)Ex + a0(x) со свободными от y коэффициентами ad(x),..., a0(x) K[x], обращающие гипергеометрические последовательности в нуль и имеющие минимальный порядок.

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

Согласно [15], последовательность T (x, y) имеет аннулирующий опера­ тор тогда и только тогда, когда ее x-сертификат может быть представлен в виде p(x + 1, y) Cx(T (x, y)) = R(x).

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

В разделе 2.3 предлагается способ вычисления порядка r минимального аннулирующего оператора: если Cx(T (x, y)) = R(x)p(x+1,y), p(x,y) l p(x, y) = cj(x)yj, j=то порядок r равен размерности LK(c0(x),..., cl(x)), т.е. линейной оболочки c0(x),..., cl(x).

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

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

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

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

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

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

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

Есть возможность потребовать использовать модификацию [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, 2me 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.

pdf.

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.






© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.