Компьютерная алгебра

Научное направление на стыке информатики и математики

Символьное интегрирование алгебраической функции f ( x ) =Икс/√ Икс ⁴ + 10 Икс ² - 96 Икс - 71с помощью системы компьютерной алгебры Axiom

В математике и информатике ^[1] компьютерная алгебра , также называемая символическими вычислениями или алгебраическими вычислениями , — это научная область, которая относится к изучению и разработке алгоритмов и программного обеспечения для управления математическими выражениями и другими математическими объектами . Хотя компьютерную алгебру можно считать подобластью научных вычислений , их обычно рассматривают как отдельные области, поскольку научные вычисления обычно основаны на числовых вычислениях с приблизительными числами с плавающей запятой , в то время как символьные вычисления делают упор на точные вычисления с выражениями, содержащими переменные , которые не имеют заданного значения и манипулируются как символы.

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

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

Терминология

Некоторые авторы отличают компьютерную алгебру от символьных вычислений , используя последнее название для обозначения видов символьных вычислений, отличных от вычислений с помощью математических формул . Некоторые авторы используют символьные вычисления для аспекта информатики предмета и «компьютерную алгебру» для математического аспекта. ^[2] На некоторых языках название поля не является прямым переводом его английского названия. Обычно по-французски это называется Calcul Formel , что означает «формальное вычисление». Это название отражает связь этой области с формальными методами .

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

Научное сообщество

Не существует научного общества , специализирующегося на компьютерной алгебре, но эту функцию берет на себя группа по особым интересам Ассоциации вычислительной техники под названием SIGSAM (Специальная группа по интересам по символическим и алгебраическим манипуляциям). ^[3]

Ежегодно проводится несколько конференций по компьютерной алгебре, главной из которых является ISSAC (Международный симпозиум по символьным и алгебраическим вычислениям), который регулярно спонсируется SIGSAM. ^[4]

Есть несколько журналов, специализирующихся на компьютерной алгебре, ведущим из которых является Journal of Symbolic Computation, основанный в 1985 году Бруно Бухбергером . ^[5] Есть также несколько других журналов, которые регулярно публикуют статьи по компьютерной алгебре. ^[6]

Аспекты информатики

Представление данных

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

Числа

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

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

Программирование эффективной реализации арифметических операций — сложная задача. Поэтому большинство свободных систем компьютерной алгебры и некоторые коммерческие, такие как Mathematica и Maple , ^{[8] [9]} используют библиотеку GMP , которая, таким образом, является стандартом де-факто .

Выражения

Представление выражения (8 - 6) × (3 + 1) в виде дерева Лиспа из магистерской диссертации 1985 года. ^[10]

За исключением чисел и переменных , каждое математическое выражение можно рассматривать как символ оператора, за которым следует последовательность операндов. В программах компьютерной алгебры выражения обычно представляются таким образом. Это представление очень гибкое, и многие вещи, которые на первый взгляд не кажутся математическими выражениями, можно представлять и манипулировать ими как таковые. Например, уравнение — это выражение с «=" в качестве оператора, матрица может быть представлена ​​как выражение с «матрицей» в качестве оператора и ее строками в качестве операндов.

Даже программы можно рассматривать и представлять как выражения с оператором «процедура» и, по крайней мере, двумя операндами, списком параметров и телом, которое само по себе является выражением с «телом» в качестве оператора и последовательностью инструкций в качестве операндов. И наоборот, любое математическое выражение можно рассматривать как программу. Например, выражение a + b можно рассматривать как программу сложения с параметрами a и b . Выполнение этой программы заключается в вычислении выражения для заданных значений a и b ; если им не присвоено никаких значений, результат оценки является просто входными данными.

Этот процесс отложенной оценки является фундаментальным в компьютерной алгебре. Например, оператор «=» уравнений в большинстве систем компьютерной алгебры также является названием программы проверки равенства: обычно вычисление уравнения приводит к уравнению, но когда требуется проверка равенства , либо явно запрашиваемый пользователем через команду «оценка логического значения», либо автоматически запускаемый системой в случае теста внутри программы, затем выполняется оценка логического результата.

Поскольку размер операндов выражения непредсказуем и может меняться в течение рабочего сеанса, последовательность операндов обычно представляется в виде последовательности либо указателей (как в Macsyma) [11], либо записей в хеш-таблице (как в Macsyma ) ^[11] или записей в хеш-таблице (как в Macsyma). Клен ).

Упрощение

Необработанное применение основных правил дифференцирования по x к выражению дает результат ${\displaystyle a^{x}}$

${\displaystyle x\cdot a^{x-1}\cdot 0+a^{x}\cdot \left(1\cdot \log a+x\cdot {\frac {0}{a}}\right).}$

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

Это упрощение обычно достигается путем переписывания правил . ^[12] Следует учитывать несколько классов правил переписывания. Самыми простыми являются правила, которые всегда уменьшают размер выражения, например E − E → 0 или sin(0) → 0 . Они систематически применяются в системах компьютерной алгебры.

Трудность возникает с ассоциативными операциями, такими как сложение и умножение. Стандартный способ справиться с ассоциативностью — учитывать, что сложение и умножение имеют произвольное количество операндов, то есть a + b + c представляется как «+»( a , b , c ) . Таким образом, a + ( b + c ) и ( a + b ) + c упрощаются до «+»( a , b , c ) , который отображается как a + b + c . В случае таких выражений, как a − b + c , проще всего систематически переписать − E , E − F , E / F как соответственно (−1)⋅ E , E + (−1)⋅ F , Е ⋅ F ⁻¹ . Другими словами, во внутреннем представлении выражений нет ни вычитания, ни деления, ни унарного минуса, вне представления чисел.

Другая трудность возникает с коммутативностью сложения и умножения. Проблема состоит в том, чтобы быстро распознать схожие термины , чтобы объединить или отменить их. Проверка каждой пары условий требует больших затрат при использовании очень длинных сумм и произведений. Чтобы решить эту проблему, Macsyma сортирует операнды сумм и произведений в таком порядке, в котором подобные термины располагаются в последовательных местах, что упрощает обнаружение. В Maple хеш- функция предназначена для генерации коллизий при вводе одинаковых терминов, что позволяет их объединять сразу после их введения. Это позволяет сразу распознавать и сохранять подвыражения, которые появляются в процессе вычисления несколько раз, и сохранять их только один раз. Это экономит память и ускоряет вычисления, избегая повторения одних и тех же операций с идентичными выражениями.

Некоторые правила перезаписи иногда увеличивают, а иногда уменьшают размер выражений, к которым они применяются. Это случай дистрибутивности или тригонометрических тождеств . Например, закон дистрибутивности допускает перезапись . Поскольку нет способа сделать правильный общий выбор, применять или не применять такое правило переписывания, такое переписывание выполняется только тогда, когда явно вызывается пользователем. Что касается дистрибутивности, компьютерная функция, применяющая это правило перезаписи, обычно называется «расширением». Правило обратной переписывания, называемое «фактором», требует нетривиального алгоритма, который, таким образом, является ключевой функцией в системах компьютерной алгебры (см. Полиномиальная факторизация ). ${\displaystyle (x+1)^{4}\rightarrow x^{4}+4x^{3}+6x^{2}+4x+1}$ ${\displaystyle (x-1)(x^{4}+x^{3}+x^{2}+x+1)\rightarrow x^{5}-1.}$

Математические аспекты

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

${\displaystyle (\sin(x+y)^{2}+\log(z^{2}-5))^{3}}$

рассматривается как полином по и ${\displaystyle \sin(x+y)}$ ${\displaystyle \log(z^{2}-5)}$

Равенство

Есть два понятия равенства математических выражений . Синтаксическое равенство — это равенство их представления в компьютере. Это легко проверить в программе. Семантическое равенство — это когда два выражения представляют один и тот же математический объект, как в

${\displaystyle (x+y)^{2}=x^{2}+2xy+y^{2}.}$

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

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

В компьютерной алгебре «каноническая форма» и «нормальная форма» не являются синонимами. ^[13] Каноническая форма такова, что два выражения в канонической форме семантически равны тогда и только тогда, когда они синтаксически равны, в то время как нормальная форма такова, что выражение в нормальной форме семантически равно нулю только в том случае, если оно синтаксически равно нулю. Другими словами, ноль имеет уникальное представление как выражение в нормальной форме.

В компьютерной алгебре обычно отдают предпочтение нормальным формам по нескольким причинам. Во-первых, вычисление канонических форм может быть более затратным, чем нормальные формы. Например, чтобы привести полином в каноническую форму, нужно разложить каждое произведение через дистрибутивность , а при нормальной форме это не обязательно (см. ниже). Во-вторых, как и в случае с выражениями, включающими радикалы, может случиться так, что каноническая форма, если она существует, зависит от некоторого произвольного выбора и что этот выбор может быть различным для двух выражений, которые были вычислены независимо. Это может сделать невозможным использование канонической формы.

История

Компьютерная алгебра, управляемая человеком

Ранние системы компьютерной алгебры, такие как ENIAC в Пенсильванском университете , полагались на человеческие компьютеры или программистов, чтобы перепрограммировать их между вычислениями, манипулировать многочисленными физическими модулями (или панелями) и снабжать устройство считывателя карт IBM. ^[14] Женщины-математики выполняли большую часть программ ENIAC, управляемых человеком: Джин Дженнингс , Марлин Вескофф , Рут Лихтерман , Бетти Снайдер , Фрэнсис Билас и Кей МакНалти возглавляли указанные усилия. ^[15]

Основы и ранние приложения

В 1960 году Джон Маккарти в Массачусетском технологическом институте исследовал расширение примитивных рекурсивных функций для вычисления символических выражений с помощью языка программирования Лисп . ^[16] Хотя его серия «Рекурсивные функции символьных выражений и их машинное вычисление» осталась незавершенной, ^[17] Маккарти и его вклад в программирование искусственного интеллекта и компьютерную алгебру с помощью Lisp помогли создать проект MAC в Массачусетском технологическом институте и организация, которая позже стала Стэнфордской лабораторией искусственного интеллекта (SAIL) в Стэнфордском университете , конкуренция которой способствовала значительному развитию компьютерной алгебры на протяжении конца 20 века.

Первые попытки символьных вычислений, предпринятые в 1960-х и 1970-х годах, столкнулись с проблемами, связанными с неэффективностью давно известных алгоритмов при переносе их в системы компьютерной алгебры. ^[18] Предшественники проекта MAC, такие как ALTRAN , стремились преодолеть алгоритмические ограничения за счет усовершенствований в аппаратном обеспечении и интерпретаторах, а более поздние усилия были направлены на оптимизацию программного обеспечения. ^[19]

Исторические проблемы

Большая часть работы исследователей в этой области заключалась в пересмотре классической алгебры с целью повышения ее эффективности при разработке эффективных алгоритмов для использования в компьютерной алгебре. Примером такого типа работы является вычисление полиномиальных наибольших общих делителей — задача, необходимая для упрощения дробей и важный компонент компьютерной алгебры. Классические алгоритмы для этих вычислений, такие как алгоритм Евклида , оказались неэффективными в бесконечных полях; алгоритмы линейной алгебры столкнулись с аналогичными трудностями. ^[20] Таким образом, исследователи обратились к поиску методов сведения полиномов (например, над кольцом целых чисел или уникальной областью факторизации ) к варианту, эффективно вычислимому с помощью алгоритма Евклида.

Алгоритмы, используемые в компьютерной алгебре

• Алгоритм Бухбергера : находит базис Грёбнера.
• Алгоритм Кантора – Цассенхауза : фактор-полиномы над конечными полями
• Алгоритм Фожера F4 : находит базис Грёбнера (также упоминается алгоритм F5).
• Алгоритм Госпера : найти суммы гипергеометрических терминов, которые сами являются гипергеометрическими терминами.
• Алгоритм завершения Кнута – Бендикса : для переписывания систем правил.
• Алгоритм многомерного деления : для многочленов от нескольких неопределенных
• Алгоритм кенгуру Полларда (также известный как лямбда-алгоритм Полларда): алгоритм решения задачи дискретного логарифмирования.
• Полиномиальное деление в длину : алгоритм деления многочлена на другой многочлен той же или меньшей степени.
• Алгоритм Риша : алгоритм вычисления операции неопределенного интегрирования (т.е. поиска первообразных )

Смотрите также

• Автоматизированное средство доказательства теорем
• Компьютерное доказательство
• Вычислительная алгебраическая геометрия
• Система компьютерной алгебры
• Дифференциальный анализатор
• Проверка доказательств
• Проверка модели
• Символьно-числовое вычисление
• Символическое моделирование
• Символический искусственный интеллект

Рекомендации

1. "Ассоциация ACM по компьютерной алгебре" .
2. Ватт, Стивен М. (2006). Сделать компьютерную алгебру более символичной (приглашено) (PDF) . Трансгрессивные вычисления 2006: Конференция в честь Жана Делла Дора (TC 2006). стр. 43–49. ISBN 9788468983813. ОСЛК  496720771.
3. Официальный сайт СИГСАМ
4. «Список конференций SIGSAM» . Архивировано из оригинала 8 августа 2013 г. Проверено 15 ноября 2012 г.
5. Коэн, Джоэл С. (2003). Компьютерная алгебра и символьные вычисления: математические методы . АК Петерс. п. 14. ISBN 978-1-56881-159-8.
6. Список журналов SIGSAM
7. Ричард Лиска Выражения, из «Особенностей программирования в системах компьютерной алгебры»
8. «Ядро Mathematica: проблемы проектирования и реализации». Октябрь 2006 г. Проверено 29 ноября 2023 г.
9. «Библиотека GNU Multiple Precision (GMP)» . Мэйплсофт . Проверено 29 ноября 2023 г.
10. Кэссиди, Кевин Г. (декабрь 1985 г.). Возможность автоматического освобождения памяти с параллельным выполнением программ в среде LISP (PDF) (магистерская диссертация). Военно-морская аспирантура, Монтерей/Калифорния. п. 15. АДА165184.
11. Macsyma Справочное руководство по математике и системам (PDF) . Максима . 1996. с. 419.
12. Бухбергер, Бруно; Лоос, Рюдигер (1983). «Алгебраическое упрощение» (PDF) . В Бухбергере, Бруно; Коллинз, Джордж Эдвин; Лоос, Рюдигер; Альбрехт, Рудольф (ред.). Компьютерная алгебра: символьные и алгебраические вычисления . Вычислительные приложения. Том. 4. стр. 11–43. дои : 10.1007/978-3-7091-7551-4_2. ISBN 978-3-211-81776-6.
13. Давенпорт, Дж. Х.; Сирет, Ю.; Турнье, Э. (1988). Компьютерная алгебра: системы и алгоритмы алгебраических вычислений . Академический. ISBN 0-12-204230-1. ОКЛК  802584470.
14. «ЭНИАК в действии: что это было и как работало» . ENIAC: Празднование истории инженерного дела Пенсильванского университета . Пенсильванский университет. Проверено 3 декабря 2023 г.
15. Лайт, Дженнифер С. (1999). «Когда компьютеры были женщинами». Технологии и культура . 40 (3): 455–483. дои : 10.1353/tech.1999.0128. ISSN  1097-3729.
16. Маккарти, Джон (1 апреля 1960 г.). «Рекурсивные функции символьных выражений и их машинное вычисление, Часть I». Коммуникации АКМ . 3 (4): 184–195. дои : 10.1145/367177.367199 . ISSN  0001-0782.
17. Вексельблат, Ричард Л. (1981). История языков программирования . Серия монографий АСМ. Конференция по истории языков программирования, Ассоциация вычислительной техники. Нью-Йорк Лондон Торонто: Академическая пресса. ISBN 978-0-12-745040-7.
18. «Символические вычисления (редакционная статья)» . Журнал символических вычислений . 1 (1): 1–6. 1 марта 1985 г. дои : 10.1016/S0747-7171(85)80025-0. ISSN  0747-7171.
19. Фельдман, Стюарт И. (1 ноября 1975 г.). «Краткое описание Альтрана». Бюллетень ACM SIGSAM . 9 (4): 12–20. дои : 10.1145/1088322.1088325. ISSN  0163-5824.
20. Кальтофен, Э. (1983), Бухбергер, Бруно; Коллинз, Джордж Эдвин; Лоос, Рюдигер; Альбрехт, Рудольф (ред.), «Факторизация многочленов», Компьютерная алгебра , Вена: Springer Vienna, vol. 4, стр. 95–113, номер документа : 10.1007/978-3-7091-7551-4_8, ISBN. 978-3-211-81776-6, получено 29 ноября 2023 г.

дальнейшее чтение

Для детального определения предмета:

• Бухбергер, Бруно (1985). «Символические вычисления (Редакционная статья)» (PDF) . Журнал символических вычислений . 1 (1): 1–6. дои : 10.1016/S0747-7171(85)80025-0.

Для учебников, посвященных данному предмету:

• Давенпорт, Джеймс Х .; Сирет, Ивон; Турнье, Эвелин (1988). Компьютерная алгебра: системы и алгоритмы алгебраических вычислений . Перевод с французского А. Давенпорта и Дж. Х. Давенпорта. Академическая пресса. ISBN 978-0-12-204230-0.
• фон цур Гатен, Иоахим; Герхард, Юрген (2003). Современная компьютерная алгебра (2-е изд.). Издательство Кембриджского университета. ISBN 0-521-82646-2.
• Геддес, КО; Чапор, СР; Лабан, Г. (1992). Алгоритмы компьютерной алгебры . Бибкод : 1992afca.book.....G. дои : 10.1007/b102438. ISBN 978-0-7923-9259-0.
• Бухбергер, Бруно; Коллинз, Джордж Эдвин; Лоос, Рюдигер; Альбрехт, Рудольф, ред. (1983). Компьютерная алгебра: символические и алгебраические вычисления . Вычислительные приложения. Том. 4. дои : 10.1007/978-3-7091-7551-4. ISBN 978-3-211-81776-6. S2CID  5221892.