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 an object-oriented package for building complex algebraic structures and computing with their elements. For example, one can quickly read in and do simple arithmetic on matrices of polynomials with complex number coefficients, or matrices of such matrices, ad infinitum.
Created by: Dennis Arnon
Maintained by: Dennis Arnon <Arnon.pa>
Keywords: Computer Algebra, Symbolic Mathematical Computation, Polynomials, Matrices, Object-Oriented Programming
XEROX Xerox Corporation
Palo Alto Research Center
3333 Coyote Hill Road
Palo Alto, California 94304
For Internal Xerox Use Only
1. Introduction
References: Scratchpad docs, Views.
1. Note on Single Set Structures
Currently the only case in which Eval will choose this sort of Structure for something it reads is for variables.
2. General steps for adding a new Structure
1. Update AlgebraStructures.df
2. Update CASDefs, CASImpls
3. Update AlgebraStructures.config
4. Make sure relevant editor display notations, if any, exist (Update InstallExprClasses, MathConstructors)
5. Update EnterAtom in ViewExprImpl to offer a notation for it, if appropriate. Make sure user interface can handle its operations (through functional notation as a minimum; perhaps through agreement of method names with notation names) (this ought not to be necessary; putting it in the database(s) with InstallExprClasses ought to be sufficient).
6. Update Eval and StructureLUB procs to know about this Structure.
2. Structure Names
Structures have (long) names which are also recipes for constructing them. These long names are stored with an element of that domain which is placed in a Tioga doc.
Structures have short names, intended to capture standard usage (e.g. Q[x, y]), which are, for example, displayed in a CaminoReal viewer to tell the user the domain of a certain object.
Default structure for all exprs is MeddleExpr's.
2. Structure Elements
There are two ways to get a structure element, i.e. to get an AlgebraStructures internal rep of an object belonging to a particular domain: convert an editor expression to AlgebraStructures internal rep (FromExpr op), or parse a ROPE into an AlgebraStructures internal rep.
3. ToExpr and FromExpr ops
Both should be available in every structure, and should be inverses of each other.
Thus note that, in particular, we assume that the editor offers sufficient (currently hardwired) display functions, and that for the elements of any AlgebraStructures structure, we can give a recipe for displaying it in terms of editor functionality.
3. TestDomain op
What this does is take an editor expression and check that, if evaluated, it will indeed be an element of the specified domain. Does no evaluation/simplification.
3. ImbedInDomain proc
There is a single such proc for the whole AlgebraStructures system.
Takes an editor expression and domain, and tries to evaluate the expression to an element of the specified domain. First does a TestDomain op. If that succeeds, then evaluates/simplifies the given editor expression to an AlgebraStructures internal rep for the value, and, by applying the ToExpr op of the structure, also returns an editor expression for the evaluated/simplified form.
For polynomials, is a highly recursive proc.
Has rules, for example if domain is Z and expr is Det(matrix of ints),
3. Structure Recast procs
Should always do something on general expr rep = meddle internal form. This is the proc that is applied when we assert that something we've created in the editor is an element of some domain. Does evaluation, e.g. if domain is ints, and expr is determinant of matrix of ints, should be able to check that determinant method exists in matrix structure, call matrix structure recast proc to convert Should work recursively, i.e. when applied to a poly, knows to call coeffRing recast proc on coefficient.
Actually, each time you come to a component part, check to see whether it already has a domain. If so, and if that domain is the desired one, done, else, apply the desired domain's recast proc to the FromExpr(MeddleInternalForm) of the object. This should permit editor copying of expressions which already have a domain, into parts of an expression which doesn't.
Meddle Expr's should have a ValidObject BOOL, i.e. if the expr has a domain, and it has been checked to be a valid element of that domain, then TRUE, else FALSE. Set to FALSE whenever an Expr changed.
A different philosophy: you never trust an editor entity.
So, e.g. there should be a polynomial expression type in Meddle, which is a list of terms.
Defn of canRecast: Really applies to two structures: Can any element of the first be recast as an element of the second?
3. Consistency of Recastability, and ability to read external reps (4/20/87)
You assume that if an Object A, belonging to Structure S, can be reCasted into a Structure T, then T's FromRope proc should be able to read the result of applying S's ToRope proc to A.
3. The Type Inference problem
A general rule for structure lub'ing. LUB(Variables, Variables) = Variables. LUB(Variables, Any arithmetic structure) cannot in general be done, unless perhaps we have a structure "Polynomials with specified coefficients but unspecified variables).
Point is that LUB Structure for a Variable and an arithmetic, non-Variable Object cannot be done just by LUB'ing their respective Structures. Because to determine this LUB we want to interpret the Variable as being in Z[var].
Thus we will assume that when this situation occurs, we have our hands on the actual variable.
Note: General Expressions are contagious to polynomials, i.e. LUB(anyPolynomialStructure, GeneralExpressions) = GeneralExpressions. Thus there cannot be "polynomials over GeneralExpressions".
However, there can be matrices over GeneralExpressions. This enables to do a matrix mult, with each element of the product matrix a GeneralExpression. Doing this sort of thing points up need for simplifier for general expressions. This appears to be the "strongest" sort of domain currently.
3. Object principles
Objects are immutable: If you change an object, you have to create a new copy of its data. Thus everyone holding a pointer to an object can assume that it doesn't change.
Zero, or NIL, objects, are represented as a full Object with domain-defined "empty" data field. E.g. the zero poly has NIL data field (since data is a list), whereas empty sequence has a length 0 SequenceDataRec.
5. Note on internal representation of matrix, vector, sequence EXPRs
We assume that the elements are always maintained as a linear list, with first element the (1,1) element, then column indices varying fastest, rows slowest. Thus a matrix's elements are the concatenation of its rows, from top to bottom. This assumption is taken for granted by e.g. Eval.
2. Polynomial class hierarchies
Polynomials ← PolysCommRing
PolysCommRing ← PolysOrderedCommRing ← PolysOrderedCommField
PolysCommRing ← PolysUnorderedCommRing ← PolysUnorderedCommField
PolysCommRing ← PolysCommField
PolysCommField ← PolysOrderedCommField
PolysCommField ← PolysUnorderedCommField
Alternatively
Polynomials ← PolysCommRing ← PolysOrderedCommRing ← PolysOrderedCommField
Polynomials ← PolysCommRing ← PolysUnorderedCommRing ← PolysUnorderedCommField
where is Commutativity of mult actually used in poly algs?
2. Matrix class hierarchies
Matrices ← SquareMatrices
SquareMatrices ← SquareMatricesOverRing
SquareMatricesOverRing ← SquareMatricesOverField
2. Creating Domains
The current Ground Domains likely to be of interest to the general user are:
Bools, Colors, FormulaOperators, Integers, Rationals, Reals, Complexes
Polynomials
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)".
When you have a variable sequence into the ScratchPad, and some coefficient domain, you can apply the polynomial constructor.
Matrices
These are rings of square matrices of specified size, whose entries are belong to a specified domain.
3. Algebra-format Ropes for Objects
The reader may find it a useful exercise, for each of these examples, to create an Item, set its WorkingDomain appropriately, Tioga-select the Algebra-format Rope given below for a sample element of that Domain, bug the OperateWorkingDomain button, and choose the FromLinearRope operation. In each instance, you should get a new Current Object and corresponding Display Expression.
You can always see what CaminoReal thinks is an appropriate Algebra-format Rope for the Primary Selection by bugging the "ToASRope" button.
1. Complex Numbers
Algebra-format Rope: (-38368.0 + 22976.0 i )
At present, CaminoReal insists that anything that is to be considered a complex number must be created with the complex template from the menu, and hence be displayed in the form X. Thus for example, complex zero must be dealt with as X (or X; the presence or absence of decimal points doesn't matter) and complex one as X. Also, complex numbers with negative imaginary part will appear as in this example: X. Given this rigidity, one can perhaps live with the fact that complex numbers are not enclosed in parenthesis, e.g. here's an example of how CaminoReal currently prints a polynomial in x with complex coefficients: X
2. Polynomials
A polynomial is written as a sequence of terms in the variables of that list. 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). 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, e.g. (x + y)^2 is illegal.
For example, suppose Domain is Polynomials in (x, y, z) over the Rationals
.
Algebra-format Rope: x z^33 - 92837498279872983749734 / 33 y**23 + x y z - 1
3. Matrices
Domain is 2 x 2 Matrices over Polynomials in (x) over the Complexes
.
Algebra-format Rope: [ [ x , (1.0 + 1.0 i ) x^12 + (0.0 - 1.0 i ) ] , [ x^3 , x ] ]
4. Algebraic Numbers (see Section 14)
Suppose the domain is extension of Rationals by the unique real root of X between -2 and -1.
Algebra-format Rope: [ x^3 + 647364/19 x^2 - 3 x + 1/8 ]
Display Expression: X
4. Domains and Objects for Algebraic Numbers, Curves and Surfaces
The RealAlgebraicNumbers constructor is applied to a domain of univariate polynomials over the Rationals, e.g. Q[x]. Having set the Working Domain of an Item to this Domain, a particular real algebraic number can be created from two Objects (which must be attached to other Items): an element of the appropriate domain of univariate polynomials (this should be an irreducible polynomial), and an isolating interval for a particular real root of that polynomial. For example, the polynomial might be:
X
and the isolating interval
The latter can be constructed as an element of the domain of Points of length 2 over the Rationals. Primary select the polynomial and secondary select the interval. Then in the Viewer whose Working Domain is Real Algebraic Numbers, bug OperateWorkingDomain, choose the MakeAlgebraicNumber option in the popup menu, and you will see the algebraic number displayed. For the above example, the result would be:
X
The ExtensionField constructor can only be applied in an Item whose Current Object is a Real Algebraic Number (for example the one we just constructed). Just select ExtensionField from the Working Domain menu, and the domain constructed is the extension of the Rationals by that Real Algebraic Number. Mathematically, the elements of this domain are now univariate polynomials in the appropriate variable reduced mod the minimal polynomial. In CaminoReal, we write them as a length one vector whose single element is a polynomial. Thus, continuing with the above example, if we create a Current Expression of
X
(primary) Select it, and bug SetObject, after reduction mod the minimal polynomial of X, we will get:
[The FormulaOperators and Cads ground Domains, and the Formulas, RealAlgebraicNumbers, ExtensionField, SamplePoints, CoveringSets, and Cells structuring operations are used, for algebraic curves and surfaces. Cad2DViewer is used for displaying algebraic curves. Exercising this stuff involves a detour through the Vax currently; consult Arnon if interested.]
5. How to add a new concrete domain.
To seek out the interfaces you want, look at AlgebraStructures.df.
The class record slots, which are the same for all Domains, are defined in AlgebraClasses.mesa.
Basically you instantiate the domain using (parametrized) domain constructors, and other concrete domains, from other interfaces.
Client's method of Creating Domains
Ground Domains are provided as public variables in the appropriate interface, e.g.:
Ints.Ints
BigRats.BigRats
Structuring Operations have obvious names in the appropriate interface, e.g.:
domain ← Polynomials.MakePolynomialStructure[coeffRing, V]
Client's method of Creating Objects
Use the FromRope operation of the Domain's class record, or constructors (e.g. Matrices.DiagonalMatrix).
Displaying Objects
Use the ToRope operation of the Domain's class record.
Using Domain-specific operations
E.g. Polynomials.
Differentiate[domain][arg].
or Polynomials.Diff[arg]
5. Writing algebraic algorithms for concrete domains
Easy, you just use interface procs directly. E.g. if you know you have a concrete polynomial structure then Polynomials.Differentiate[arg]
5. Writing algebraic algorithms for parametrized domains
Harder, You have to use the method lookup mechanism on the parameter domains.
In general, try to lookup the method once outside loops, then just Apply it inside loops.
5. General note on code writing - avoiding circularity of interface references
Use the lookup mechanism, e.g. Lookup of $variableSequence in Variables does this.