Computer algebra: Difference between revisions

Revision as of 15:39, 28 December 2022

Revision as of 20:40, 28 December 2022

Line 2:

{{Lead extra info|date=May 2020}}

[[File:RischIntegration.PNG|thumb|500px|[[Symbolic integration]] of the [[algebraic function]] {{math|1=''f''(''x'') = {{sfrac|''x''|{{sqrt|''x''⁴ + 10''x''² -− 96''x'' -− 71}}}}}} using the computer algebra system ''[[Axiom (computer algebra system)|Axiom]]'']]

In [[mathematics]] and [[computer science]],<ref>{{Cite web |title=ACM Association in computer algebra |url=https://www.sigsam.org/cca/}}</ref> '''computer algebra''', also called '''symbolic computation''' or '''algebraic computation''', is a scientific area that refers to the study and development of [[algorithm]]s and [[software]] for manipulating [[expression (mathematics)|mathematical expressions]] and other [[mathematical object]]s. Although computer algebra could be considered a subfield of [[scientific computing]], they are generally considered as distinct fields because scientific computing is usually based on [[numerical computation]] with approximate [[floating point number]]s, while symbolic computation emphasizes ''exact'' computation with expressions containing [[variable (mathematics)|variable]]s that have no given value and are manipulated as symbols.

Line 39:

==== Expressions ====

[[File:Cassidy.1985.015.gif|thumb|400px|Representation of the expression {{math|(8- − 6)&times; × (3 + 1)}} as a [[Lisp (programming language)|Lisp]] tree, from a 1985 Master's Thesis.<ref>{{cite thesis | type=Master's thesis | url=https://commons.wikimedia.org/wiki/File:The_feasibility_of_automatic_storage_reclamation_with_concurrent_program_execution_in_a_LISP_environment._(IA_feasibilityofaut00cass).pdf | author=Kevin G. Cassidy | title=The Feasibility of Automatic Storage Reclamation with Concurrent Program Execution in a LISP Environment | institution=Naval Postgraduate School, Monterey/CA | date=Dec 1985 }} Here: p.15</ref>]]

Except for [[number]]s and [[variable (mathematics)|variables]], every [[Expression (mathematics)|mathematical expression]] may be viewed as the symbol of an operator followed by a [[sequence]] of operands. In computer algebra software, the expressions are usually represented in this way. This representation is very flexible, and many things that seem not to be mathematical expressions at first glance, may be represented and manipulated as such. For example, an equation is an expression with "=" as an operator, a matrix may be represented as an expression with "matrix" as an operator and its rows as operands.

Even programs may be considered and represented as expressions with operator "procedure" and, at least, two operands, the list of parameters and the body, which is itself an expression with "body" as an operator and a sequence of instructions as operands. Conversely, any mathematical expression may be viewed as a program. For example, the expression {{math|''a'' + ''b''}} may be viewed as a program for the addition, with {{mvarmath|''a''}} and {{mvarmath|''b''}} as parameters. Executing this program consists in ''evaluating'' the expression for given values of {{mvarmath|''a''}} and {{mvarmath|''b''}}; if they doare not havegiven anyant value—that is they are indeterminates—values, the result of the evaluation is simply its input.

This process of delayed evaluation is fundamental in computer algebra. For example, the operator "=" of the equations is also, in most computer algebra systems, the name of the program of the equality test: normally, the evaluation of an equation results in an equation, but, when an equality test is needed,—either either explicitly asked by the user through an "evaluation to a Boolean" command, or automatically started by the system in the case of a test inside a program—thenprogram, then the evaluation to a boolean 0 or 1result is executed.

As the size of the operands of an expression is unpredictable and may change during a working session, the sequence of the operands is usually represented as a sequence of either [[Pointer (computer programming)|pointers]] (like in [[Macsyma]]) or entries in a [[hash table]] (like in [[Maple (software)|Maple]]).

Line 52:

The raw application of the basic rules of [[derivative|differentiation]] with respect to {{math|''x''}} on the expression <math>a^x</math> gives the result

:<math> x\cdot a^{x-1}\cdot 0 + a^x\cdot \left (1\cdot \log a + x\cdot \frac{0}{a} \right).</math>

SuchA a complicatedsimpler expression than this is clearlygenerally not acceptabledesired, and a procedure of simplification is needed as soon as onewhen worksworking with general expressions.

This simplification is normally done through [[rewriting|rewriting rules]].<ref>Buchberger, Bruno, and Rüdiger Loos. "[https://www.risc.jku.at/people/buchberg/papers/1982-00-00-B.pdf Algebraic simplification]." Computer algebra. Springer, Vienna, 1982. 11-43.</ref> There are several classes of rewriting rules that have to be considered. The simplest consists in the rewritingare rules that always reduce the size of the expression, like {{math|''E'' &minus; ''E'' → 0}} or {{math|sin(0) → 0}}. They are systematically applied in computer algebra systems.

The firstA difficulty occurs with [[associative operation]]s like addition and multiplication. The standard way to deal with associativity is to consider that addition and multiplication have an arbitrary number of operands, that is that {{math|''a'' + ''b'' + ''c''}} is represented as {{math|"+"(''a'', ''b'', ''c'')}}. Thus {{math|''a'' + (''b'' + ''c'')}} and {{math|(''a'' + ''b'') + ''c''}} are both simplified to {{math|"+"(''a'', ''b'', ''c'')}}, which is displayed {{math|''a'' + ''b'' + ''c''}}. WhatIn aboutthe case of expressions such as {{math|''a'' &minus; ''b'' + ''c''}}? To deal with this problem, the simplest way is to systematically rewrite systematically {{math|&minus;''E''}}, {{math|''E'' &minus; ''F''}}, {{math|''E''/''F''}} as, respectively, {{math|(&minus;1)⋅''E''}}, {{math|''E'' + (&minus;1)⋅''F''}}, {{math|''E''⋅''F''^&minus;1}}. In other words, in the internal representation of the expressions, there is no subtraction nor division nor unary minus, outside the representation of the numbers.

A secondAnother difficulty occurs with the [[commutativity]] of addition and multiplication. The problem is to quickly recognize quickly the [[like terms]] in order to combine or cancel them. In fact, the method for finding like terms, consisting of testingTesting every pair of terms, is too costly for being practicable with very long sums and products. ForTo solvingaddress this problem, [[Macsyma]] sorts the operands of sums and products withinto aan function of comparisonorder that is designed in order thatplaces like terms are in consecutive places, andallowing thuseasy easily detecteddetection. In [[Maple (software)|Maple]], thea [[hash function]] is designed for generating collisions when like terms are entered, allowing the to combinebe themcombined as soon as they are introduced. This design of the hash function allows also to recognize immediately the expressions or subexpressions that appear several times in a computation and to storebe themimmediately recognized and stored only once. This allows not only to save somesaves memory spaceand but also to speedspeeds up computation, by avoiding repetition of the same operations on several identical expressions.

Some rewriting rules sometimes increase and sometimes decrease the size of the expressions to which they are applied. This is the case of [[distributivity]] or [[Trigonometric identity#Product-to-sum and sum-to-product identities|trigonometric identities]]. For example, the distributivity law allows rewriting <math>(x+1)^4 \rightarrow x^4+4x^3+6x^2+4x+1</math> and <math>(x-1)(x^4+x^3+x^2+x+1) \rightarrow x^5-1.</math> As there is no way to make a good general choice of applying or not such a rewriting rule, such rewritingsrewriting areis done only when explicitly asked forinvoked by the user. For the distributivity, the computer function that applies this rewriting rule is generallytypically called "expand". The reverse rewriting rule, called "factor", requires a non-trivial algorithm, which is thus a key function in computer algebra systems (see [[Polynomial factorization]]).

== Mathematical aspects ==

In this section we consider someSome fundamental mathematical questions that arise as soon aswhen one wants to manipulate [[expression (mathematics)|mathematical expressions]] in a computer. We consider mainly the case of the [[Multivariate polynomial|multivariate]] [[rational fraction]]s. This is not a real restriction, because, as soon as the [[irrational function]]s appearing in an expression are simplified, they are usually considered as new indeterminates. For example,

:<math>(\sin(x+y)^2+ \log(z^2-5))^3</math>

is viewed as a polynomial in <math>\sin(x+y)</math> and <math>\log(z^2-5)</math>

=== Equality ===

There are two notions of equality for [[expression (mathematics)|mathematical expressions]]. The '''syntacticSyntactic equality''' is the equality of the expressions which means that they are written (ortheir representedrepresentation in a computer) in the same way. Being trivial, the syntactic equalityThis is rarely considered by mathematicians, although it is the only equality that is easy to test with ain program. The ''semanticSemantic equality'' is when two expressions represent the same mathematical object, likeas in

:<math> (x+y)^2=x^2+2xy+y^2.</math>

It is known from [[Richardson's theorem]] that there may not exist an algorithm that decides whether two expressions representing numbers are semantically equal, if exponentials and logarithms are allowed in the expressions. ThereforeAccordingly, (semanticalsemantic) equality may be tested only on some classes of expressions such as the [[polynomial]]s and [[rational fraction]]s.

To test the equality of two expressions, instead of designing specific algorithms, it is usual to put expressions in some ''[[canonical form]]'' or to put their difference in a ''normal form'', and to test the syntactic equality of the result.

UnlikeIn incomputer usual mathematicsalgebra, "canonical form" and "normal form" are not synonymous in computer algebra.<ref>Davenport, J. H., Siret, Y., & Tournier, É. (1988). Computer algebra. London: Academic.</ref> A ''canonical form'' is such that two expressions in canonical form are semantically equal if and only if they are syntactically equal, while a ''normal form'' is such that an expression in normal form is semantically zero only if it is syntactically zero. In other words, zero has a unique representation byas expressionsan expression in normal form.

Normal forms are usually preferred in computer algebra for several reasons. Firstly, canonical forms may be more costly to compute than normal forms. For example, to put a polynomial in canonical form, one has to expand byevery product through [[distributivity]] every product, while it is not necessary with a normal form (see below). Secondly, it may be the case, like for expressions involving radicals, that a canonical form, if it exists, depends on some arbitrary choices and that these choices may be different for two expressions that have been computed independently. This may make impracticable the use of a canonical form.

==History==