Skip to main content
main-content

Über dieses Buch

Algorithmic Algebra studies some of the main algorithmic tools of computer algebra, covering such topics as Gröbner bases, characteristic sets, resultants and semialgebraic sets. The main purpose of the book is to acquaint advanced undergraduate and graduate students in computer science, engineering and mathematics with the algorithmic ideas in computer algebra so that they could do research in computational algebra or understand the algorithms underlying many popular symbolic computational systems: Mathematica, Maple or Axiom, for instance. Also, researchers in robotics, solid modeling, computational geometry and automated theorem proving community may find it useful as symbolic algebraic techniques have begun to play an important role in these areas. The book, while being self-contained, is written at an advanced level and deals with the subject at an appropriate depth. The book is accessible to computer science students with no previous algebraic training. Some mathematical readers, on the other hand, may find it interesting to see how algorithmic constructions have been used to provide fresh proofs for some classical theorems. The book also contains a large number of exercises with solutions to selected exercises, thus making it ideal as a textbook or for self-study.

Inhaltsverzeichnis

Frontmatter

Chapter 1. Introduction

Abstract
The birth and growth of both algebra and algorithms are strongly intertwined. The origins of both disciplines are usually traced back to Muhammed ibn-Mūsa al-Khwarizmi al-Quturbulli, who was a prominent figure in the court of Caliph Al-Mamun of the Abassid dynasty in Baghdad (813–833 A.D.). Al-Khwarizmi’s contribution to Arabic and thus eventually to Western (i.e., modern) mathematics is manifold: his was one of the first efforts to synthesize Greek axiomatic mathematics with the Hindu algorithmic mathematics. The results were the popularization of Hindu numerals, decimal representation, computation with symbols, etc. His tome “al-Jabr wal-Muqabala,” which was eventually translated into Latin by the Englishman Robert of Chester under the title “Dicit Algoritmi,” gave rise to the terms algebra (a corruption of “al-Jabr”) and algorithm (a corruption of the word “al-Khwarizmi”).
Bhubaneswar Mishra

Chapter 2. Algebraic Preliminaries

Abstract
In this chapter, we introduce some of the key concepts from commutative algebra. Our focus will be on the concepts of rings, ideals and modules, as they are going to play a very important role in the development of the algebraic algorithms of the later chapters. In particular, we develop the ideas leading to the definition of a basis of an ideal, a proof of Hilbert’s basis theorem, and the definition of a Gröbner basis of an ideal in a polynomial ring. Another important concept, to be developed, is that of a syzygy of a finitely generated module.
Bhubaneswar Mishra

Chapter 3. Computational Ideal Theory

Abstract
In the previous chapter, we saw that an ideal in a Noetherian ring admits a finite Gröbner basis (Theorem 2.3.9). However, in order to develop constructive methods that compute a Gröbner basis of an ideal, we need to endow the underlying ring with certain additional constructive properties. Two such properties we consider in detail, are detachability and syzygy-solvability. A computable Noetherian ring with such properties will be referred to as a strongly computable ring.
Bhubaneswar Mishra

Chapter 4. Solving Systems of Polynomial Equations

Abstract
The Gröbner basis algorithm can be seen to be a generalization of the classical Gaussian elimination algorithm from a set of linear multivariate polynomials to an arbitrary set of multivariate polynomials. The S-polynomial and reduction processes take the place of the pivoting step of the Gaussian algorithm. Taking this analogy much further, one can devise a constructive procedure to compute the set of solutions of a system of arbitrary multivariate polynomial equations:
$$ \begin{array}{*{20}{c}} {{f_1}\left( {{x_1}, \ldots ,{x_n}} \right) = 0,} \\ {{f_2}\left( {{x_1}, \ldots ,{x_n}} \right) = 0,} \\ \vdots \\ {{f_r}\left( {{x_1}, \ldots ,{x_n}} \right) = 0,} \end{array} $$
i.e., compute the set of points where all the polynomials vanish:
$$ \left\{\langle\xi_{1},\ldots,\xi_{n}\rangle:f_{i}(\xi_{1},\ldots,\xi_{n})=0,\quad{\rm for}\ {\rm all}\ 1\leq i\leq r\right\}. $$
Bhubaneswar Mishra

Chapter 5. Characteristic Sets

Abstract
The concept of a characteristic sets was discovered in the late forties by J.F. Ritt (see his now classic book Differential Algebra [174]) in an effort to extend some of the constructive algebraic methods to differential algebra. However, the concept languished in near oblivion until the seventies when the Chinese mathematician Wu Wen-Tsün [209–211] realized its power in the case where Ritt’s techniques are specialized to commutative algebra. In particular, he exhibited its effectiveness (largely through empirical evidence) as a powerful tool for mechanical geometric theorem proving. This proved to be a turning point; a renewed interest in the subject has contributed to a better understanding of the power of Ritt’s techniques in effectively solving many algebraic and algebraico-geometric problems.
Bhubaneswar Mishra

Chapter 6. An Algebraic Interlude

Abstract
Before we move on to the topics of resultants and an algorithmic treatment of real algebra, we shall take a short pause to study in this chapter the unique factorization domain, the principal ideal domain, and the Euclidean domain. Of course, readers familiar with these topics may safely skip this chapter and go directly to the next chapter.
Bhubaneswar Mishra

Chapter 7. Resultants and Subresultants

Abstract
In this chapter we shall study resultant, an important and classical idea in constructive algebra, whose development owes considerably to such luminaries as Bezout, Cayley, Euler, Hurwitz, and Sylvester, among others. In recent time, resultant has continued to receive much attention both as the starting point for the elimination theory as well as for the computational efficiency of various constructive algebraic algorithms these ideas lead to; fundamental developments in these directions are due to Hermann, Kronecker, Macaulay, and Noether. Some of the close relatives, e.g., discriminant and subresultant, also enjoy widespread applications. Other applications and generalizations of these ideas occur in Sturm sequences and algebraic cell decomposition—the subjects of the next chapter.
Bhubaneswar Mishra

Chapter 8. Real Algebra

Abstract
In this chapter, we focus our attention on real algebra and real geometry. We deal with algebraic problems with a formulation over real numbers, ℝ (or more generally, over real closed fields). The underlying (real) geometry provides a rich set of mechanisms to describe such topological notions as “between,” “above/below,” “internal/external,” since it can use the inherent order relation (<) of the real (or, real closed) field. As a result, the subject has found many applications in such practical areas as computer-aided manufacturing, computational geometry, computer vision, geometric theorem proving, robotics, and solid modeling, etc., and thus has generated a renewed interest. We concentrate on the following key ingredients of real algebra: Sturm theory, algebraic numbers, and semialgebraic geometry.
Bhubaneswar Mishra

Backmatter

Weitere Informationen