Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top

1993 | Book

Introduction Read chapter Read first chapter

Algorithmic Algebra

Author: Bhubaneswar Mishra

Publisher: Springer New York

Book Series : Monographs in Computer Science

Included in: Professional Book Archive

Login to get access
insite
SEARCH

About this book

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.

Table of Contents

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
Metadata
Title
Algorithmic Algebra
Author
Bhubaneswar Mishra
Copyright Year
1993
Publisher
Springer New York
Electronic ISBN
978-1-4612-4344-1
Print ISBN
978-1-4612-8742-1
DOI
https://doi.org/10.1007/978-1-4612-4344-1