[ Term Structure | Algebra | Geometry | Logic | Drawing ]
[ Language Bindings | C++ | Java | Lisp | ML ]

Algebra and Analysis

Table of Contents

• Numbers and variables
• Arithmetic Operators
• Equations and Inequalities
• Special Functions
  Function Operators
  Elementary Functions
  Combinatorial and Number Theoretic Functions
  Others
• Linear Algebra
• Calculus Operators
• Algebraic Domains
  Rationale for Domains
  Primitive Domains
  Domain Operators

This document describes the operators that are used to describe algebraic and analytic expressions. We proceed in a bottom up fashion.

Numbers and Variables

The lowest leaves of mathematical expressions in algebra and analysis are numbers and variables. Elements of the rational integers are represented by LongIntegers. One representation of elements of the reals is as floating point numbers using nodes labeled IEEEFloat. Complex numbers are not singled out for special treatment but are represented as sums of their real and imaginary part.

There are a number of well known constants. These are identified by symbolic names discussed below. To provide flexibility and to provide additional hints for systems that receive and manipulate MathBus terms, the name space for named quantities is divided into three parts: constants, variables and functions. (This decision will need to be revisited in the future. I suspect that this division should not have been made.)

Constants are represented using the following node label.

AlgConstant constName
Used to refer to constants that are widely used. The following table gives the currently defined constants and their associated string identifiers, which are used as the string ID constName sub-term of an AlgConstant node. Users should not create nodes with this label whose constName is not an element of the following list.

Variables are represented in a similar fashion as constants, but using the AlgVariable label.

AlgVariable varName
This node represents an algebraic variable. Which variable is usually indicated by the string identifier referred to by the string identifier varName sub-term. Algebraic variables can be used to represent functions, The printed representation of the variable is typically the string represented by the string ID. Since this string is a Unicode string many common, but non-Roman characters can be represented.

In many mathematical contexts, however this does not suffice. The variables are often decorated with dots, dashes, and squiggles of all types. These are indicated by adding attributes to AlgConstant, AlgVariable and AlgFuncCode (described below) nodes. The "hat", "tilde", and "vec" decorations are among the simplest. To keep storage to a minimum, the presense of all of the decorations are indicated using a single property CharDecoration. The value of this decoration is a LongInteger node of a single 32 bit quantity. We have followed TeX's naming convention when identifying these decorations.

In addition the following attribute labels can be used to identify other properties.

Arithmetic Operators

In computer algebra systems, although one has operators like difference and quotient, the internal representation uses a more canonical form using addition and multiplication by -1, or multiplication and exponentiation to the -1 power. The computer algebra approach minimizes the number of operations that need to be considered by algorithms, but limits the ability to distinguish certain classes of expressions that one might want in documentation or educational materials.

Another issue to be considered is whether there should be a single version of each the arithmetic operators, or whether there should be several versions. For instance, the addition operator in x + y is different depending on whether x and y are rational integers, polynomials, vectors, or more complicated objects. However, since the term structure is not intended to represent the specific operations on mathematical objects, but the structure of the objects we have decided at this time to use a single, generic operator for each of the arithmetic operations. The operations we use are listed below.

Plus subterm₁ subterm₂ … subterm_n

Minus subterm

Difference subterm₁ subterm₂

Times subterm₁ subterm₂ … subterm_n

Reciprocal subterm

Although there is no standard concise mathematical notation for the reciprocal of an expression, we provide a node label for it for symmetry with the Minus node label.

Quotient subterm₁ subterm₂

Exponentiate subterm₁ subterm₂

Equations and Inequalities

The following node labels are used to indicate equations and inequalities. A simplification routine would probably convert these expressions into ones that only use the first three node labels.

EquationLess lhs rhs

EquationLessEqual lhs rhs

EquationEqual lhs rhs

EquationGreatEqual lhs rhs

EquationGreat lhs rhs

EquationNotEqual lhs rhs

Special Functions

There is an enormous number of special functions in mathematics. While MathBus labels could have been allocated to each special function, it was felt that this would quickly exhaust the MathBus label space. Instead, a function node is created for each special function and an Application is used to apply functions to arguments.

In addition to saving on MathBus operator space, this approach allows us to designate particular special functions without referring to their application to a specific set of arguments. Thus, we can refer to the function sin and need not say sin x.

Function Operators

Special functions are represented using the AlgFuncCode node to indicate the function itself, and the Application node to indicate when a function is applied to a one or more arguments.

AlgFuncCode strId

Function nodes are used represent functions within the term structure. Examples include the exponential and logarithm functions, trigonometric functions and other special functions. The AlgFuncCode node uses string identifier to indicate the specific function. Certain string identifiers are predefined for well known special functions.

Lambda 'AlgFunction' term var₁ var₂ … var_n

This is a specialization of the Lambda node described earlier. It is used to indicate functions that are defined by closed form expressions.

Although functions are usually combined with arguments using the Application operator discussed below, they need not be. They are independent terms in their own right.

Elementary Functions

The following table gives the string identifiers that are associated with the elementary special functions. Note that different systems may have different interpretations of the branch cuts. Precisely where the branch cuts are placed is not specified in the MathBus term structure at the moment, but will probably be added using the attribute mechanism.

Logarithm

Combinatorial and Number Theoretic Functions

Factorial arg

The usual notation for the factorial function is

(Application (AlgFuncCode 'Factorial') arg) = arg!.

It is defined by the following relations:

GammaFunction z

The usual notation for the Gamma function is

(Application (AlgFuncCode 'GammaFunction') z) = .

BetaFunction z w

The usual notation for the Beta function is

(Application (AlgFuncCode BetaFunction') z w) = .

PochhammerSymbol n arg

The usual notation for the Pochhammer symbol is

(Application (AlgFuncCode PochhammerSymbol') n arg) = (arg)_n.

It is defined by the following relations:

BinomialCoefficient n m

FirstStirlingNum n m

SecondStirlingNum n m

NumPartitions n m

NumDistinctPartitions n m

MoebiusFunction n

EulerTotient n

NumDivisors k n

Summations and productions are represented as

SummationSym (Lambda 'AlgFunction' body ind) lolim hilim

The usual notation for this is

(SummationSym (Lambda 'AlgFunction' body ind) lolim hilim) = .

ProductSym (Lambda 'AlgFunction' body ind) lolim hilim

The usual notation for this is

(ProductSym (Lambda 'AlgFunction' body ind) lolim hilim) = .

There are more complex forms of these sums and products that still need to be defined.

Others

ExponentialIntegral z

The usual notation for this is

(Application (AlgFuncCode 'ExponentialIntegral') z) = .

LogarithmicIntegral z

The usual notation for this is

(Application (AlgFuncCode 'LogarithmicIntegral') z) = .

SineIntegral z

The usual notation for this is

(Application (AlgFuncCode 'SineIntegral') z) = .

CosineIntegral z

The usual notation for this is

(Application (AlgFuncCode 'CosineIntegral') z) = .

HypSineIntegral z

The usual notation for this is

(Application (AlgFuncCode 'HypSineIntegral') z) = .

HypCosineIntegral z

The usual notation for this is

(Application (AlgFuncCode 'HypCosineIntegral') z) = .

ErrorFunction z

The usual notation for this is

(Application (AlgFuncCode 'ErrorFunction') z) =.

CompErrorFunction z

The usual notation for this is

(Application (AlgFuncCode 'CompErrorFunction') z) =.

FresnelC z

The usual notation for this is

(Application (AlgFuncCode 'FresnelC') z) =.

FresnelS z

The usual notation for this is

(Application (AlgFuncCode 'FresnelS') z) =.

LegendreP m n z

The usual notation for this is

(Application (AlgFuncCode 'LegendreP') m n z) =.

LegendreQ n m z

The usual notation for this is

(Application (AlgFuncCode 'LegendreQ') m n z) =.

BesselJ n z

The usual notation for this is

(Application (AlgFuncCode 'BesselJ') n z) =.

BesselY n z

The usual notation for this is

(Application (AlgFuncCode 'BesselY')n z) =.

BesselI n z

The usual notation for this is

(Application (AlgFuncCode 'BesselI') n z) =.

BesselK n z

The usual notation for this is

(Application (AlgFuncCode 'BesselK') n z) =

Elliptic functions, hyper geometric functions, etc.

Linear Algebra

The basic objects that need to be represented from the regime of linear algebra are vectors and matrices. A number of different representations are provided to deal with arbitrarily high dimensional matrices, sparse matrices and matrices that contain floating point numbers.

AlgDenseVector elt₁ elt₂ … elt_n

Represents a one dimensional vector. Each sub-term corresponds to one element of the vector. Since MathBus sub-term access is one based, the first component of the vector has index 1, the second has index 2, etc. A typical vector is

(AlgDenseVector (Plus x [1]) [0] (Plus x [2]) [0] (Plus x [3]))

which corresponds to the mathematical vector

.

Such a vector can have as many as 2³² - 1 elements.

AlgDenseVectorFloat elthi₁ eltlo₁ elthi₂ eltlo₂ … elthi_n eltlo_n

Represents a one dimensional vector where each element is an IEEE standard floating point number. All of the sub-terms of this node are 32-bit integers, and each element of the algebraic vector is represented as a pair of sub-terms. The high bits of the IEEE representation are given in the first 32-bit integer, while the low 32-bits are given in the second. Because MathBus sub-terms access is one based, the k-th element of the vector will be contained in sub-terms 2k - 1 and 2k. Vectors of this type can only handle 2³¹ elements.

AlgSparseVector dim elt₁ ind₁ elt₂ ind₂ … elt_k ind_k

Represents a one dimensional vector of dimension dim, but only non-zero elements are represented. The odd indexed sub-terms are 32-bit integers that give the algebraic vector index of next sub-term. Thus the dense vector

(AlgDenseVector (Plus x [1]) [0] (Plus x [2]) [0] (Plus x [3]))

is equivalent to the sparse vector

(AlgSparseVector 3 (Plus x [1]) 1 (Plus x [2]) 3 (Plus x [3]) 5)

Since the ind_i are are 32-bit unsigned integers, this structure can only represent vectors of dimension less than 2³². Furthermore, these vectors cannot have more than 2³¹ - 1 non-zero elements.

AlgSparseVectorFloat dim elthi₁ eltlo₁ ind₁ … elthi_k eltlo_k ind_k

Represents a sparse vector of dimension dim of floating point numbers-only non-zero elements are represented. All of the sub-terms of this node are 32-bit integers. Each non-zero element of the vector uses two sub-terms.

We single out two dimensional matrices, both dense and sparse for special consideration since they occur so frequently. Higher dimensional matrices are represented as a vector of matrices of lower dimension.

AlgDenseMatrix row cols elt₁₁ elt₁₂ … elt_mn

Represents a matrix with exactly rows rows and cols columns. The elements of the matrix are the sub-nodes of the term listed in row major order.

AlgDenseMatrixFloat row cols elthi₁₁ eltlo₁₁ … elthi_mn eltlo_mn

Represents a matrix of floating point numbers with exactly rows rows and cols columns. The elements of the matrix are the sub-nodes of the term listed in row major order. All sub-terms of nodes with this label are 32-bit integers. Each element of the matrix is represented as a pair of sub-terms.

Sparse matrices are represented as a "AlgSparseMatrix" node whose sub-terms are AlgSparseVectors.

AlgSparseMatrix rows vect₁ row₁ vect₂ row₂ … vect_k row_k

Represents a sparse matrix or multi-dimensional matrix. Matrices of this type are represented recursively, as a collection of matrices of lower dimensionality. To be succinct we say the matrix consists of a number of rows. The sub-term rows is the maximum index of the rows in the matrix. The even indexed sub-terms are matrices of one less dimensionality that are indexed by the following sub-term.

Elements and sub-matrices of a vector or matrix can be represented by terms labeled AlgSubMatrix.

AlgSubMatrix matrix ind₁ ind₂ … ind_k

The sub-term matrix is assumed to represent a matrix of some form. The rank of the matrix is assumed to be k, and each of the remaining sub-terms are give an index in one dimension of the matrix.

AlgIndex lo step hi

Represents an indexing set of numbers, lo, lo + step, lo + 2step, through hi. These sub-terms are not 32-bit integers but MathBus terms.

Calculus operators

Derivatives are somewhat more complex than one might at first expect. The expression

illustrates this ambiguity. It could have either of the following meanings

Because of this ambiguity, we have chosen to define derivative operators that do not refer to specific variables, but are rather positional derivatives of functions. The meaning on the first line would be written

,

while the second meaning would be expressed as

.

To express these subtleties, the MathBus term structure provides two different node labels. The AlgFuncDeriv label is used to represent operators like ₁ which express derivatives of functions. The AlgExprTotDeriv and AlgExprPartDeriv labels represent expression derivatives like the d/dx and /x operators.

AlgFuncDeriv function index₁ index₂ … index_k

Function is a mathematical function, not a term. This node indicates the derivative of function with respect to its arguments given by the indices. An argument index can appear more than once to indicate multiple derivatives.

AlgExprTotDeriv expr variable₁ … variable_n

Represents the total derivative of the expression expr with respect to the indicated variables.

AlgExprPartDeriv expr variable₁ … variable_n

Represents the total derivative of the expression expr with respect to the indicated variables.

Using these node labels the equation given in equation (1) would take the form

(EquationEqual
  (AlgExprTotDeriv (Application (AlgFunction 'f')
                                (AlgVariable 'x')
                                (Exponentiate (AlgVariable 'x') [2]))
                   (AlgVariable 'x'))
  (Plus (Application (AlgFuncDeriv (AlgFuncCode 'f') 1)
                     (AlgVariable 'x')
                     (Exponentiate (AlgVariable 'x') [2]))
        (Times [2]
               (AlgVariable 'x')
               (Application (AlgFuncDeriv (AlgFuncCode 'f') 2)
                            (AlgVariable 'x')
                            (Exponentiate (AlgVariable 'x') [2])))))

Integrals implicitly including a variable binding. For instance, the integral

,

is a function of s, but the variable t is bound within the scope of the integral. To represent integrals, we use the Lambda term structure to specify the body of the integral, including the variable of integration.

AlgIntegral expr var

In definite integrals, the variable of integration is bound within the scope of the integral. Notice that this is not the case for indefinite integrals. So, in contrast to the simple term used to represent the indefinite integral, we us a more complex term structure to represent a definite integral. One of the sub-terms of the definite integral terms is labeled with 'Lambda' to indicate this binding.

DefiniteIntegral (Lambda 'AlgFunction' expr var) lolim hilim

Represents the definite integral of expr with respect to var between the indicated limits. This is a simple line integral from lolim to hilim.

VolumeIntegral (Lambda 'AlgFunction' expr var₁ … var_n) region

Represents an integral over some more complex region. This notation should be able to represent surface and volume integrals, as well integrals over more complex structures including Haar integrals.

The (Laplace transform) integral given above can be represented using the 'DefiniteIntegral' label as

(AlgIntegral
  (Lambda 'AlgFunction'
    (Times (Exponentiate (AlgConstant 'E')
                         (Minus (Times (AlgVariable 's') (AlgVariable 't'))))
           (Application (AlgFuncCode 'f') (AlgVariable 't')))
    (AlgVariable 't'))
  [0] (AlgConstant 'PositiveInfinity'))

Algebraic Domains

A number of computer algebra systems have found it useful to indicate the algebraic domain to which a mathematical expression belongs. These systems include Axiom[33], GAP [], Weyl [44] and experimental work in Maple called Gauss []. Briefly, the algebraic domain is a structure that represents a collection of other objects, where this collection has some "interesting" mathematical properties. Examples of domains are the group of operations on Rubic's cube, ring of rational integers (the set of integers {…, -2, -1, 0, 1, 2, …}) and the points that form a Euclidean space.

Section 7.14.7.1 discusses some of the reasons for and applications of domains. In Section 4.7.27.2 we describe the primitive low level domains and in Section 4.7.37.3 describes nodes that indicate combinations of domains into more complicated structures.

Rationale for Domains

The MathBus provides facilities for representing domains and attaching them to other MathBus objects. This section gives three examples that illustrate the need for domains.

Consider the problem of integrating the function 1/(x³ - 2):

.

Notice that, although the original problem involved rational functions with integer coefficients (Z), the final answer requires the use of 3 and ³². These radicals are needed to express the zeroes of x³ - 2, exactly. Occasionally, one is fortunate and all the zeroes of the denominator are rational numbers, e.g.,

,

but often new algebraic quantities must be added.

Now consider a routine called solve that returns one of the zeroes of a polynomial in one variable. Given x² - 5, it should return 5. But how should the symbol 5 be interpreted, i.e., how does one know that (5)² = 5, and is 5 equal to 2.2361 or -2.2361? Furthermore, after solve has been asked to solve x² - 5, what is returned as the zero of the polynomial x² - 20? Either 20 or 2 5 could be correct, although the latter is probably better than the former.

These issues can be addressed in MathBus by using domains. Domains are collections of objects, usually with operations among the objects, that possess some underlying mathematical organization. For instance, the set of rational integers, Z, is a domain, as is the set of rational numbers, Q. The polynomials x² - 5, x² - 20 and x² - x - 1 could all be elements of the domain Q[x], the set of polynomials in x with rational number coefficients. Other common domains are the real numbers, R, and the complex numbers, C. On the other hand, we rarely think of a set of numbers, e.g., {1492, 1776, 1917}, as having any mathematical structure and being a domain.

In the example above, solve is first called on x² - 5, which is an element of Q[x]. For the duration of this section, we will use the notation ( x² - 5)_Q[x] when it is necessary to indicate the domain that contains an algebraic element. When solve returns 5 it must also create a domain in which 5 is an element. This domain is Q[a]/(a² -5), the ring of polynomials in with coefficients in Q reduced modulo the relation a² - 5 = 0. Notice that a could correspond to either of the zeroes of x² - 5, so solve must also set up an embedding of Q[a]/(a ² - 5) into C-that is, a map that sends each element of Q[a]/(a ² - 5) to a complex number. Since there is a natural embedding of Q into C it is only necessary to indicate the image of in C.

This final algebraic structure, along with the embedding into C is abbreviated as Q[5]. Solve returns (5)_Q[5] thus conveying both the simplification rules that 5must obey and the embedding in C. Notice that this information is associated with the domains, rather than attached directly to 5. We find this to be the mathematically more natural approach.

The second invocation of solve is interesting. Is solve invoked on (x² - 20)_Q[x] or (x² - 20)_Q[5][x]? It is not possible to determine which is the case by just examining the polynomial. Some reference to the enclosing domain is needed. If solve is called on (x² - 20)_Q[x] then (20)_Q[Ö20] is returned, just as in the previous discussion. When solve is called on (x² - 20)_Q[Ö5][x], however, the coefficient field does not need to be extended, and (2Ö5)_Q[Ö5] is returned. This eliminates the potential future need of determining the relationship between 5 and 20.

The MathBus provides mechanisms to support multiple distinct but isomorphic domains in the same computation. Why would one want to have two copies of Z, say, present during a computation? Algebraic extensions provide one motivation. The three zeroes of x³ - 2 are

Each generates an algebraic extension of Q of degree 3. Since each has a different embedding in the complex numbers, they are, in fact, different algebraic extensions of Q. However, algebraically each extension is a simple cubic extension of the form Q[](³ - 2): i.e.,

That is, the elements of these fields can be represented as univariate polynomials modulo an irreducible univariate polynomial. Algebraically these fields are isomorphic. The only difference between these three fields is their embedding in C, i.e.,

Thus we need to be able to represent distinct fields that are algebraically isomorphic. Only when their embedding into the complex numbers is specified is it possible to distinguish them.

In addition, having multiple isomorphic domains allows us to check "functorial" code for missing or incorrect conversions while still using simple examples. For instance, consider the representation of polynomials over the integers, Z[x]. Internally, such polynomials may be represented as lists of exponent-coefficient pairs:

2x³ + 5 ((3, 2), (0, 5)).

The coefficients are elements of Z as are the exponents. For most operations, the exponents never come in contact with the coefficients.

For instance, when multiplying polynomials, the coefficients are multiplied with each other, and the exponents are compared and added to each other, but there are no operations that mix exponents and coefficients.

Many implementations use the same representation for both coefficients and exponents. Instead, we suggest that there should be a domain of integers for the exponents in addition to the domain associated with the coefficients. More generally, k[x] would have two sub-domains, k for the coefficients and Z for the exponents.

The value of this approach is apparent when examining polynomial differentiation. In that algorithm an exponent must be multiplied with coefficient. By having two isomorphic, but different, copies of Z we are forced to coerce an exponent into the domain of the coefficients even though it may not initially appear to be necessary for polynomials in Z[x], thus catching the need for coercion immediately.

Primitive Domains

no domain, rational integers, Euclidean spaces, etc.

RationalIntegers code

Represents the domain of rational integers. This domain is the basis of almost all algebraic domains. Code may be used to distinguish one instance of the rational integers from another. The code 0 is reserved to refer to a "canonical" domain of rational integers for those applications that do not care to distinguish different rational integer domains.

Domain Operators

DirectSum domain₁ domain₂ … domain_n

Represents the direct sum of the domains given as sub-terms. The elements of a direct sum domain are usually vectors where each of the components is an element of domain₁ domain₂ … domain_n.

RingOfFractions domain multiplicativeSet

Represents the ring consisting of fractions where the numerator is an element of domain and the denominator is an element of multiplicativeSet. If domain and multiplicativeSet are the same, then result is quotient ring of domain.

PolynomialRing ring variable₁ variable₂ … variable_n

Ring of polynomials in the indicated variables, where the coefficients are elements of ring.

AlgIdeal ring poly₁ poly₂ … poly_n

Represents the ideal generated by the elements poly₁ poly₂ … poly_n, which are interpreted as a elements of ring. The ideal is interpreted as an ideal of ring.

FactorRing domain subdomain

The domain obtained by viewing all elements of domain that differ by an element of subdomain as equivalent. Thus the ring of integers modulo 13, GF(13), would be represented as

(FactorRing (RationalIntegers 0) (AlgIdeal (RationalIntegers 0) [13]))

MathBus terms can be associated with particular domains, by using the 'AlgebraicDomain' attribute property. For instance,

(Attribute [163] 'AlgebraicDomain' (RationalIntegers 0))

represents the integer 163 which is an element of Z. In contrast

(Attribute [163] 
   'AlgebraicDomain' (PolynomialRing (RingOfFractions (RationalIntegers 0)))
                                     (AlgebraicVariable 1)    ;; x
                                     (AlgebraicVariable 2)))  ;; y

is also the integer 163, but it an element of the polynomial ring Q[x, y]. In both cases, the information about the domains is only present in the attributes of the term.

Copyright Cornell University
For problems or questions regarding this web contact [ SimLab project].
Last updated: November 03, 1997 by .