PolynomialsDoc.tioga
Dennis Arnon, December 20, 1985 2:47:35 pm PST
Polynomials
CEDAR 6.0 — FOR INTERNAL XEROX USE ONLY
Polynomials
Dennis Arnon
© Copyright 1985 Xerox Corporation. All rights reserved.
Abstract: Arithmetic of multivariate polynomials with exact, arbitrary precision rational coefficients. Somewhat nice I/O conversions.
Created by: Dennis Arnon
Maintained by: Dennis Arnon <Arnon.pa>
Keywords: Polynomials, Computer Algebra, BigCardinals, BigRats
XEROX Xerox Corporation
Palo Alto Research Center
3333 Coyote Hill Road
Palo Alto, California 94304
For Internal Xerox Use Only
1. Introduction
The client interface is Polynomials.mesa. A simple viewer tool (AlgebraImpl.bcd) is also provided.
2. Variable Lists
For any polynomial, we need to keep track of 'what variables it's a polynomial in'. This is accomplished by associating a variable list with the polynomial. This is a list of Ropes (the variables). In order for scanning to work, variables should be Cedar identifiers. A variable list should be written as comma-separated variables enclosed in parentheses (whitespace ok anywhere except within a variable). For example, "(x,y,z)".
3. IO (external) representation of polynomials
Once a variable list is established, a polynomial is written as a sequence of terms in the variables of that list, terminated by a " $" (leave a blank before the $). Order of terms doesn't matter. Multiplication is implicit (whitespace between coefficients and variables). Exponentiation is indicated by either "^" or "**". Coefficients can be either rational numbers or integers. Order of occurrence of variables in a term doesn't matter (no duplicate monomials allowed, however). For example, with variable list "(x,y,z)", the following is a legal polynomial:
x z^33 - 92837498279872983749734 / 33 y**23 + x y z - 1 $
Error if a variable not in the variable list occurs, but not all variables in the list need occur in any given polynomial. Case matters in variables. Order of occurrence of variables in a term doesn't matter.
No algebra (i.e. no recursive structure) currently supported in input.
4. The Tool
Run Algebraimpl.bcd, and you'll get an Algebra viewer. Select a variable list somewhere (other than the Algebra viewer, which is only for output), and click the VarList button. The variable list will be echoed back to you. Now you can input polynomials with this list. Select a polynomial somewhere, and click either Poly1 or Poly2 to set one of the two global operands. The results of arithmetic operations will be stored in Poly1.
5. Details of representations (only for those who care)
Distributed polynomial representation
The representation is (a1, d1, a2, d2, ...), where each ai is a nonzero coefficient, each di is a degree vector, and d1 > d2 > ... in the ordering of degree vectors established by DVCompare (see below).
If the variable list is (x1, x2, ..., xr), r >= 1, and the monomial is xi1^ei1 xi2^ie2 ... xik^eik,
with each ei positive, 0 <= k <= r, and i1 < i2 < ... < ik, the monomial's degree vector is (ik, ek, ik-1, ek-1, ..., i1, e1). Note the reversed ordering. Note also that a degree vector can have any length between zero (constant term) and 2r.
DVCompare:
PROC [dv1, dv2: DegreeVector]
RETURNS [ [-1..1] ] ~ {
index1, index2, exponent1, exponent2: CARDINAL;
WHILE dv1#
NIL
AND dv2#
NIL
DO
index1 ← dv1.first; dv1 ← dv1.rest;
exponent1 ← dv1.first; dv1 ← dv1.rest;
index2 ← dv2.first; dv2 ← dv2.rest;
exponent2 ← dv2.first; dv2 ← dv2.rest;
IF index1 > index2 THEN RETURN[1];
IF index1 < index2 THEN RETURN[-1];
IF exponent1 > exponent2 THEN RETURN[1];
IF exponent1 < exponent2 THEN RETURN[-1];
ENDLOOP;
IF dv1#NIL THEN RETURN[1];
IF dv2#NIL THEN RETURN[-1];
RETURN[0];
};
Recursive polynomial representation
exponent, reductum for nonconstant polynomials, decreasing order of exponents, last exponent may be zero.
External representation of formulas (not yet implemented)
A term is either an atomic formula
A = B
A < B
A <= B
A > B
A >= B
A ~= B
or a formula enclosed in parenthesis.
A formula is either
term
term & formula
term | formula (| has lower precedence than &)
An input formula is
formula $
Atomic formulas A op B are transformed internally (by the reader) into A - B op 0.