Symbolic mathematics

The Computer Algebra is the branch of mathematics and computer science that deals with the automated algebraic expressions, symbolic manipulation.

• 4.1 Efficient exact arithmetic with integers
• 4.2 Efficient exact arithmetic with rational numbers
• 4.3 Efficient exact arithmetic with polynomials in

Overview

The main objective of this sub-region it is ( or will not be allowed to rounding approximations ) by exact invoice transform algebraic expressions and to identify the most compact possible result. A constraint here is to make the algorithms used efficiently.

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

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

Practical application experience such results by using efficient algorithms in the development and improvement of computer algebra systems to enable the computer-aided manipulation of algebraic expressions. These systems are also an increasingly important tool for mathematicians and scientists from diverse disciplines.

Underlying structures

Unlike in the numerics, where with floating-point approximations of the numbers that occur is expected that computer algebra has the goal of always exactly expected. Accordingly, it is generally necessary to specify requirements for the underlying structures ( the rule groups, rings, or bodies).

Groups

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

Computable rings

A ring is called computable (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 finally
• Equality between two elements can be decided in finite time,
• There are algorithms with which the ring operations " " and "·" to be performed.

Examples

Predictable are about:

• Natural numbers
• The integers,
• The rational numbers,
• All forms of finite fields.

From a computable ring is more predictable rings can be constructed:

• Over polynomial rings,
• Rational functions,
• Matrices over
• All finite algebraic extensions of the above bodies,
• All finite transcendental extensions of the above body.

Formal objects

In the computer algebra of the underlying areas are next to the items still more "formal" objects considered such as

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

This is usually not the calculation of numerical values ​​, but for example, the determination of " closed formulas " as solutions.

Applications

In the applications of mathematical methods in science and technology traditionally available numerical methods in the foreground. With the symbolic methods of computer algebra to new applications have opened, which depend on accurate solutions and in which structure- mathematical considerations, such as the description of symmetries received; Furthermore, the treatment of problems that depend on uncertain parameters.

These include:

• In physics and its technological applications: Mixed symbolic- numerical calculations of complex problems in celestial mechanics, high energy physics ( Feynman integrals) and the theory of relativity ( 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 for the description of incommensurate modulated structures, quasicrystals and magnetic structures.
• In chemistry: applications of the representation theory to the classification of graphs of chemical compounds, in particular of isomers; Solution of large systems of equations for the determination of chemical reaction equilibria at variable reaction conditions, eg in combustion processes and exhaust gas regulation.
• In Security Systems: Algebraic methods of error detection and correction in message transmission; cryptographic encoding of information received in confidence by public-key method with methods of number theory and algebraic groups; Verification of security mechanisms ( protocols ).
• In robotics: motion planning and regulating autonomous robot, for example, in space; cylindrical algebraic decomposition of the cells; geometric image processing for machine vision.
• In computer-aided design (CAD ): Flexible inference systems for geometric modeling of parameterized problems; Construction of transitional surfaces.
• In the control theory: investigation of the stability and security of control systems with feedback.
• In genetic research: Classification of DNA structures.
• In training: computer algebra systems promise an improvement of mathematics education, since it becomes possible through their commitment to focus more on the lesson content. Furthermore, the treatment of more realistic application-related tasks is possible.

The methods of computer algebra in these applications allow an automatic treatment of problems that could only be laboriously tackled with ad hoc approaches otherwise. The great potential of these methods is by no means 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 integers

If you want to classify the time complexity of tasks and algorithms for exact arithmetic with integers, so first of all a computer model must be used. A discussion of various computer models can be found in the chapter complexity. A relatively catchy model is the multi- tape Turing machine, a variant of the classical Turing machine that shows several bands, each with a write head. For complexity estimates with the Landau notation logarithm to an unspecified base is used as needed under the name. As a measure of the time the number of bit operations required is selected, which is made ​​dependent on the bit length of the input in Landau notation.

The precise mathematical specification of ( bit ) complexity for exact arithmetic with integers must first start with a precise definition of the bit length of an integer: If the number is not zero, then

Set; In addition, is defined. For the specific storage of an integer for at least one additional bit for the sign is needed.

The tasks of the sign determination, 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 to be mastered in linear time with. The n -shift is feasible.

A non-trivial result of the computer algebra is the recognition that the multiplication is faster than (corresponding to the multiplication algorithm naive ) detachably. An acceleration first reached Karatsuba with the Karatsuba algorithm; this was then recognized as a special case of a more general algorithms family, which are subsumed under the term Toom - Cook algorithm. Groundbreaking was then the Arnold Schönhage and Volker Strassen 1971 presented based on discrete Fourier transforms Schönhage -Strassen algorithm for which the authors themselves have a complexity

Who demonstrated. Considering how expensive is the " naive" multiplication algorithm, this complexity seems incredible "fast". Since the algorithm is however quite complex and difficult programmable, there is still no efficient implementation in a computer algebra system.

As the complexity of integer multiplication in the entire computer algebra of absolutely -reaching importance, is this a shorthand notation was

Introduced. Equipped with this "fast" integer multiplication now, the catalog of the basic arithmetic for arithmetic in such be completed follows: The task of calculating is feasible; for the ( simultaneous ) calculation of binomial coefficients is required. The integer division ( with quotient and remainder as a result ) are required

Requires the calculation of the greatest common divisor

In the same complexity is also predictable, ie the cofactors with will all be included.

Efficient exact arithmetic with rational numbers

Exact before arithmetic can be performed in concrete, only one canonical representation (representation ) must be found of rational numbers; This problem did not appear even on at the precise arithmetic of integers. Rational numbers are equivalence classes " meaning the same " breaks from integers; are, for example, and different representatives of the same rational number.

The most common canonical representation of rational numbers is defined by all common divisors are canceled out from the numerator and denominator: Every rational number is then uniquely by a reduced fraction

Representable. Is this definition taken once, includes any elementary operation in such as addition and multiplication necessarily the task of Herauskürzens the greatest common divisor of the numerator and denominator of the fraction result.

Thanks to the results of the exact arithmetic in all operations are thus in the complexity

Feasible. From hope to be able to accomplish the addition of rational numbers in linear complexity, we must here take leave.

Fortunately, the calculation of the greatest common divisor can be computed very efficiently using the Euclidean algorithm. The Euclidean algorithm plays at many points in the computer algebra in changing variants a supporting role.

Efficient exact arithmetic with polynomials in

It is sufficient in this case, consider the arithmetic in, since operations with rational polynomials can be returned by respectively factoring out the common denominator for operations with integer polynomials in an obvious way. For defining the polynomial (coefficients ) in length than the maximum of the lengths of the individual coefficients.

For the following run-time table of important computational problems in we put the following assumptions:

• The degree or further
• Of the length or further and,
• Next to be with bit length.

Then run the (according to bit complexity ) fastest previously known algorithms for the following duration table: