Skip to main content
Top

1996 | Book

Polynomial Algorithms in Computer Algebra

Author: Dipl.-Ing. Dr. Franz Winkler

Publisher: Springer Vienna

Book Series : Texts & Monographs in Symbolic Computation

insite
SEARCH

About this book

For several years now I have been teaching courses in computer algebra at the Universitat Linz, the University of Delaware, and the Universidad de Alcala de Henares. In the summers of 1990 and 1992 I have organized and taught summer schools in computer algebra at the Universitat Linz. Gradually a set of course notes has emerged from these activities. People have asked me for copies of the course notes, and different versions of them have been circulating for a few years. Finally I decided that I should really take the time to write the material up in a coherent way and make a book out of it. Here, now, is the result of this work. Over the years many students have been helpful in improving the quality of the notes, and also several colleagues at Linz and elsewhere have contributed to it. I want to thank them all for their effort, in particular I want to thank B. Buchberger, who taught me the theory of Grabner bases nearly two decades ago, B. F. Caviness and B. D. Saunders, who first stimulated my interest in various problems in computer algebra, G. E. Collins, who showed me how to compute in algebraic domains, and J. R. Sendra, with whom I started to apply computer algebra methods to problems in algebraic geometry. Several colleagues have suggested improvements in earlier versions of this book. However, I want to make it clear that I am responsible for all remaining mistakes.

Table of Contents

Frontmatter
1. Introduction
Abstract
In the recent decades it has been more and more realized that computers are of enormous importance for numerical computations. However, these powerful general purpose machines can also be used for transforming, combining and computing symbolic algebraic expressions. In other words, computers can not only deal with numbers, but also with abstract symbols representing mathematical formulas. This fact has been realized much later and is only now gaining acceptance among mathematicians and engineers.
Franz Winkler
2. Arithmetic in basic domains
Abstract
For the purposes of exact algebraic computation integers have to be represented exactly. In practice, of course, the size of the machine memory bounds the integers that can be represented. But it is certainly not acceptable to be limited by the word length of the machine, say 232.
Franz Winkler
3. Computing by homomorphic images
Abstract
The Chinese remainder method has already been investigated by Chinese mathematicians more than 2000 years ago. For a short introduction to the history we refer to Knuth (1981). The main idea consists of solving a problem over the integers by solving this problem in several homomorphic images modulo various primes, and afterwards combining the solutions of the modular problems to a solution of the problem over the integers. In fact, the method can be generalized to work over arbitrary Euclidean domains, i.e., domains in which we can compute greatest common divisors by the Euclidean algorithm. An interesting list of different statements of the Chinese remainder theorem is given in Davis and Hersh (1981).
Franz Winkler
4. Greatest common divisors of polynomials
Abstract
If K is a field, then K[x] is a Euclidean domain, so gcd(f, g) for f, gK[x] can be computed by the Euclidean algorithm. Often, however, we are given polynomials f, g over a domain such as ℤ or K[x1, …, xn-1] and we need to compute their gcd.
Franz Winkler
5 Factorization of polynomials
Abstract
Similar to what we have done for the computation of gcds of polynomials, we will reduce the computation of the factors of an integral polynomial to the computation of the factors of the polynomial modulo a prime number. So we have to investigate this problem first, i.e., we consider the problem of factoring a polynomial a(x) ∈ ℤp[x], p a prime number. W.l.o.g. we may assume that lc(a) = 1.
Franz Winkler
6. Decomposition of polynomials
Abstract
The first polynomial time algorithms for decomposition of polynomials have been presented by Gutierrez et al. (1988) and practically at the same time by D. Kozen and S. Landau (1989). We follow the approach of Kozen and Landau.
Franz Winkler
7. Linear algebra—solving linear systems
Abstract
Systems of linear equations over a field K can be solved by various methods, e.g., by Gaussian elimination or Cramer’s rule. But if we start with a system over the integers, we will immediately introduce rational numbers, whose arithmetic operations are clearly more costly than the corresponding operations on integers. So for the same reason as in the computation of gcds of polynomials or factorization of polynomials, we are interested in a method for solving systems of linear equations which avoids computation with rational numbers as much as possible. Such a method for fraction free Gaussian elimination is Bareiss’s algorithm, as described in Bareiss (1968).
Franz Winkler
8. The method of Gröbner bases
Abstract
Many of the properties that are important for Gröbner bases can be developed in the frame of binary relations on arbitrary sets, so-called reduction relations (Huet 1980). The theory of reduction relations forms a common basis for the theory of Gröbner bases, word problems in finitely presented groups, term rewriting systems, and lambda calculus.
Franz Winkler
9. Quantifier elimination in real closed fields
Abstract
Many interesting problems of the geometry over the real numbers can be stated as systems of polynomial equations, inequations, and inequalities, usually with some structure of quantification. For instance, in Sect. 1.1 the piano movers problem in robotics has been mentioned. There are many other application areas, e.g., stability conditions for difference schemes. Quantifier elimination provides an approach to solving such polynomial problems over the real numbers.
Franz Winkler
10 Indefinite summation
Abstract
The problem of indefinite summation is very similar to the problem of indefinite integration, in fact, we can somehow think of it as a discrete analogon to the integration problem. Whereas in integration we start out with a continuous function f(x) and want to determine another function g(x) such that in indefinite summation we are given a sequence (an)n∈ℕ and we want to determine another sequence (sn)n∈ℕ0 (in which the function symbol ∑ is eliminated) such that any partial sum of the corresponding series can be expressed as Of course we expect that the existence of algorithmic solutions for this indefinite summation problem will depend crucially on the class of functions that we take as input and possible output.
Franz Winkler
11. Parametrization of algebraic curves
Abstract
Algebraic geometry is the study of geometric objects defined as the zeros of polynomial equations. So it is not surprising that many of the techniques in algebraic geometry become computationally feasible once we have algorithmic solutions for the relevant problems in commutative algebra, i.e., the algebra of polynomial rings. We take a look at one particular problem in algebraic geometry, the rational parametrization of algebraic curves. For an introduction to algebraic curves we refer to Walker (1950) or Fulton (1969).
Franz Winkler
Backmatter
Metadata
Title
Polynomial Algorithms in Computer Algebra
Author
Dipl.-Ing. Dr. Franz Winkler
Copyright Year
1996
Publisher
Springer Vienna
Electronic ISBN
978-3-7091-6571-3
Print ISBN
978-3-211-82759-8
DOI
https://doi.org/10.1007/978-3-7091-6571-3