Elimination Practice

The following sections are included:

• Preface

• Contents

The central objects treated in this book are multivariate polynomials. The process of elimination allows one to eliminate variables from some polynomials by using others. This process may sometimes generate very large polynomials, so software tools are required to perform the involved calculations on computer. In this chapter, we use a number of simple examples to show how the elimination of variables works and how to use it to solve various kinds of problems.

The ϵPSILON Library refers to the collection of functions and routines written by the author and described in this book. The functions are implemented mostly in the Maple system on the basis of various elimination methods presented in [78]. Some of them are written for particular applications, for example, to geometric theorem proving. This chapter provides an overview on the implementation, functionality, and applicability of the library.

This chapter describes the CharSets package, which provides a complete and comprehensive implementation of Wu–Ritt's method of characteristic sets [98, 50]. Functions implemented in this package are capable of computing a characteristic set of a polynomial set in different senses, decomposing a polynomial set into ascending sets or irreducible ascending sets, decomposing an algebraic variety into irreducible subvarieties, decomposing a polynomial ideal into primary components, factorizing a polynomial over a successive algebraic extension field, and solving a system of polynomial equations and inequations. We present these functions, discuss some implementation strategies, and report on experimental results. Some of the functions are also extended to the case of ordinary differential polynomials.

The modules TriSys and SiSys presented in this chapter implement two elimination methods introduced by the author [63, 73, 77]. The functions available in these modules allow one to decompose any polynomial system into fine triangular systems (with or without projection), into regular systems, into simple systems, and into irreducible triangular systems, to decompose any algebraic variety into unmixed or irreducible subvarieties, and to solve any system of polynomial equations and inequations. Some of these functions perform the same tasks as the corresponding functions in the CharSets package, but the former are often more efficient.

The application module GEOTHER provides an environment for handling and proving theorems in geometry automatically. In this environment, geometric theorems are represented by means of predicate specifications. Several functions are implemented that allow one to translate the specification of a geometric theorem into an English or Chinese statement, into algebraic expressions, and into a logic formula automatically. Geometric diagrams can also be drawn automatically from the predicate specification, and the drawn diagrams may be modified and animated with a mouse click and dragging. Five algebraic provers based on Wu's method of characteristic sets, the Gröbner basis method, and other triangularization techniques are available for proving such theorems in elementary (and differential) geometry. Geometric meanings of the produced algebraic nondegeneracy conditions can be interpreted automatically, in most cases. PostScript and HTML files can be generated, also automatically, to document the manipulation and machine proof of the theorem. This chapter presents these capabilities of GEOTHER, addresses some implementation issues, and reports on the performance of GEOTHER's algebraic provers.

In this chapter we review other existing implementations of triangular-set-based algorithms in different programming languages and provide information about their capabilities and availability. Elimination tools that are slightly different from yet most relevant to our library are Gröbner bases packages, which are available in almost all popular computer algebra systems. We point out some of these systems and give a short introduction to the software packages Gb and FGb specialized for Gröbner bases computation. Another family of elimination tools, developed on the basis of classical and modern theories of resultants, will be discussed briefly. A few miscellaneous functions are also explained.

A straightforward and important application of elimination methods and tools is solving systems of polynomial equations and inequations. Such equation systems occur in diverse problems from many areas of science, engineering, and industry. In this chapter, we formulate a few general principles based on elimination techniques and apply them to solving algebraic equations and inequations in different situations. The considered polynomial systems may be zero-dimensional, or of positive dimension, or with parameters, as shown by several practical examples.

Automated theorem proving in geometry was a highlight of research, represented by the work of H. Gelernter [27] and his collaborators, in the early days of artificial intelligence. However, there had been no breakthrough until the later 1970s when W.-t. Wu introduced an algebraic method based on polynomial computation [85, 87]. After the surprising success of Wu's method, which has proved hundreds of nontrivial geometric theorems, automated deduction in geometry has witnessed two flourishing decades of development. Different algebraic methods based on characteristic and triangular sets, Gröbner bases, variable and point elimination, and Clifford algebra as well as other synthetic approaches using heuristic search and term-rewriting have been proposed, investigated, implemented, and applied to prove and discover theorems in elementary and differential geometries (see [13, 71, 98, 99] and http://www-calfor.lip6.fr/~wang/GRBib). This chapter presents some of the coordinate-based methods together with a number of examples, which serve to demonstrate the power of elimination techniques for geometric reasoning and to illustrate the proving machines built into GEOTHER.

Elimination techniques and tools have remarkable applications in modern engineering geometry. This chapter presents some of the applications to selected problems, such as automatic derivation of locus equations and inequations, implicitization of parametric objects, computation of quasi-offsets to curves and surfaces, blending of algebraic surfaces, and decomposition of algebraic varieties, from automated geometric reasoning and computer-aided geometric design and modeling.

Symbolic elimination methods provide constructive tools not only for algebraic geometry, but also for polynomial-ideal theory and many related problems in different areas of computer mathematics. Our elimination tools have natural applications in all such areas. In this chapter we consider some of the applications, more concretely to the problems of computing with polynomial ideals, factorizing multivariate polynomials, analyzing differential equations qualitatively, and reasoning about curves and surfaces automatically in differential geometry.

The following sections are included:

• Appendix A Polynomial Systems: 50 Test Examples

• Appendix B Algebraic Factorization: 55 Examples

• References

• Index