Computer algebra

The computer algebra is the branch of mathematics and computer science that deals with the automated symbolic manipulation algebraic employs expressions.

overview

The main goal of this sub-area is to transform algebraic expressions through exact calculations (rounding or approximations are not permitted) and to determine the most compact result possible. A secondary condition here is to design the algorithms used efficiently.

The disciplines of mathematics and computer science are closely interwoven in computer algebra, on the one hand via the complexity theory for analysis, on the other hand via software technology for the practical implementation of computer algebraic algorithms.

One focus is the exact calculation with whole , rational and algebraic numbers as well as with polynomials over these number spaces. Another application is the symbolic solving of equations of all kinds, the symbolic summation of series , the symbolic calculation of limit values and the symbolic differentiation and integration (also called algebraic integration ).

Such results find practical application through the use of efficient algorithms in the development and improvement of computer algebra systems that enable the computer-aided manipulation of algebraic expressions. These systems are also an increasingly important tool for mathematicians and scientists in a wide variety of disciplines.

Underlying structures

In contrast to numerics , where floating point approximations of the occurring numbers are used for calculation, computer algebra claims to always calculate exactly. Accordingly, it is fundamentally necessary to specify requirements for the underlying structures (usually groups , rings or bodies ).

groups

All finite groups can be represented in the computer, for infinite groups there are algorithms under certain conditions, e.g. for polycyclic groups .

Predictable Rings

A ring is called predictable (or "effective") if the following conditions apply:

• The elements of the ring can be represented on a computer, in particular the representation of the elements must be finite,
• Equality between two elements can be decided in finite time,
• there are algorithms with which the ring operations “+” and “·” can be carried out.

Examples

The following can be calculated:

• the natural numbers ${\displaystyle \mathbb {N} }$
• the whole numbers ${\displaystyle \mathbb {Z} }$
• the rational numbers ${\displaystyle \mathbb {Q} }$
• all forms of finite bodies .

Further calculable rings can be constructed from a calculable ring : ${\displaystyle R}$

• Polynomial rings over ${\displaystyle R}$
• Rational functions over ${\displaystyle R}$
• Matrices over ${\displaystyle R}$
• All finite algebraic extensions of the above fields,
• All finite transcendent extensions of the above bodies.

Formal objects

In computer algebra, in addition to the elements of the underlying areas, other “formal” objects are also considered, such as

• Integrals ,
• Rows ,
• ( formal ) power series ,
• Differential and difference equations (or operators).

As a rule, this is not about calculating numerical values, but rather, for example, determining “closed formulas” as solutions.

Applications

When applying mathematical methods in science and technology, numerical methods are traditionally in the foreground. With the symbolic methods of computer algebra, new areas of application have opened up in which exact solutions are important and in which structural mathematical considerations, e.g. B. to describe symmetries, go into; also the handling of problems that depend on indefinite parameters.

These include, for example:

• In physics and its technological applications: mixed symbolic-numerical calculations of complex problems in celestial mechanics , high-energy physics (Feynman integrals) and relativity theory ( differential geometry ); Integration and solution of differential equations in closed form; symbolic calculations in the algebras of quantum mechanics ; Classification of higher-dimensional crystallographic groups to describe incommensurably modulated structures, quasicrystals and magnetic structures.
• In chemistry : applications of representation theory to the classification of graphs of chemical compounds, especially isomers ; Solving large systems of equations to determine chemical reaction equilibria under variable reaction conditions, e.g. B. in combustion processes and exhaust gas regulation.
• In information security : algebraic methods of error detection and correction in message transmission; cryptographic coding of confidential messages by public key methods using methods of number theory and algebraic groups ; Verification of security mechanisms (protocols).
• In robotics : movement planning and regulation of autonomous robots e.g. B. in space travel ; cylindrical algebraic cell decomposition of ; geometrical image processing in machine vision . ${\displaystyle \mathbb {R} ^{n}}$
• In computer-aided design (CAD) : flexible inference systems for the geometric modeling of parameterized problems; Construction of transition surfaces.
• In control theory : Investigation of the stability and safety of control systems with feedback.
• In genetic research : classification of DNA structures.
• In training : Computer algebra systems promise an improvement in mathematics lessons, as their use makes it possible to concentrate more on the lesson content. It is also possible to handle more realistic application-related tasks.

The methods of computer algebra allow an automatic handling of problems in these application areas, which otherwise could only be tackled with difficulty with ad hoc approaches. The great potential of these methods is far from exhausted. Continuous promotion of these applications and the underlying algorithms combined with increasingly powerful hardware will give the field of computer algebra further development opportunities.

Complexity considerations

Efficient exact arithmetic with whole numbers

If one wants to classify the time complexity of tasks and algorithms for exact arithmetic with whole numbers , a computer model must first be used. A discussion of various computer models can be found in the chapter on complexity . A relatively catchy model is the multi-band Turing machine, a variant of the classic Turing machine that has several bands with one read / write head each. For complexity estimates with the Landau notation , a logarithm on an unspecified basis is used if necessary . The number of bit operations required is selected as a measure of the time, which in Landau notation is made dependent on the bit length of the input. ${\displaystyle \operatorname {log} }$ ${\displaystyle B>1}$

The precise mathematical specification of (bit) complexities for the exact arithmetic with whole numbers must first start with the precise definition of the bit length of a whole number: If the number is not zero, it becomes ${\displaystyle a\in \mathbb {Z} }$

${\displaystyle L(a):=\lfloor \log _{2}|a|\rfloor }$

set; is also defined. For the specific storage of a whole number, at least one bit is also required for the sign . ${\displaystyle L(0):=1}$

The tasks of the sign determination of the calculation of the negative and the absolute value generation are all in linear time with feasible; the addition and the comparison of two numbers are in linear time with handle to. The n shift is feasible in. ${\displaystyle \operatorname {sgn} (a),}$ ${\displaystyle -a}$ ${\displaystyle |a|}$ ${\displaystyle O(l)}$ ${\displaystyle l=L(a)}$ ${\displaystyle a+b}$ ${\displaystyle a<b}$ ${\displaystyle O(l)}$ ${\displaystyle l={\rm {max}}(L(a),L(b))}$ ${\displaystyle 2^{n}\cdot a}$ ${\displaystyle O(n+l)}$

A non-trivial result of computer algebra is the knowledge that the multiplication can be solved much faster than in (which corresponds to the naive multiplication algorithm). Anatoly Karazuba initially achieved an acceleration with the Karazuba algorithm ; this was then recognized as a special case of an even more general family of algorithms that are subsumed under the term Toom Cook algorithm . Groundbreaking was the Schönhage-Strassen algorithm presented by Arnold Schönhage and Volker Strassen in 1971, which is based on discrete Fourier transformations and for which the authors themselves have a complexity of ${\displaystyle a\cdot b}$ ${\displaystyle O\left(l^{2}\right)}$

${\displaystyle O(l\cdot \log \,l\cdot \log \,\log \,l)}$

proven. If you consider how complex the “naive” multiplication algorithm is, this complexity appears incredibly “fast”. However, since the algorithm is quite complex and difficult to program, there has not yet been an efficient implementation in a computer algebra system.

Since the complexity of integer multiplication is of absolute importance in all computer algebra, a short notation was used for this

${\displaystyle \psi (l):=O(l\cdot \log \,l\cdot \log \,\log \,l)}$

introduced. Equipped with this "fast" integer multiplication, the catalog of the basic arithmetic operations for arithmetic can now be completed as follows: The task of calculating can be carried out in; is required for the (simultaneous) calculation of the binomial coefficients . The whole number division (with quotient and remainder as a result) is required ${\displaystyle \mathbb {Z} }$ ${\displaystyle a^{n}}$ ${\displaystyle O\left(\psi (nl)\right)}$ ${\displaystyle {n \choose 0}\cdots {n \choose n}}$ ${\displaystyle O\left(n\cdot \psi (n)\right)}$ ${\displaystyle a/b}$

${\displaystyle O\left({\frac {l}{l_{m}}}\cdot \psi (l_{m})\right)}$.

The calculation of the greatest common divisor is needed ${\displaystyle {\rm {gcd}}(a,b)}$

${\displaystyle O\left(\left({\frac {l}{l_{m}}}+{\rm {log}}\,l_{m}\right)\cdot \psi (l_{m})\right)}$.

The same complexity is also calculable, i.e. H. the cofactors with are included in the calculation. ${\displaystyle {\rm {gcdex}}(a,b)}$ ${\displaystyle u,v}$ ${\displaystyle {\rm {gcd}}(a,b)=ua+vb}$

Efficient exact arithmetic with rational numbers

Before exact arithmetic can be carried out in concrete terms, a canonical representation of rational numbers must first be found; this problem did not arise with the exact arithmetic of integers. Rational numbers are equivalence classes of “meaningful” fractions from whole numbers; for example and are different representatives of the same rational number. ${\displaystyle \mathbb {Q} }$ ${\displaystyle {\frac {1}{2}}}$ ${\displaystyle {\frac {2}{4}}}$

The most common canonical representation of rational numbers is determined by removing all common factors from the numerator and denominator: Every rational number is then unambiguous by a reduced fraction

${\displaystyle {\frac {p}{q}}}$with and ${\displaystyle p\in \mathbb {Z} ,}$ ${\displaystyle q\in \mathbb {N} }$ ${\displaystyle {\rm {ggT}}(p,q)=1}$

representable. Once this determination has been made, every elementary operation such as addition and multiplication also necessarily includes the task of removing the greatest common divisor from the numerator and denominator of the fraction of the result. ${\displaystyle \mathbb {Q} }$

Thanks to the results of exact arithmetic in , the operations are all in complexity ${\displaystyle \mathbb {Z} }$ ${\displaystyle a+b,\quad a-b,\quad a\cdot b,\quad a/b}$

${\displaystyle O\left(\psi (l)\cdot {\rm {log}}\,l\right)}$

feasible. We have to say goodbye to the hope of being able to add rational numbers in linear complexity.

Fortunately, the calculation of the greatest common divisor can be calculated very efficiently using the Euclidean algorithm . The Euclidean algorithm plays a major role in many places in computer algebra in changing variants.

Efficient exact arithmetic with polynomials in ℚ [x]

It is sufficient to consider the arithmetic in , since operations with rational polynomials can be traced back to operations with integer polynomials in an obvious way by factoring out the main denominators. For polynomials , the (coefficient) length is defined as the maximum of the lengths of the individual coefficients. ${\displaystyle \mathbb {Z} \left[x\right]}$ ${\displaystyle f\in \mathbb {Z} [x]}$ ${\displaystyle L(f)}$

For the following runtime table of important calculation problems we assume the following: ${\displaystyle \mathbb {Z} [x]}$

• ${\displaystyle f,g\in \mathbb {Z} \left[x\right]}$
• from the degree or further , ${\displaystyle d_{f}=\deg f}$ ${\displaystyle d_{g}=\deg g,}$ ${\displaystyle d=\max(d_{f},d_{g}),\,d_{m}=\min(d_{f},d_{g})}$
• on the length or further and , ${\displaystyle l_{f}=L(f)}$ ${\displaystyle l_{g}=L(g),}$ ${\displaystyle l=\max(l_{f},l_{g})}$ ${\displaystyle l_{m}=\min(l_{f},l_{g})}$
• next to it is with bit length . ${\displaystyle a\in \mathbb {Z} }$ ${\displaystyle l_{a}=L(a)}$

Then the fastest algorithms known so far (according to bit complexity) lead to the following runtime table:

surgery	Complexity as ${\displaystyle O(\dots )}$	for unequal input sizes
${\displaystyle f+g}$	${\displaystyle d\,l}$	${\displaystyle d_{m}\,l}$
${\displaystyle f\cdot g}$	${\displaystyle \psi (d(l+\log d))}$	${\displaystyle {\frac {d}{d_{m}}}\,\psi (d_{m}((d-d_{m}+1)l+\log d))}$
${\displaystyle f/g}$ Division with remainder	${\displaystyle \psi (d(l+\log d))}$	${\displaystyle {\frac {dl}{d_{m}l_{m}}}\,\psi (d_{m}(l_{m}+\log d_{m}))}$
${\displaystyle \operatorname {prem} (f,g)}$	${\displaystyle -}$	${\displaystyle {\frac {d}{d_{m}}}\,\psi (d_{m}((d-d_{m}+1)l+\log d))}$
${\displaystyle f^{k}}$	${\displaystyle \psi (kd(l+\log d))}$	${\displaystyle -}$
${\displaystyle f(ax)}$ Scaling	${\displaystyle d\,\psi (l+dl_{a})}$	${\displaystyle -}$
${\displaystyle a^{d}f\left({\frac {x}{a}}\right)}$ Scaling	${\displaystyle d\,\psi (l+dl_{a})}$	${\displaystyle -}$
${\displaystyle f(2x)}$ Scaling	${\displaystyle d(l+d)}$	${\displaystyle -}$
${\displaystyle 2^{d}f\left({\frac {x}{2}}\right)}$ Scaling	${\displaystyle d(l+d)}$	${\displaystyle -}$

See also

• Symbolic math

literature

German-language literature:

• Michael Kaplan: Computer Algebra. Springer, Berlin et al. 2005, ISBN 3-540-21379-1 .
• Wolfram Koepf: Computer algebra. An algorithmic introduction. Springer, Berlin et al. 2006, ISBN 3-540-29894-0 .
• Attila Pethö : Algebraic Algorithms. Edited by Michael Pohst . Vieweg, Braunschweig et al. 1999, ISBN 3-528-06598-2 .

English-language literature:

• Peter Bürgisser , Michael Clausen , Mohammad Amin Shokrollahi : Algebraic Complexity Theory (= The basic teachings of the mathematical sciences in single representations. 315). Springer, Berlin et al. 1997, ISBN 3-540-60582-7 ( review ).
• Arjeh M. Cohen , Hans Cuypers, Hans Sterk: Some Tapas of Computer Algebra (= Algorithms and Computation in Mathematics. 4). Springer, Berlin et al. 1999, ISBN 3-540-63480-0 .
• David Cox , John Little , Donal O'Shea : Ideals, varieties, and algorithms. 2nd edition. Springer, New York NY et al. a. 1997, ISBN 0-387-94680-2 .
• Joachim von to Gathen , Jürgen Gerhard: Modern Computer Algebra. 2nd edition. Cambridge University Press, Cambridge et al. 2003, ISBN 0-521-82646-2 .
• Keith O. Geddes, Stephen R. Czapor, George Labahn: Algorithms for Computer Algebra. Kluwer, Boston MA et al. 1992, ISBN 0-7923-9259-0 .

Web links

• Specialist group for computer algebra , joint specialist group of GI , DMV and GAMM
• Sieveking: Algorithms of Computer Algebra . (PDF; 666 kB) Script, Goethe University Frankfurt a. M.