hypertex/pages/POLY.ht

% Copyright The Numerical Algorithms Group Limited 1992-94. All rights reserved.
% !! DO NOT MODIFY THIS FILE BY HAND !! Created by ht.awk.
\newcommand{\PolynomialXmpTitle}{Polynomial}
\newcommand{\PolynomialXmpNumber}{9.67}
%
% =====================================================================
\begin{page}{PolynomialXmpPage}{9.67 Polynomial}
% =====================================================================
\beginscroll

%
%
%
%
%


The domain constructor \spadtype{Polynomial} (abbreviation: \spadtype{POLY})
provides polynomials with an arbitrary number of unspecified
variables.

\xtc{
It is used to create the default polynomial domains
in \Language{}.
Here the coefficients are integers.
}{
\spadpaste{x + 1}
}
\xtc{
Here the coefficients have type \spadtype{Float}.
}{
\spadpaste{z - 2.3}
}
\xtc{
And here we have a polynomial in two variables with coefficients which
have type \spadtype{Fraction Integer}.
}{
\spadpaste{y^2 - z + 3/4}
}

The representation of objects of domains created by \spadtype{Polynomial}
is that of recursive univariate polynomials.\footnote{The term
\spad{univariate} means ``one variable.'' \spad{multivariate} means
``possibly more than one variable.''}
\xtc{
This recursive structure is sometimes obvious from the display of
a polynomial.
}{
\spadpaste{y ^2 + x*y + y \bound{prev}}
}
In this example, you see that the polynomial is stored as a polynomial in
\spad{y} with coefficients that are polynomials in \spad{x} with integer
coefficients.
In fact, you really don't need to worry about the representation unless
you are working on an advanced application where it is critical.
The polynomial types created from
\spadtype{DistributedMultivariatePolynomial} and
\spadtype{NewDistributedMultivariatePolynomial} (discussed in
\downlink{`DistributedMultivariatePolynomial'}{DistributedMultivariatePolynomialXmpPage}\ignore{DistributedMultivariatePolynomial}) are stored and displayed in a
non-recursive manner.
\xtc{
You see a ``flat'' display of the above
polynomial by converting to one of those types.
}{
\spadpaste{\% :: DMP([y,x],INT) \free{prev}}
}

We will demonstrate many of the polynomial facilities by using two
polynomials with integer coefficients.
\xtc{
By default, the interpreter expands polynomial expressions, even if they
are written in a factored format.
}{
\spadpaste{p := (y-1)^2 * x * z \bound{p}}
}
\xtc{
See \downlink{`Factored'}{FactoredXmpPage}\ignore{Factored} to see
how to create objects in factored form directly.
}{
\spadpaste{q := (y-1) * x * (z+5) \bound{q}}
}
\xtc{
The fully factored form can be recovered by using
\spadfunFrom{factor}{Polynomial}.
}{
\spadpaste{factor(q) \free{q}}
}
This is the same name used for the operation to factor integers.
Such reuse of names is called \spadgloss{overloading} and makes it much easier
to think of solving problems in general ways.
\Language{} facilities for factoring polynomials created with
\spadtype{Polynomial} are currently restricted to
the integer and rational number coefficient cases.
There are more complete facilities for factoring univariate polynomials:
see \downlink{``\ugProblemFactorTitle''}{ugProblemFactorPage} in Section \ugProblemFactorNumber\ignore{ugProblemFactor}.

\xtc{
The standard arithmetic operations are available for polynomials.
}{
\spadpaste{p - q^2\free{p q}}
}
\xtc{
The operation \spadfunFrom{gcd}{Polynomial} is used to compute the
greatest common divisor of two polynomials.
}{
\spadpaste{gcd(p,q) \free{p q}\bound{prev4}}
}
\xtc{
In the case of \spad{p} and \spad{q}, the gcd is obvious from their
definitions.
We factor the gcd to show this relationship better.
}{
\spadpaste{factor \% \free{prev4}}
}
\xtc{
The least common multiple is computed by using \spadfunFrom{lcm}{Polynomial}.
}{
\spadpaste{lcm(p,q) \free{p q}}
}
\xtc{
Use \spadfunFrom{content}{Polynomial} to compute the greatest common divisor of the
coefficients of the polynomial.
}{
\spadpaste{content p \free{p}}
}

Many of the operations on polynomials require you to specify a variable.
For example, \spadfunFrom{resultant}{Polynomial} requires you to give the
variable in which the polynomials should be expressed.
\xtc{
This computes the resultant of the values of \spad{p} and
\spad{q}, considering them as polynomials in the variable \spad{z}.
They do not share a root when thought of as polynomials in \spad{z}.
}{
\spadpaste{resultant(p,q,z) \free{p q}}
}
\xtc{
This value is \spad{0} because as polynomials in \spad{x} the polynomials
have a common root.
}{
\spadpaste{resultant(p,q,x) \free{p}\free{q}}
}
The data type used for the variables created by \spadtype{Polynomial} is
\spadtype{Symbol}.
As mentioned above, the representation used by \spadtype{Polynomial} is
recursive and so there is a main variable for nonconstant polynomials.
\xtc{
The operation \spadfunFrom{mainVariable}{Polynomial} returns this
variable.
The return type is actually a union of \spadtype{Symbol} and
\spad{"failed"}.
}{
\spadpaste{mainVariable p \free{p}}
}
\xtc{
The latter branch of the union is be used if the polynomial has no
variables, that is, is a constant.
}{
\spadpaste{mainVariable(1 :: POLY INT)}
}
\xtc{
You can also use the predicate \spadfunFrom{ground?}{Polynomial} to test
whether a polynomial is in fact a member of its ground ring.
}{
\spadpaste{ground? p \free{p}}
}
\xtc{
}{
\spadpaste{ground?(1 :: POLY INT)}
}
\xtc{
The complete list of variables actually used in a particular polynomial is
returned by \spadfunFrom{variables}{Polynomial}.
For constant polynomials, this list is empty.
}{
\spadpaste{variables p \free{p}}
}

\xtc{
The \spadfunFrom{degree}{Polynomial} operation returns the
degree of a polynomial in a specific variable.
}{
\spadpaste{degree(p,x) \free{p}}
}
\xtc{
}{
\spadpaste{degree(p,y) \free{p}}
}
\xtc{
}{
\spadpaste{degree(p,z) \free{p}}
}
\xtc{
If you give a list of variables for the second argument, a list
of the degrees in those variables is returned.
}{
\spadpaste{degree(p,[x,y,z]) \free{p}}
}
\xtc{
The minimum degree of a variable in a polynomial is computed using
\spadfunFrom{minimumDegree}{Polynomial}.
}{
\spadpaste{minimumDegree(p,z) \free{p}}
}
\xtc{
The total degree of a polynomial is returned by
\spadfunFrom{totalDegree}{Polynomial}.
}{
\spadpaste{totalDegree p \free{p}}
}

\xtc{
It is often convenient to think of a polynomial as a leading monomial plus
the remaining terms.
}{
\spadpaste{leadingMonomial p \free{p}}
}
\xtc{
The \spadfunFrom{reductum}{Polynomial} operation returns a polynomial
consisting of the sum of the monomials after the first.
}{
\spadpaste{reductum p \free{p}}
}
\xtc{
These have the obvious relationship that the original polynomial
is equal to the leading monomial plus the reductum.
}{
\spadpaste{p - leadingMonomial p - reductum p \free{p}}
}
\xtc{
The value returned by \spadfunFrom{leadingMonomial}{Polynomial} includes
the coefficient of that term.
This is extracted by using
\spadfunFrom{leadingCoefficient}{Polynomial} on the original polynomial.
}{
\spadpaste{leadingCoefficient p \free{p}}
}
\xtc{
The operation \spadfunFrom{eval}{Polynomial} is used to substitute a value
for a variable in a polynomial.
}{
\spadpaste{p  \free{p}}
}
\xtc{
This value may be another variable, a constant or a polynomial.
}{
\spadpaste{eval(p,x,w) \free{p}}
}
\xtc{
}{
\spadpaste{eval(p,x,1) \free{p}}
}
\xtc{
Actually, all the things being substituted are just polynomials,
some more trivial than others.
}{
\spadpaste{eval(p,x,y^2 - 1) \free{p}}
}

\xtc{
Derivatives are computed using the \spadfunFrom{D}{Polynomial}
operation.
}{
\spadpaste{D(p,x) \free{p}}
}
\xtc{
The first argument is the polynomial and the second is the variable.
}{
\spadpaste{D(p,y) \free{p}}
}
\xtc{
Even if the polynomial has only one variable, you must specify it.
}{
\spadpaste{D(p,z) \free{p}}
}

Integration of polynomials is similar and the
\spadfunFrom{integrate}{Polynomial} operation is used.

\xtc{
Integration requires that the coefficients support division.
Consequently,
\Language{} converts polynomials over the integers to polynomials over
the rational numbers before integrating them.
}{
\spadpaste{integrate(p,y) \free{p}}
}

It is not possible, in general, to divide two polynomials.
In our example using polynomials over the integers, the operation
\spadfunFrom{monicDivide}{Polynomial} divides a polynomial by a monic
polynomial (that is, a polynomial with leading coefficient equal to 1).
The result is a record of the quotient and remainder of the
division.
\xtc{
You must specify the variable in which to express the polynomial.
}{
\spadpaste{qr := monicDivide(p,x+1,x) \free{p}\bound{qr}}
}
\xtc{
The selectors of the components of the record are
\spad{quotient} and \spad{remainder}.
Issue this to extract the remainder.
}{
\spadpaste{qr.remainder \free{qr}}
}
\xtc{
Now that we can extract the components, we can demonstrate the
relationship among them and the arguments to our original expression
\spad{qr := monicDivide(p,x+1,x)}.
}{
\spadpaste{p - ((x+1) * qr.quotient + qr.remainder) \free{p}\free{qr}}
}

\xtc{
If the \spadopFrom{/}{Fraction} operator is used with polynomials, a
fraction object is created.
In this example, the result is an object of type
\spadtype{Fraction Polynomial Integer}.
}{
\spadpaste{p/q \free{p}\free{q}}
}
\xtc{
If you use rational numbers as polynomial coefficients, the
resulting object is of type \spadtype{Polynomial Fraction Integer}.
}{
\spadpaste{(2/3) * x^2 - y + 4/5 \bound{prev1}}
}
\xtc{
This can be converted to a fraction of polynomials and back again, if
required.
}{
\spadpaste{\% :: FRAC POLY INT \free{prev1}\bound{prev2}}
}
\xtc{
}{
\spadpaste{\% :: POLY FRAC INT \free{prev2}\bound{prev3}}
}
\xtc{
To convert the coefficients to floating point,
map the \spadfun{numeric} operation on the coefficients of the polynomial.
}{
\spadpaste{map(numeric,\%) \free{prev3}}
}

For more information on related topics, see
\downlink{`UnivariatePolynomial'}{UnivariatePolynomialXmpPage}\ignore{UnivariatePolynomial},
\downlink{`MultivariatePolynomial'}{MultivariatePolynomialXmpPage}\ignore{MultivariatePolynomial}, and
\downlink{`DistributedMultivariatePolynomial'}{DistributedMultivariatePolynomialXmpPage}\ignore{DistributedMultivariatePolynomial}.
You can also issue the system command
\spadsys{)show Polynomial}
to display the full list of operations defined by
\spadtype{Polynomial}.
\endscroll
\autobuttons
\end{page}
%