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

Научная область на стыке информатики и математики

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

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

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

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

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

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

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

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

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

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

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

Аспекты компьютерной науки

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

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

Числа

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

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

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

Выражения

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

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

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

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

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

Упрощение

Грубое применение основных правил дифференцирования по 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).}$

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

Это упрощение обычно выполняется с помощью правил переписывания . ^[14] Существует несколько классов правил переписывания, которые следует рассмотреть. Простейшими являются правила, которые всегда уменьшают размер выражения, например 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 , E ⋅ F ⁻¹ . Другими словами, во внутреннем представлении выражений нет ни вычитания, ни деления, ни унарного минуса, за пределами представления чисел.

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

Некоторые правила перезаписи иногда увеличивают, а иногда уменьшают размер выражений, к которым они применяются. Это случай дистрибутивности или тригонометрических тождеств . Например, закон дистрибутивности позволяет переписывать и Поскольку нет способа сделать хороший общий выбор применения или неприменения такого правила перезаписи, такое переписывание выполняется только при явном вызове пользователем. Для дистрибутивности компьютерная функция, которая применяет это правило перезаписи, обычно называется «expand». Обратное правило перезаписи, называемое «factor», требует нетривиального алгоритма, который, таким образом, является ключевой функцией в системах компьютерной алгебры (см. Факторизация полиномов ). ${\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}.}$

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

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

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

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

История

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

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

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

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

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

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

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

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

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

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

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

Ссылки

1. «Ассоциация ACM в компьютерной алгебре».
2. Уотт, Стивен М. (2006). Making Computer Algebra More Symbolic (Приглашенный) (PDF) . Transgressive Computing 2006: Конференция в честь Жана Делла Дора (TC 2006). стр. 43–49. ISBN 9788468983813. OCLC  496720771.
3. Официальный сайт SIGSAM
4. "Список конференций SIGSAM". Архивировано из оригинала 2013-08-08 . Получено 2012-11-15 .
5. Коэн, Джоэл С. (2003). Компьютерная алгебра и символьные вычисления: математические методы . AK Peters. стр. 14. ISBN 978-1-56881-159-8.
6. Список журналов SIGSAM
7. "Лекция 12: Рациональные функции и преобразования — Введение в символьные вычисления 1.7.6 документация". homepages.math.uic.edu . Получено 2024-03-31 .
8. Neut, Sylvain; Petitot, Michel; Dridi, Raouf (2009-03-01). «Геометрическое видение Эли Картана или как избежать раздувания выражений». Journal of Symbolic Computation . Решение полиномиальных систем в честь Дэниела Лазара. 44 (3): 261–270. doi :10.1016/j.jsc.2007.04.006. ISSN  0747-7171.
9. Ричард Лиска Выражение swell, из "Особенности программирования в системах компьютерной алгебры"
10. «Ядро Mathematica: проблемы проектирования и реализации». Октябрь 2006 г. Получено 29 ноября 2023 г.
11. "Библиотека GNU Multiple Precision (GMP)". Maplesoft . Получено 29.11.2023.
12. Кэссиди, Кевин Г. (декабрь 1985 г.). Возможность автоматического освобождения памяти с параллельным выполнением программ в среде LISP (PDF) (магистерская диссертация). Военно-морская аспирантура, Монтерей/Калифорния. стр. 15. ADA165184.
13. Macsyma Mathematics and System Reference Manual (PDF) . Macsyma . 1996. стр. 419.
14. Бухбергер, Бруно; Лоос, Рюдигер (1983). "Алгебраическое упрощение" (PDF) . В Бухбергер, Бруно; Коллинз, Джордж Эдвин; Лоос, Рюдигер; Альбрехт, Рудольф (ред.). Компьютерная алгебра: символические и алгебраические вычисления . Computing Supplementa. Том 4. стр. 11–43. doi :10.1007/978-3-7091-7551-4_2. ISBN 978-3-211-81776-6.
15. Дэвенпорт, Дж. Х.; Сирет, И.; Турнье, Э. (1988). Компьютерная алгебра: системы и алгоритмы для алгебраических вычислений . Академический. ISBN 0-12-204230-1. OCLC  802584470.
16. "ENIAC in Action: What it Was and How it Worked". ENIAC: Celebrating Penn Engineering History . Университет Пенсильвании. Получено 3 декабря 2023 г.
17. Лайт, Дженнифер С. (1999). «Когда компьютеры были женщинами». Технология и культура . 40 (3): 455–483. doi :10.1353/tech.1999.0128. ISSN  1097-3729.
18. Маккарти, Джон (1 апреля 1960 г.). «Рекурсивные функции символических выражений и их вычисление машиной, часть I». Сообщения ACM . 3 (4): 184–195. doi : 10.1145/367177.367199 . ISSN  0001-0782.
19. Wexelblat, Richard L. (1981). История языков программирования . Серия монографий ACM. Конференция по истории языков программирования, Ассоциация вычислительной техники. Нью-Йорк Лондон Торонто: Academic Press. ISBN 978-0-12-745040-7.
20. "Symbolic Computation (An Editorial)". Журнал Symbolic Computation . 1 (1): 1–6. 1985-03-01. doi :10.1016/S0747-7171(85)80025-0. ISSN  0747-7171.
21. Фельдман, Стюарт И. (1 ноября 1975 г.). «Краткое описание Альтрана». ACM SIGSAM Bulletin . 9 (4): 12–20. doi :10.1145/1088322.1088325. ISSN  0163-5824.
22. Kaltofen, E. (1983), Buchberger, Bruno; Collins, George Edwin; Loos, Rüdiger; Albrecht, Rudolf (ред.), «Факторизация многочленов», Computer Algebra , Computing Supplementa, т. 4, Вена: Springer Vienna, стр. 95–113, doi :10.1007/978-3-7091-7551-4_8, ISBN 978-3-211-81776-6, получено 29.11.2023

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

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

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

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

• Davenport, James H .; Siret, Yvon; Tournier, Èvelyne (1988). Computer Algebra: Systems and Algorithms for Algebraic Computation . Перевод с французского A. Davenport и JH Davenport. Academic Press. ISBN 978-0-12-204230-0.
• фон цур Гатен, Иоахим; Герхард, Юрген (2003). Современная компьютерная алгебра (2-е изд.). Издательство Кембриджского университета. ISBN 0-521-82646-2.
• Геддес, КО; Цапор, СР; Лабан, Г. (1992). Алгоритмы для компьютерной алгебры . Bibcode : 1992afca.book.....G. doi : 10.1007/b102438. ISBN 978-0-7923-9259-0.
• Бухбергер, Бруно; Коллинз, Джордж Эдвин; Лоос, Рюдигер; Альбрехт, Рудольф, ред. (1983). Компьютерная алгебра: символические и алгебраические вычисления . Computing Supplementa. Том 4. doi :10.1007/978-3-7091-7551-4. ISBN 978-3-211-81776-6. S2CID  5221892.