The Mathematica Journal
Departments
Feature Articles
Columns
New Products
New Publications
Classifieds
Calendar
News Bulletins
Mailbox
Letters
Write Us
About the Journal
Staff and Contributors
Submissions
Subscriptions
Advertising
Back Issues
Home
Download this Issue

Introduction

Mathematica 4.0 contains several new functions that allow systems of real algebraic equations and inequalities to be solved. In this article we describe the functions, show examples of their use, and comment on the algorithms used in their implementation. 

Let us first specify what is meant by a system of algebraic equations and inequalities, and what its solutions are.

An algebraic expression in variables [Graphics:../Images/index_gr_1.gif] is an expression constructed with [Graphics:../Images/index_gr_2.gif] and rational numbers, using addition, multiplication, rational powers, and the Root function. For instance, the following is an algebraic expression in variables x and y.

[Graphics:../Images/index_gr_3.gif]

A system of real algebraic equations and inequalities in variables [Graphics:../Images/index_gr_4.gif] is a logical combination of equations and inequalities with both sides being algebraic expressions in [Graphics:../Images/index_gr_5.gif]. For instance, the following is a system of algebraic equations and inequalities in variables x and y.

[Graphics:../Images/index_gr_6.gif]

Functions that solve systems of real algebraic equations and inequalities always use LogicalExpand first to put the system in the disjunctive normal form. For the remainder of this article, we assume that the systems are in the disjunctive normal form; that is, they are disjunctions of conjunctions of equations and inequalities.

A tuple [Graphics:../Images/index_gr_7.gif] of real numbers satisfies (or is a solution of) a system [Graphics:../Images/index_gr_8.gif] of real algebraic equations and inequalities in variables [Graphics:../Images/index_gr_9.gif] if there is at least one [Graphics:../Images/index_gr_10.gif], such that after replacing the [Graphics:../Images/index_gr_11.gif] with the [Graphics:../Images/index_gr_12.gif] all the radicals and Root objects in [Graphics:../Images/index_gr_13.gif] are real-valued and all the equations and inequalities in [Graphics:../Images/index_gr_14.gif] are satisfied.

What does it mean to "solve" a system of real algebraic equations and inequalities? The solutions form semialgebraic subsets of [Graphics:../Images/index_gr_15.gif]. These subsets are often infinite and, unlike complex algebraic sets, cannot be "generically" parametrized using a subset of variables. For instance, the set of solutions of

[Graphics:../Images/index_gr_16.gif]

is the following figure.

[Graphics:../Images/index_gr_17.gif]

[Graphics:../Images/index_gr_18.gif]

In many practical situations (e.g., geometric theorem proving using assumptions), we may need to check very simple properties of systems, like whether a system has any solutions at all, whether a system is always satisfied, or whether the set of solutions of one system is contained in the set of solutions of another system (the first system implies the second). All these problems are equivalent, and we describe functions solving them in the section "Decision Problem."

The set of solutions of any system of real algebraic equations and inequalities in variables [Graphics:../Images/index_gr_19.gif] can be decomposed into a finite number of "cylindrical" parts.

[Graphics:../Images/index_gr_20.gif]

In the above expression, [Graphics:../Images/index_gr_21.gif] is one of <, [Graphics:../Images/index_gr_22.gif], and [Graphics:../Images/index_gr_23.gif]; and [Graphics:../Images/index_gr_24.gif] and [Graphics:../Images/index_gr_25.gif] are [Graphics:../Images/index_gr_26.gif], [Graphics:../Images/index_gr_27.gif], or algebraic expressions in variables [Graphics:../Images/index_gr_28.gif] which are real-valued for all tuples of real numbers [Graphics:../Images/index_gr_29.gif] satisfying

[Graphics:../Images/index_gr_30.gif]

In the section "Solving Systems of Equations and Inequalities," we present functions which find solution sets of systems of real algebraic equations and inequalities. We represent these solutions in the cylindrical solution form, i.e., in the form of a finite number of disjoint cylindrical parts, with [Graphics:../Images/index_gr_31.gif] and [Graphics:../Images/index_gr_32.gif] being Root functions, rational functions, or functions of the form [Graphics:../Images/index_gr_33.gif] for rational functions a, b, and c.

A quantified system of real algebraic equations and inequalities in variables [Graphics:../Images/index_gr_34.gif] is an expression

[Graphics:../Images/index_gr_35.gif]

where [Graphics:../Images/index_gr_36.gif] is [Graphics:../Images/index_gr_37.gif] or [Graphics:../Images/index_gr_38.gif], and S is a system of real algebraic equations and inequalities in [Graphics:../Images/index_gr_39.gif].

By Tarski's theorem the solution sets of quantified systems of real algebraic equations and inequalities are semi-algebraic sets. The function Resolve, presented in the section "Quantifier Elimination," finds the solution sets and represents them in the cylindrical solution form.

Finally, we show new functions for global optimization of algebraic functions subject to algebraic equation and inequality constraints, and we comment on the algorithms used by the inequality solvers.


Converted by Mathematica      April 24, 2000

[Article Index] [Next Page]