AlgebraStructuresDoc.tioga
Dennis Arnon, June 6, 1986 4:15:42 pm PDT
AlgebraStructures
CEDAR 6.0 — FOR INTERNAL XEROX USE ONLY
AlgebraStructures
Dennis Arnon
© Copyright 1986 Xerox Corporation. All rights reserved.
Abstract: AlgebraStructures is a package for building complex algebraic structures and computing with their elements. For the user, there is a "desk calculator" type tool, which currently offers INTs, BigRats, REALs, and Complex Numbers as built-in ground types, and polynomial, matrix, and extension field constructors. For example, one can quickly read in and do simple arithmetic on matrices of polynomials with complex number coefficients. These same facilities are available to the client, in the form of interfaces exporting the built-in ground types, and interfaces providing generic polynomial, matrix, and extension field operations. The polynomial constructor implements multivariate polynomials (with somewhat nice I/O conversions). The matrix constructor implements square matrices. The extension field constructor implements real and general algebraic number fields.
Created by: Dennis Arnon
Maintained by: Dennis Arnon <Arnon.pa>
Keywords: Algebra, Polynomials, Matrices, Extension Fields, BigRats, Complex Numbers, Type Generic, Object-Oriented Programming, BigCardinals
XEROX   Xerox Corporation
    Palo Alto Research Center
    3333 Coyote Hill Road
    Palo Alto, California 94304

For Internal Xerox Use Only
1. Introduction
To start up the tool, do "Run AlgebraStructures". You will see four rows of buttons.
At any point in time, AlgebraStructures has the concept of a "current structure". You use AlgebraStructures by building the current structure you want, then reading in elements of that structure and operating on them.
Bug one of the Ints, BigRats, Reals, or Complexes buttons to set the current structure to the corresponding number domain. Each time the current structure is reset, a message appears. For example, if we bug BigRats, we get a message
Global Structure is (Field) BigRats
The format for complex numbers is illustrated by this example: (-38368.0 + 22976.0 i ).
The remaining buttons in the first row are for constructing a new structure that is the ring of polynomials in specified variables, whose coefficients are elements of the current structure. First set the current "variable sequence" (see section on this below), then bug PolyRing. For example, setting variable sequence to (x) produces the message
Variables = (x),
and if we now bug PolyRing now, we get the message
Global Structure is (Ring) Polynomials in (x) over BigRats
See the section below on IO representation of polynomials for required format for elements of polynomial rings. The PolynomialDiff button is differentiation.
Let's talk now about the last row of buttons. AlgebraStructures keeps two variables, denoted XXX and YYY. Bugging one of these means you want to read in an element of the current structure, a valid external representation for which is assumed to be the current selection. The remaining buttons in this row are arithmetic ops on XXX and YYY. Binary ops have the semantics XXX ← XXX op YYY, unary ops are XXX ← op XXX. The SetScalar button only has meaning if the current structure is a matrix ring or an extension field. Bugging it then trys to read a valid scalar from the current selection. Having set a scalar, bugging ScalarMult will multiply XXX by it and assign the result to XXX.
You will notice that output is rather one-dimensional. This at least has the virtue that we can support the principle that anything produced as output can subsequently be selected as input.
The second row of buttons is for creating a new structure that is the ring of square matrices of specified size, whose entries are elements of the current structure. First set a (CARDINAL-valued) matrix size by bugging MatrixSize, then bug MatrixRing to reset the current structure. For example, if current structure is Polynomials in (x) over Complexes, and if we have specified 2 x 2 matrices, then bugging MatrixRing produces the message
Global Structure is (Ring) 2 x 2 Matrices over Polynomials in (x) over Complexes
The following illustrates the external format of such a matrix:
[ [ x $, (1.0 + 1.0 i ) x^12 + (0.0 - 1.0 i ) $] , [ x^3 $, x $] ]
MatrixTranspose, MatrixDeterminant, and MatrixInvert operate on XXX.
The third row of buttons is for extension fields. Let's create the complex numbers as an extension of BigRats. First set current structure to polynomials in i over BigRats:
Global Structure is (Ring) Polynomials in (i) over BigRats
Now set XXX to i^2 + 1:
i^2 + 1 $
Now bug GenAlgNum. This creates the algebraic number i, i.e. the square root of -1. Now bug GenExtField. This creates the algebraic number field Q(I):
Global Structure is (Division Algebra) Extension of BigRats by root of i^2 + 1 $
Now we can enter and manipulate complex numbers, as polynomials in i. For example, if we input the polynomial [ i^7 + 33/16 i^6 - 3 i + 1 ] (note that elements of algebraic number fields are polynomials enclosed in square brackets without a dollar sign), we get:
[ - 4 i - 17/16 ]
which is the canonical representation of this complex number.
Let us create the real algebraic number field Q(sqrt(2)), where sqrt(2) denotes the positive root. We set current structure to polynomials in x over BigRats:
Global Structure is (Ring) Polynomials in (x) over BigRats
Now set XXX to x^2 - 2:
x^2 - 2 $
Now set an isolating interval for the positive square root of two. This is an interval with rational endpoints containing the root we want, for example: ( 9/8, 15/8 ). Now bug RealAlgNum, to create the algebraic number. This produces the printout:
x^2 - 2 $
( 9/8 , 15/8 )
Now bugging RealExtField creates the number field:
Global Structure is (Division Algebra) Extension of BigRats by the unique root of x^2 - 2 $ in ( 9/8 , 15/8 )
2. Variable Sequences
For any polynomial, we need to keep track of 'what variables it's a polynomial in'. This is accomplished by associating a variable sequence with the polynomial. This is a sequence of Ropes (the variables). In order for scanning to work, variables should be Cedar identifiers. A variable sequence 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 sequence 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 "**". Order of occurrence of variables in a term doesn't matter (no duplicate monomials allowed, however). For example, with variable sequence "(x,y,z)", the following is a legal polynomial with BigRat coefficients:
x z^33 - 92837498279872983749734 / 33 y**23 + x y z - 1 $
Error if a variable not in the variable sequence 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 simplification currently supported in input.