Содержание к диссертации
Введение
1 Введение 4
1.1 Цель и предмет исследования 4
1.2 История и аналоги 7
1.3 Основные результаты, выносимые на защиту 11
2 Математические основы Построителя 13
2.1 Что содержит Построитель 16
2.2 Некоторые сведения о применяемых алгоритмах
2.2.1 Действия с перестановками 17
2.2.2 Дроби 17
2.2.3 Линейная алгебра 18
2.2.4 Арифметика многочленов 18
2.2.5 Факторизация многочленов 19
2.2.6 Базис Гребнера 19
2.2.7 Симметрические функции 20
2.3 gx-кольца 21
2.3.1 Многочлены над с-евклидовым кольцом 27
2.3.2 Прямая сумма колец 28
2.3.3 Кольцо остатков 30
2.3.4 Преобразования описаний колец 35
2.3.5 gx-действия в программах 37
2.4 Усиление способа ЛЛЛ-Григорьева разложения на простые множители в GF(q)[x,y] 38
2.4.1 Нахождение неприводимого множителя многочлена / из F[t] [х] для конечного поля F 41
2.4.2 Обоснование правильности алгоритма 42
2.4.3 Оценка сложности 46
2.5 Выводы 50
3 Общие требования к языку программирования 51
3.1 Гибкость стратегии вычисления 52
3.2 Функциональность 55
3.3 Богатые средства задания типов 56
3.4 Категорность 57
3.5 Поддержка полиморфизма 58
3.6 Поддержка стандартных отображений между областями 61
3.7 Выразимость свойств значений 3.7.1 Категории алгебраической библитеки проекта BAL 65
3.7.2 О логическом программировании в языках Cayenne,
Aldor 70
3.7.3 О применении правил, равенств 71
3.8 Выводы 74
4 Параметрические алгебраические области 76
4.1 Архитектура библиотеки основной алгебры 77
4.1.1 Ключевые черты проекта 77
4.1.2 Категории, представленные в проекте 83
4.1.3 Начальный пример 84
4.1.4 Использование подхода образца 87
4.1.5 Смысл случаев для параметрической области 92
4.2 О расширении языка зависимыми типами 94
5 Заключение 96
Список литературы
- Основные результаты, выносимые на защиту
- Линейная алгебра
- Богатые средства задания типов
- Категории, представленные в проекте
Основные результаты, выносимые на защиту
Данный способ построения программ для алгебраических областей близок к обычно применяемому в математических работах способу описания вычислений. Наиболее известные на настоящее время языки и системы, применяющие категорный подход, суть Axiom [Je], Aldor [Al], MuPAD [Mu]. Система Axiom является в настоящее время обширной библиотекой математики для языка программирования Aldor (сейчас еще продолжается переписывание Axiom на Aldor).
Нам не известны какие-либо отечественные разработки этого направления — кроме упоминаемых здесь программ Построитель [Ме2], BAL [МеЗ].
Работу на этом направлении автор начал в 1990-м году. Первым итогом была программа САС [Mel], написанная на безтиповом функциональном языке. Описания алгебраических областей dR строились из других описаний согласно конструкторам (Многочлен, Вектор, ...). Далее, описания dR передавались функциям в качестве дополнительного аргумента, и добавлялась система расстановки препроцессором по умолчанию подходящих аргументов dR.
Из этого опыта стало ясно, что желательно использовать языки программирования с более богатыми средствами задания типов. Последние получили к тому времени достаточно работоспособные и доступные воплощения, например, [GH].
Вернемся к рассмотрению программ Построитель, Aldor - Axiom, MuPAD. Про систему MuPAD [Ми] нам известно, что она использует язык MuPAD, с процедурами и другими нефункциональными средствами, делающими эту программную архитектуру далекой от Построителя.
Система Axiom создана раньше, чем MuPAD, обладает всеми необходимыми для нашего сравнения свойствами, ее обширная библиотека состоит из надежно воплощенных алгоритмов хорошей производительности. Поэтому в дальнейшем мы считаем, что достаточно только сравнения Построителя с программой Aldor - Axiom.
Вот некоторые сведения об этих средствах. Отметим, что системы Aldor - Axiom и MuPAD не полностью доступны: не предоставляют пользователю исходный код, и следовательно, возможности самостоятельно исправлять эту программу. Axiom даже является полностью коммерческой системой. Такое положение мало отвечает потребностям научного сообщества.
Далее, Построитель применяет чисто функциональное программирование и ленивый способ вычисления. Aldor (Axiom), MuPAD не являются функциональными системами и применяют только прямые вычисления.
Aldor [А1] есть язык программирования похожий на ML, отчасти — на Haskell, но расширенный возможностью действовать с (абстрактными) типами данных (представляющих математические области) как с обычными значениями. Языковым средством для этого являются зависимые типы (dependent types) — типы, зависящие от значения. Притом допускается откладывать распознавание некоторых типов на этап выполнения программы.
Так, например, это позволяет более естественно запрограммировать область вычетов Z/(m) с динамически меняющимся га (Подраздел 4.2).
В этом смысле, — смысле программной архитектуры, — Построитель есть библиотека, случаев (instances) для алгебраических конструкторов языка Haskell. Причем отсутствие в языке зависимых типов восполнено применением подхода образцового элемента (Подраздел 4.1.1 пункт (sa)). Подраздел 4.1.4 объясняет трудности, встречающиеся на этом пути.
Перечислим коротко главные отличия программы Построитель от системы Aldor - Axiom. Построитель функционален и вычисляет лениво , применяет другую систему программирования (Haskell), применяет подход образцового элемента как замену языкового средства зависимых типов, чаще, чем Aldor, возлагает распознавание случаев категорий на прикладную программу (недостаток, возникающий изза предыдущего пункта), распространяется свободно вместе с исходным текстом и опирается на свобод но распространяемую с исходным текстом реализацию языка Хаскел.
Что касается общего математического подхода, примененного во всех этих системах, то он более-менее очевиден. Подробности же математических методов (Раздел 2) относятся не к основаниям системы, а к научной библиотеке, каковая особенно велика по охвату в системе Axiom.
Раз существует весьма естественно построенное средство математических вычислений Aldor - Axiom, то чем вызвана разработка Построителя? Она вызвана следующими причинами. Построитель рассматривается как проверка практической возможности создания достаточно производительной программы общего математического назначения, применяющей категорный и чисто функциональный подход и непрямой способ вычисления.
Система Aldor - Axiom слишком закрыта . Очень недавно этот недостаток был немного исправлен за счет выделения языка Aldor. К тому же до этого события трудно было даже понять, где в системе Axiom язык программирования, а где алгебраическая библиотека.
Язык Haskell проще (как это вообще свойственно чисто функциональным языкам), связанная с ним идеология стоит ближе к лямбда исчислению и обладает хорошими теоретическими свойствами.
Язык Haskell имеет несколько свободных реализаций. Aldor имеет одну реализацию, не проверенной пользователями надежности; библиотека Axiom в настоящее время еще переписывается на Aldor. Разработчики системы Aldor объявили о намерении сделать исполняемый код свободно распространяемым.
Помимо Построителя, некоторые опыты использования Хаскела в программировании алгебры, описаны в статьях [Fo, Ка].
Все ныне существующие разработки по применению языка Хаскел к компьютерной алгебре, — кроме наших программ BAL, Построитель, — ограничиваются некоторым маленьким кругом представимых алгебраической областей и не делают попыток осознать задачу о том, как могут быть представлены более сложные, параметрические области, скажем, кольцо остатков по идеалу, заданному образующими.
Правда, в 2001 году в Haskell была предпринята попытка выразить средство зависимых типов через расширение языка Haskell так называемыми экзистенциальными типами (официальные данные о проекте отсутствуют). Но на этом направлении имеются большие трудности, и едва ли можно рассчитывать на полноценную замену. 1.3 Основные результаты, выносимые на защиту
Для ясного выделения результатов автора в дальнейшем изложении те части труда (теоремы, предложения, леммы, алгоритмы . ..), которые автор хочет особо отметить как свои результаты, отмечены знаком ( ). В диссертации представлены следующие итоги.
Линейная алгебра
Этот результат по вычислительной алгебре есть побочный итог разработки программы факторизации, вошедшей в систему Построитель [Ме2], и он опубликован в [Ме5]. Речь идет о разложении на неприводимые множители многочлена двух переменных над произвольным конечным полем GF(q) (из q элементов).
Известный LLL метод [LLL] был приспособлен в статьях Д.Ю.Григорьева и А.Л.Чистова [CG] (1982) и A.K.Lenstra [Le] (1985) для получения факторизации многочлена / из F[x,y] над конечным полем F. [Le] выводит оценку сложности с основной частью 0((deg2,/)6(deg /)2) арифметических действий в F.
В препринте [CG] 1982 года (в [G] тот же способ описан на русском языке) дан среди других результатов алгоритм факторизации многочлена / из F[t,x] с затратой количества арифметических действий в F, ограниченного некоторой степенью величины (degj. f)(degtf) q Подробные же оценки в [CG] не выводились. Здесь мы показываем, что способ [CG] допускает, — после некоторых поправок, — лучшую оценку: с основной частью 0((degx / )4(degy/)3).
Заметим также, что исходная задача равносильна факторизации в -Р[ ][аф
Обсуждаемые здесь алгоритмы из [G, Le] являются в основном переработкой известного способа LLL факторизации в Ъ\х\\ общность задач состоит в том, что кольца Z и F[t] суть евклидовы. Эта переработка, — по версии [G], — изложена нами (с поправками) ниже в Разделе 2.4.1.
Для понимания дальнейших рассуждений читатель должен обозревать Алгоритм из Раздела 2.4.1 — который будем называть просто Алгоритм. О ссылках: некоторые ссылки из данного раздела могут быть заменены на параграфы книги [Mi] (1989), посвященные факторизации в Ъ\х\ и F[i,:c].
Способ ([Le]: Раздел 2) отличается от [G] приемом поиска малого вектора Ь в решетке L (смотри Алгоритм). Алгоритм [G] ищет Ъ, накладывая линейные соотношения на неопределенные коэффициенты и-1у2 Є F — подшаг hO-sv Алгоритма. Способ же ([Le]: Раздел 2) применяет для поиска Ъ редукцию базиса: ([Le]: Раздел 1). [G] не выводит подробной оценки стоимости, тогда как [Le] (Теорема 2.18) доказывает оценку 0(r6\f\2 + (r3 + \ff)-q-s) (CB-Le) действий в F (формула приведена к нашим обозначениям).
Моею целью было выбрать высокопроизводительный способ вычисления и, разобрав его в подробностях, составить работоспособную программу. В ходе этого исследования получен излагаемый здесь результат по алгоритмам.
Во первых, было ясно, в чем состоят и что дают способы ([Le]: Разделы 1,2). Существует еще работа [GK] (1985), посвященная, в основном, вероятностному способу факторизации. Для детерминированного алгоритма она не дает лучшей оценки, чем (CB-Le). Теперь, изучая [G], мы (1) подправили детали алгоритма [G], (2) используя эту поправку и неравенства из [G, Le] для некоторых инвариантов решетки, вывели лучшую оценку на количество неопределенных коэффициентов. Это ведет к полной оценке 0(г4 Л3 + r4(logg г)3 Л2 + r3/(logD /)3 (log q)) (СВ) действий в F.
Заметим: из этих оценок не следует, что предлагаемый способ CG-усиленный обязательно дешевле асимптотически, чем способ [Le].
Результат состоит из трех улучшений. 1. Для нового способа ( CG-усиленный ) доказана меньшая верхняя оценка, чем известна для [Le]. Это дает больше знания о методе — в таком же смысле, в каком, например, условие п 7 для целого числа дает больше информации, чем условие п 8 . 2. Для нового способа выведена весьма малая степенная верхняя оценка, тогда как работа [CG], не ставила такой цели и ограничивалась некоторой (очень большой) степенной оценкой. 3. Новый способ действительно дешевле, чем [CG]. Это видно из того, в нем требуется решать линейную систему размера меньшего порядка зависимости от г, /. Нижние частичные оценки пока не выводились.
Наш вывод использует сдвиговую симметрию на части базиса для L. Эта симметрия могла бы вести и к специальному улучшению способа редукции базиса. Автор лока-что не нашел такого улучшения.
Вот основные изменения к алгоритму [G] (Раздел 2.4.1): (1) На подшаге hO-lt находится не просто треугольный базис для решетки L, а так называемый усиленный базис В. При этом используется сдвиговая симметрия части исходного базиса L. (2) При поиске разделяющего р Є А на Шаге р не применяется вычисление результанта. Прием (1) позволяет вывести лучшую оценку на количество неопределенных коэффициентов. Прием (2) избавляет от необходимости рассматривать способы вычисления результанта над F[t] и оценки их стоимости.
Применяя обозначения из начала Раздела 2.4, запишем Алгоритм для этой задачи: Шаг sq. Сведение к свободному от квадратов, примитивному / Є А[х]. Вычисляя НОД с производной, применяя некоторые другие приемы, свести задачу к случаю свободного от квадратов / такого, что cleg / 1, cont/ = 1, lc(lc/) = 1. Шаг р. Найти в А разделяющий простой многочлен р. Достаточно найти р Є GF(q)[t] неприводимый над F и такой, что р не делит 1с/ и /modp свободен от квадратов. Для этого порождать подряд все нормированные р Є GF(q)[t], начиная с линейных и применяя к р проверку на неприводимость над F. Наличие квадратов в /modp проверяется нахождением НОД с производной. Шаг f. Факторизовать /modp в (А/(р))[х].
Богатые средства задания типов
Так, нам кажется многообещающим развитие функциональных языков в направлении программирования логики равенства через системы переписывания термов. Причем термы рассматриваются с сортами (типами) и правила переписывания применяются по модулю некоторых отношений эквивалентности. Сведения об этом содержатся в статьях [GM, НО, AV] а также в материалах по программе Maude [Md].
Языки Aldor [А1] и Cayenne (Кайен) [Au] также пытаются привнести использование явно выраженных свойств и доказательств в программирование.
Дело в том, что существующие средства программирования отстают от идеологии вычислений , давно применяемой математиками.
Главное преимущество вычислителя-математика состоит в том, что вычисления идут в двух пространствах: доказательства и использование свойств промежуточных функций разумно чередуются с прямым вычислением. Вот, к примеру, две программы для нахождения определителя матрицы над рациональными числами.
Программа (2) лучше тем, что дает некоторую основу для возможных доказательств и упрощения на этапе компиляции. Математики потому вычисляют трудные примеры успешнее, чем программы, что они удачно пользуются свойствами, такими как (а) - (г). Например, во многих частных случаях вызова программы (1) нетрудно доказать, что det М = 0, в то время как вызов производит большой объем вычислений.
Во многих случаях учет свойств (а) - (г) даст компилятору принципиальную возможность сильно упрощать программу. Свойства (а) - (г) могут быть выведены из (1). Но программист указывает эти свойства явно, если они важны и программист сомневается в том, что компилятор сумеет их вывести самостоятельно.
Условие правильности.
Способность компилятора проверять условие законности применения того или иного способа не менее важна, чем его способность упрощать программу. Во многих случаях компилятор мог бы простейшими рассуждениями опровергнуть условие законности и не пропустить бессмысленную программу к выполнению.
Но не только выражение типа задает условие законности. Например, программа сортировки вставкой sort : : Ord а = [а] - [а] бессмысленна для области а, на которой сравнение Ord.compare не обладает свойством транзитивности. А это свойство удобно выражается и могло бы быть предметом проверки во время компиляции. Скажем, компилятор мог бы заключить, что порядок, определенный на области пар (а, а) лексикографически через действие compare на а, транзи-тивен, если compare транзитивна на а. Такие легко выражаемые важные свойства часто встречаюся. Главное соображение на этот счет таково: часто указание свойств частей программы важнее ее вычислительной части. Обычно важнее объяснить, что вычисляется, приведя некоторые свойства значения, чем сказать — как вычисляется, какими действиями и в каком порядке.
В языке Хаскел-98 эти соображения мало учтены. Тому есть оправдание: языки высокого уровня и без того сложны для воплощения.
В программах Построитель, BAL [Ме2, МеЗ] этот недостаток Хаскела наполовину выправлен за счет следующих решений: (1) подход образцового элемента, base-действия (Подраздел 4.1.1), (2) введение библиотеки классических категорий алгебры (Подраздел 3.7.1). Решение (1) дает возможность прямо разбирать значения некоторых важных свойств областей и действий. Решение (2) можно считать неким проектом новой стандартной библиотеки алгебры для языка Хаскел. В стандартной прелюдии (Prelude) Хаскел-98 объявляются такие алгебраические классы (мы будем называть их категориями) как, например, Num — с действиями + , -, , fromlnteger , Integral — с делением с остатком quotRem, Fractional — с делением (/). При этом в способе определения стандартных случаев для конструкторов Integer, Ratio просматривются математические соответствия этих классов: Кольцо (Ring), евклидово кольцо (EuclideanRing), поле (Field). Только в Хаскеле-98 про эти отвлеченные действия +, , . . . известны лишь их типы, скажем, (+) : : а - а - а. Например, условие Num а = , объявленное программистом, никак не связывается со свойствами соответствующих действий. Так, выражение (программа) (1 + х) - х : : Num а = а ни при каких режимах компилятора Хаскел-98 не может быть заменено на 1 : : Num а = а
Так что истинные алгебраические категории имеют довольно-таки отдаленное отношение к тому, как компилятор Хаскел-98 понимает алгебраические программы. Так же обстоит дело с языками Aldor, Cayenne.
Для исправления этого недостатка проект библиотеки BAL [МеЗ] для языка Хаскел (Basic Algebra Library) предлагает, в частности, усовершенствование башни алгебраических категорий — смотри следующий Раздел.
Нижеследующую систему категорий автор причисляет к результатам диссертации, считая, что эти категории исправляют крупнейший недостаток стандарта на алгебраические классы и случаи для языка Haskell-98.
Категории, представленные в проекте
Перед чтением последующего объяснения советуем вспомнить введение из Подраздела 4.1.1 (ключевые черты ...). ResidueE есть абстрактный тип для кольца остатков. Какой-либо начальный элемент кольца остатков евклидова кольца г : : EuclideanRing а = ResidueE а может быть создан применением функции rse. Например, г = rse с 4 3 [(3,1)] : : ResidueE Integer строит 4 как элемент г области Z/(3) так, что 4 сводится по модулю 3 к каноническому представителю 1; 3 вписывается в представление элемента г и называется основа . Здесь rse принимает список [(3,1)] как данную факторизацию основы; использование факторизации показано на странице 91. Другой пример: вызовы rse с 2 3 [] , rse с 4 3 [] создают два элемента области Z/(3), их внутренние представления суть Rse 2 3 [], Rse 1 3 [] .
Режим с указывает функции rse свести первый аргумент канонически по основе. Режим f означает с и еще вынуждает rse приготовить факторизацию основы; и факторизация берется как готовая, если она задана в аргументе непустой. Факторизация может быть пропущена путем задания пустого списка.
Части элемента г кольца остатков могут быть извлечены применением функций rseRepr, rseBase,rseFt.
Однажды создав какой-нибудь простейший элемент s : : ResidueE а, программа может применять s как образец для алгебраической области и естественно проектировать элементы х : : а в кольцо остатков "по образцу" s путем применения cast s х. Действие mapCoef принадлежит классу PolLike из предлагаемой библиотеки. Вызов mapCoef f р применяет функцию f к каждому коэффициенту многочлена р, приводя итог (многочлен) к каноническому виду. Библиотека задает для конструктора ResidueE случай instance EuclideanRing а = Additive (ResidueE a) where ... — и другие случаи, до CommutativeRing включительно. Это отражает известую те орию из общей алгебры. Например, умножение остатков призводится умножением представителей и проектированием итога в канонический остаток. Далее, библио тека даже определяет случаи instance ... = GCDRing (ResidueE a) where ... , instance ... = Field (ResidueE a) — их особое назначение объясняется в дальнейшем. Зачем нужна категория EuclideanRing Не достаточно ли частных случаев для типа ResidueE Integer? Не достаточно, так как Rational [х] и некоторые другие области тоже имеют осмысленное действие деления с остатком divRem с требуемыми свойствами. В частности, эти области имеют одну полиморфную программу для вычисления НОД через divRem.
Вышеназванные случаи задают арифметику кольца остатков R = Z/(m) из разбираемого примера. И поскольку предлагаемый стандартный случай GCDRing (UPol а) определяет НОД в R[x] через арифметику области R, все это позволяет программе из примера найти gcd [f m, g m] :: UPol (ResidueE Z).
Что касается выражений osetCard pS, subringProps pR в конце программы, они выдают принадлежности последней из областей R = (Z/ (т)) [х] . Для этого программа BAL разбирает башню областей Z - Z/(m) - (Z/(m))[x], выводя значения принадлежностей каждой области из таких значений для более простых областей. Но добавим теперь основу 4 к списку ms в разбираемом примере: gcs = gcdMods f g [2,3,5,4] Программа компилируется, при выполнении вычисляет и печатает искомый НОД многочленов для m = 2, 3, 5, а потом прерывается с сообщением Ошибка: gcd [f,g] - R[x], R = Z/(4), R не является кольцом с НОД Дело в том, что программа пытается представлять алгебраическую область R = R(m) = Zj(m), зависящую от параметра — целого числа т. А это не укладывается в рамки обычного для языка Хаскел представления области как типа с конечным набором случаев на нем. Подробнее о данном примере: для вычисления gcd в R[x] требуется осмысленный метод для gcd в R. Он возможен, например, для R = Z, Z [у] . Но для Z/(m) он имеет смысл лишь при простом т. Если число m простое, то Z/(m) есть поле и также кольцо с НОД, и тогда gcd f m g m вычисляется способом над кольцом с НОД . Чтобы учесть эту теорию BAL задает случаи instance EuclideanRing а = GCRRing (ResidueE a) where ... instance EuclideanRing a = Field (ResidueE a) Но этого не достаточно для представления параметрической области Z/(m). Так, данные resSamples :: [ResidueE Z] могут принадлежать областям Z/(ml), Z/(m2), ... внутри одного и того же типа ResidueE Z. Случаи GCDRing, Field (кольцо с НОД, поле) подходят с виду, с точки зрения компилятора, к каждой из областей Z/(m) — ибо области отнесены к одному типу. Но математически осмысленным значением m для случаев GCDRing, Field является только простое т.
Вызов gcdMods f g [2,3,5,4] применяет gcd f m g m. Затем программа gcd извлекает коэффициент г из f m как образец для области и проверяет условие detectGCDRing г. Если оно выдает значение отличное от Yes, gcd прерывает программу. Такие предварительные проверки законности как эта detectGCDRing г, были бы всегда желательны по умолчанию, так как они предотвращают бессмысленные вычисления в случае, когда пользователь вызвал действие для области с неподходящим значением параметра. Были бы желательны — если бы не возможная дороговизна вычисления условия законности. Но в данном случае проверка условия для коэффициента много дешевле, чем собственно цикл gcd для многочленов. Так что тут проверка detectGCDRing г уместна. В общем случае программист может пропустить любую проверку вида detectCategory. Но в таком месте программист возлагает на себя заботу о применении соответствующего метода только к области с правильным значением параметра.
Далее, образец г есть остаток, он определяет текущую область R = Z/(m), г содержит параметр ft = rseFt г. Действие gcd применяет detectGCDRing для выяснения, является ли Z/(m) кольцом с НОД. Функция detectGCDRing применяет baseGCDRing ...и разбирает список факторизации ft в элементе кольца остатков. Примененная в этом примере в четвертый раз, эта функция находит ft = [(2,2)], это означает, что m не простое, и тогда программа gcd вызывает прерывание.
Итак, сопоставления типа со случаем (instance match) не достаточно для распознавания категории для алгебраической области. Иногда еще требуется проверить значение параметра, содержащегоя в ОЭ.
