Algebraic Approximations

I. INTRODUCTION

There are several artificial intelligence domains, such as electronic circuit analysis or chemical engineering, where handling symbolic mathematics is important. While symbolic mathematics packages exist [l) they often prove inadequate to handle the complexity of the symbolic expressions in such domains [2]. This paper proposes some techniques for using assumptions about relative magnitudes to simplifyexpressions while maintaining a known degree of accuracy. There is a strong analogy between the proposed technique and the use of exponential notation in the approximate represen­ tation of real numbers.

The necessity of making assumptions about the relative sizes of the values of variables intro­ duces the possibility that they will be proven wrong during the course of solving some set of equations. Thus a truth maintenance system [3) [4) may prove useful in keeping track of the assumptions underlying specific simplifications and solutions. The number of assumptions needed can be reduced by employing constraint propagation [5) as a primary technique for solving equations.

II, ALGEBRAIC SI!-IPLIFICATION

The first step in defining an "n significant figure representaion" is to define a canonical polynomial as either an integ~r consa~rt, a variable, or a polynomial a 0 x + a 1 x + ... +an where a 0 is not 0 and none of the coefficints a 1 contain the variable x. Notice that every canonical polynomial other than 0 takes on a non-zero value for some (in fact most) interpretations of its variables.

Some way of discussing the relative sizes of variables is needed. Each variable x is associated with an order o(x) which is some power of ten. It is assumed that x takes on values near o(x). The order function o can be extended to all non-zero canonical polynomials p in such a way that the magnitudes of the values p takes on are usually near o(p); The order o(p) of a non-zero canonical polynomial p is defined to be o(x) for a variable x, 1 for an integer constant, and the maximum of the orders of the non-zero terms for a polynomial of the ag~ye form, where the order of ~-~on-zero term aix is defined to be o(ai)o(x) · A canonical polynomial is called minimal if it is a

David A. McAllester

Artificial Intelligence Laboratory Massachusetts Institute of Technology

variable, an integer constant, or if all of its non-zero terms are of the same order and each coefficient of each term is minimal. A minimal polynomial can be thought of as containing only that information relevant to determining the value of the polynomial to within ten percent.

An n significant figure polynomial expansion is a pair ((p 0 , p 1 , ... p) e) of ann-tuple of minimal canonical polynomYals and an integer e such th~~ifor each pi either p 1 · equals 0 or o(p 1 ) equals 10 . Such an expansion Is considered equivalent to the expression p 0 + p 1 + ... + p . There is a strong analogy between n significan~ figure poly­ nomial expansions and n significant figure expon­ ential notaion representations of real numbers. Finally an n significant figure representaion is defined to be a ratio of two n significant figure polynomial expansions and therefore has the follow­ ing form:

The truncation of an m significant figure rep­ resentaion to an n significant figure representation is defined in the obvious way as the result of dropping m-n low order terms form the numerator and denominat~r. An n significant figure representation is called an n significant figure approximation of an arbitrary rational expression S if it is a trun­ cation of an m significant figure representation which is exactly equivalent to S.

An expression containing real numbers can be approximately evaluated using procedures which add, subtract, multiply and divide n significant figure approximations of reals. The approximate simplific­ ation of rational algebraic expressions can be done in the same way using procedures which add, sub­ tract, multiply and divide the n significant figure representations defined above. It is relatively straightforward to define procedures which compute a canonical polynomial equivalent to the sum, dif­ ference, or product of two canonical polynomials. From these one can construct procedures which com­ pute n significant figure approximations to the sum, difference, product or quotient of two n significant figure representations. As opposed to standard num­ eric operations these symbolic simplification proc­ edures never perform carries.

To fully define an n significant figure simp­ lification procedure it remains only t o s pecify n significant figure representations of numeric cons­ tants and variables. A variable x can be represented as the ratio:

Finally any real number can be approximate ly represented as the ratio of ((k 0 , k , ... k) e) to i, where each ki is some small iAtegral Multiple of an appropriate power of ten.

As an example consider the 2 s ignificant figure simplification of the expression:

This is the expression for theequivalent res ­ istance of two resist2rs in parallel. As sume that 2 the order of r is 10 while the order of r is 10 Thus r 2 is muc~ smaller than r 1 and the equtvalent resistance of these two in parHllel should be rough­ ly r 2 . The following series of expressions shows some of the intermediate states of a simplification of this expression.

The final form of this expression indicates the need for some mechanism to remove common factors of the numerator and denominator. Such procedures exist [6] and can be readily incorporated into this framework.

One important application of approximate simp­ lification techniques is the symbolic analysis of complex electronic circuits. Any circuit composed of linear elements can be described by a matix equation Ge ~ i where G is an admittance matrix, e is a vector of node potentials, and i is a vector of currents. It is often impracticle to compute the exact symbolic solution to such an equation because of the complexity of the exact symbolic inverse of G. It is hoped that by using approximate symbolic arithmetic operations the symbolic computation of matrix inverses will become practical.

III. EQUATIONS, ASSUMPTIONS AND TRUTH MAINTENANCE

Often one is interested in solutions to comp­ lex non-linear equations. For example consider the equation:

-5 Suppose that a is very small, about 10 . If x is assumed to be on the order of 1 then by dropping unimportant terms form the equation it can be shown that x is almost_~xactly 1. Similarly if x is assumed to be about 10 then it can be shown that x is a!T8st exactly a, while fo~ x on the order of 10 x is almost exactly a . Such techniques, though well known in engineering and applied mathematics [7], have not been incorpora t ed into computer symbolic mathematics packages.

In general an expression which is constrained to be zero can be simplified to an n significant figure approximation. To solve for a variable x the the expression should be put in the form ax + b where a and b are n significant figure polynomial expansions. Then x can be set equal to the n sign­ ificant figuresimplification of -b/a. If the original expression can't be simplified to the des ired form it may still be possible to simplify it to a product expressions each of which is linear in x. In this case one factor must be zero and each factor can be used to give a possible value for x. Only those solutions which are of a size consistent with the assumed size of x are viable and if there are no such solutions then the assumption about the size of x must be retracted and some other size tried (perhaps the size of one of the solutions for x).

This technique can be extended to systems of equations by employing Gaussian elimination. First an assumed order o(x) is associated with each variable x. Then the equations are solved one at a time, each time for a variable which has not yet been solved for. It is possible that during this process some subset of assumptions about the orders of variables is shown to be Inconsistent. When this happens an assumption must be retracted and th<· simplifications and solutions which depended on that assumption must be redone. A truth maintenance system [3) [4) could prove useful in keeping track of which simplifications and solutions depend on which assumptions.

Simplifications would be less sensitive to changes in the assumed size of variables if they could be based on assumptions of the form "the order of x is less than the order of y" rather than assumptions about the specific sizes of varibles. A truth maintenance system might again prove useful in keeping track of which simplifications remain valid when assumptions change.

Constraint propagation is a technique for solving sets of equations [5]. In constraint prop­ agation some subset of variables are a-priori chosen to be "independent" while others are chosen to be "dependent". Dependent variables are elimin­ ated when they can be expressed directly in terms of independent variables via some exact manipul­ ation of a single equation. Once an exact value for a dependent variable is found it can be simp­ lified to an n significant figure approximation (the simplification of exact values can be very expensive without the use of approximations). This has the advantage that assumptions about the sizes of the dependent variables do not need to be made.

It has the disadvantage that not every set of equations can be solved in this way. It would appear that some mixture of constraint propagation and other techniques would be optimal for solving sets of equations under order of magnitude assump­ tions about variable sizes.