axiom-developer
[Top][All Lists]

## Re: [Axiom-developer] a problem, maybe with strict typing

 From: Martin Rubey Subject: Re: [Axiom-developer] a problem, maybe with strict typing Date: 20 Dec 2006 10:35:08 +0100 User-agent: Gnus/5.09 (Gnus v5.9.0) Emacs/21.4

Dear William,

it seems that I am quite difficult to understand. I hope I can clarify some
things. The package works now, as I said already in my previous mail, I only
dislike one thing about it, but obviously, I couldn't make it clear. The
package is attached below.

> Speaking for myself, I won't use the expanded series as input from a user.

I don't do that either, nor would I suggest it.

> As will be seen in previous discussion and below, series expansions require
> more than just TRANFUN.

TRANFUN serves as an example, as I stated, I think.

> > -ALDOR
> > QUESTION----------------------------------------------------------------

> > My "new" idea is to create a new domain SUPEXPR that is like SUP but has
> > TRANFUN. That sounds childish, but I think it is not. I would do it as
> > follows:

> > SUPEXPR(R: Ring):UPOLYC R with
> >        if R has TRANFUN then TRANFUN
> >
> >
> >         sin(p: %): % ==
> >             ground? p => coerce sin ground p
> >             output(hconcat("Cannot compute sin p for p=", p::OutputForm)
> >                   $OutputPackage > > error "SUPEXPR: sin defined for elements of the coefficient > > ring > > only" > > > > cos(p: %): % == > > ground? p => coerce cos ground p > > output(hconcat("Cannot compute cos p for p=", p::OutputForm) > >$OutputPackage
> >             error "SUPEXPR: cos defined for elements of the coefficient
> >         ring
> >             only"

> > etc. Of course, it would be nice if this could be done generically. But I
> > suppose, Aldor cannot do something like this, i.e., define some operations
> > generically only for a "subdomain"?

> > -------------------------------------------------------------------------------
> >
> > In any case, this seems to do the trick, and should be quite easy to
> > extend.

> I am not familiar with Aldor, but what you suggested does not seem to be
> Aldor specific (except for "extend").

Replace Aldor with SPAD if you like. But it seems to me that there is more hope
to make things "generic" in Aldor...

> Note that you avoided the most important operation in the example
> implementation of sin above: for example, sin(1+?*x), where 1+?*x is in R =
> UTS(FRAC INT, x,0) and presumably SUPEXPR R would have a new symbol ? from
> UPOLYC R, would yield an error message,

No, I didn't omit anything I need. Even if R = UTS(FRAC INT, x, 0), i.e., R has
TRANFUN, I don't want to teach SUPEXPR to do something with sin(1+?*x). I guess
you meant 1+?*x would be in SUPEXPR R. Obviously, 1+?*x is not in R, thus
SUPEXPR *should* throw an error.

> The signature you proposed probably won't be ideal for the user because if
> the map argument in solve involves transcendental functions, you will be in
> trouble when it is to be evaluated.

No. As long as F is "large" enough, it just works.

> The problem you are interested in has nothing to do with differential
> equations (it may have an application to differential equation) because it is
> just solving an implicit equation in series or power series. So all that is
> needed is an expression giving the implicit equation, where the dependent and
> independent variables are given.

Yes.

> > Could you please try to re-phrase what you mean with

> >   If you require your user to give input functions directly from
> >   GR:=UPS(F,x,a), you will need to first "embed" GR to SGR:=UPS(SUP F,x,a),

> > in particular, to make things precise, could you give the signature you
> > propose for solve(...)?

> Not sure what you are puzzled about. By "give input functions directly from
> GR", I mean allowing the implicit equation to be given by expressions
> involving a power series, which is probably a bad idea anyway since equations
> are generally not given that way. The series expansion of any special or
> transcendental function should be dealt with by the solve package (that is,
> you).

I don't understand. Nowhere I suggested to deal with expressions involving
power series - assuming that, with "expressions" you refer to something like
EXPR. So far I only considered maps from UTS -> UTS and, somewhat
alternatively, elements of a FunctionSpace that I interpret as maps UTS -> UTS.

> If you are asking about "embed", then perhaps you like the language of
> category theory? Treat UTS(-,x,a) (sorry, UPS is not the correct
> abbreviation) as a functor from Ring to Ring. Then we have the following
> diagram:

>                 F    ----->   UTS(F,x,a)
>              id |                   | map
>                 v                   v
>              SUP(F) ---> UTS(SUP(F),x,a)

In this picture, I guess that elements f of F are really implicit equations
defining y(x) which get mapped to the power series expansion of the function
y(x)?

Martin

(The following pamphlet requires allprose.sty for LaTeXing, but the spad
generation using document works even if allprose.sty is not present.)

\documentclass{article}
\usepackage{allprose}

\begin{document}
\author{Martin Rubey}
\maketitle
\begin{abstract}
\end{abstract}
\tableofcontents
\section{domain SUPEXPR SparseUnivariatePolynomialExpressions}

This domain is a hack, in some sense. What I'd really like to do -
automatically - is to provide all operations supported by the coefficient
domain, as long as the polynomials can be retracted to that domain, i.e., as
long as they are just constants. I don't see another way to do this,
unfortunately.

<<dom: SUPEXPR SparseUnivariatePolynomialExpressions>>=
)abb domain SUPTRAFUN SparseUnivariatePolynomialExpressions
SparseUnivariatePolynomialExpressions(R: Ring): Exports == Implementation where

Exports == UnivariatePolynomialCategory R with

if R has TranscendentalFunctionCategory
then TranscendentalFunctionCategory

if R has TranscendentalFunctionCategory then
sin(p: %): % ==
ground? p => coerce sin ground p
output(hconcat("sin p for p= ", p::OutputForm))$OutputPackage error "SUPTRAFUN: sin only defined for elements of the coefficient ring" cos(p: %): % == ground? p => coerce cos ground p output(hconcat("cos p for p= ", p::OutputForm))$OutputPackage
error "SUPTRAFUN: cos only defined for elements of the
coefficient ring"
@

\section{package UTSSOL TaylorSolve}

[[UTSSOL]] is a facility to compute the first few coefficients of a Taylor
series given only implicitely by a function [[f]] that vanishes when applied to
the Taylor series.

It uses the method of undetermined coefficients.

\begin{ToDo}
Could I either
\begin{itemize}
\item take a function [[UTSCAT F -> UTSCAT F]] and still be able to compute
with undetermined coefficients, or
\item take a function [[F -> F]], and do likewise?
\end{itemize}

Let's see.

Try to compute the equation without resorting to power series. I.e., %
[[c: SUP SUP F]], and [[f: SUP SUP F -> SUP SUP F]]. Won't this make the
computation of coefficients terribly slow?

I could also try to replace transcendental kernels with variables\dots

Unfortunately, [[SUP F]] does not have [[TRANFUN]] -- well, it can't, of
course. However, I'd like to be able to compute %
[[sin(1+monomial(1,1)$UFPS SUP EXPR INT)]]. \end{ToDo} <<pkg: UTSSOL TaylorSolve>>= )abb package UTSSOL TaylorSolve TaylorSolve(F, UTSF, UTSSUPF): Exports == Implementation where F: Field SUP ==> SparseUnivariatePolynomialExpressions UTSF: UnivariateTaylorSeriesCategory F UTSSUPF: UnivariateTaylorSeriesCategory SUP F NNI ==> NonNegativeInteger Exports == with ssolve: (UTSSUPF -> UTSSUPF, List F) -> UTSF Implementation == add <<implementation: UTSSOL TaylorSolve>> @ <<implementation: UTSSOL TaylorSolve>>= ssolve(f, l) == c1 := map(#1::(SUP F), l)$ListFunctions2(F, SUP F)::(Stream SUP F)
c: Stream SUP F := concat(c1, generate(monomial(1$F,1$NNI)))
@

[[c]] is the stream of the already computed coefficients of the solution, plus
one which is so far undetermined.

<<implementation: UTSSOL TaylorSolve>>=
st: List Stream SUP F := [c, c]
@

Consider an arbitrary equation $f\big(x, y(x)\big)=0$. When setting $x=0$, we
obtain $f\big(0, y(0)\big)=0$. It is not necessarily the case that this
determines $y(0)$ uniquely, so we need one initial value that satisfies this
equation.
\begin{ToDo}
[[ssolve]] should check that the given initial values satisfy $f\big(0, y(0), y'(0),...\big) = 0$.
\end{ToDo}
Now consider the derivatives of $f$, where we write $y$ instead of $y(x)$ for
\begin{equation*}
\frac{d}{dx}f(x, y)=f_1(x, y) + f_2(x, y)y^\prime
\end{equation*}
and
\begin{align*}
\frac{d^2}{dx^2}f(x, y)&=f_{1,1}(x, y)\\
&+f_{1,2}(x, y)y^\prime\\
&+f_{2,1}(x, y)y^\prime\\
&+f_{2,2}(x, y)(y^\prime)^2\\
&+f_2(x, y)y^{\prime\prime}.
\end{align*}
In general, $\frac{d^2}{dx^2}f(x, y)$ depends only linearly on
$y^{\prime\prime}$.

\begin{ToDo}
This points to another possibility: Since we know that we only need to solve
linear equations, we could compute two values and then use interpolation.
This might be a bit slower, but more importantly: can we still check that we
have enough initial values? Furthermore, we then really need that $f$ is
analytic, i.e., operators are not necessarily allowed anymore. However, it
seems that composition is allowed.
\end{ToDo}

<<implementation: UTSSOL TaylorSolve>>=
next: () -> F :=
nr := st.1
res: F

if ground?(coeff: SUP F := nr.1)$(SUP F) @ If the ne element was already calculated, we can simply return it: <<implementation: UTSSOL TaylorSolve>>= then res := ground coeff else @ Otherwise, we have to find the first non-satisfied relation and solve it. It should be linear, or a single non-constant monomial. That is, the solution should be unique. <<implementation: UTSSOL TaylorSolve>>= ns := st.2 eqs: Stream SUP F := coefficients f series ns while zero? first eqs repeat eqs := rest eqs eq: SUP F := first eqs if degree eq > 1 then if monomial? eq then res := 0 else output(hconcat("The equation is: ", eq::OutputForm))$OutputPackage
error "ssolve: equation for coefficient not linear"
else res := (-coefficient(eq, 0$NNI)$(SUP F)
/coefficient(eq, 1$NNI)$(SUP F))

nr.1 := res::SUP F
st.1 := rest nr
res

series generate next
@
%$\section{package EXPRSOL ExpressionSolve} \begin{ToDo} I'd really like to be able to specify a function that works for all domains in a category. For example, [[x +-> y(x)^2 + sin x + x]] should \lq work\rq\ for [[EXPR INT]] as well as for [[UTS INT]], both being domains having [[TranscendentalFunctionCategory]]. \end{ToDo} <<pkg: EXPRSOL ExpressionSolve>>= )abb package EXPRSOL ExpressionSolve ExpressionSolve(R, F, UTSF, UTSSUPF): Exports == Implementation where R: Join(OrderedSet, IntegralDomain, ConvertibleTo InputForm) F: FunctionSpace R UTSF: UnivariateTaylorSeriesCategory F SUP ==> SparseUnivariatePolynomialExpressions UTSSUPF: UnivariateTaylorSeriesCategory SUP F OP ==> BasicOperator SY ==> Symbol NNI ==> NonNegativeInteger MKF ==> MakeBinaryCompiledFunction(F, UTSSUPF, UTSSUPF, UTSSUPF) NNI ==> NonNegativeInteger MKF ==> MakeBinaryCompiledFunction(F, UTSSUPF, UTSSUPF, UTSSUPF) Exports == with ssolve: (F, OP, SY, List F) -> UTSF Implementation == add <<implementation: EXPRSOL ExpressionSolve>> @ The general method is to transform the given expression into a form which can then be compiled. There is currently no other way in Axiom to transform an expression into a function. We need to replace the differentiation operator by the corresponding function in the power series category, and make composition explicit. Furthermore, we need to replace the variable by the corresponding variable in the power series. It turns out that the compiler doesn't find the right definition of [[monomial(1,1)]]. Thus we introduce it as a second argument. In fact, maybe that's even cleaner. Also, we need to tell the compiler that kernels that are independent of the main variable should be coerced to elements of the coefficient ring, since he will complain otherwise. <<implementation: EXPRSOL ExpressionSolve>>= opelt := operator("elt"::Symbol)$OP
opdiff := operator("D"::Symbol)$OP opcoerce := operator("coerce"::Symbol)$OP

replaceDiffs: (F, OP, Symbol) -> F
replaceDiffs (expr, op, sy) ==
lk := kernels expr
for k in lk repeat
if freeOf?(coerce k, sy) then
expr := subst(expr, [k], [opcoerce [coerce k]])

if is?(k, op) then
arg := first argument k
if arg = sy::F
then expr := subst(expr, [k], [(name op)::F])
else expr := subst(expr, [k], [opelt [(name op)::F,
replaceDiffs(arg, op,
sy)]])
--                    => "iterate"

if is?(k, %diff) then
args := argument k
differentiand := replaceDiffs(subst(args.1, args.2 =
args.3), op, sy)
expr := subst(expr, [k], [opdiff differentiand])
--                    => "iterate"
expr

ssolve(expr, op, sy, l) ==
ex := replaceDiffs(expr, op, sy)
f := compiledFunction(ex, name op, sy)$MKF ssolve(f(#1, monomial(1,1)$UTSSUPF), l)$TaylorSolve(F, UTSF, UTSSUPF) @ %$

\section{Bugs}

<<inp: ssolve>>=
ssolve(sin f x / cos x, f, x, [1])$EXPRSOL(INT, EXPR INT, UFPS EXPR INT, UFPS SUPEXPR EXPR INT) @ returns \begin{verbatim} (((0 . 1) 0 . 1) NonNullStream #<compiled-function |STREAM;generate;M$;62!0|> .
UNPRINTABLE)
\end{verbatim}

but
<<inp: ssolve>>=
U ==> UFPS SUPEXPR EXPR INT
ssolve(s +-> sin s *((cos monomial(1,1)$U)**-1)$U, f, x, [0])\$EXPRSOL(INT, EXPR
INT, UFPS EXPR INT, UFPS SUPEXPR EXPR INT)
@

works. This is probably due to missing [[/]] in [[UFPS]].

--
-- This program is free software; you can redistribute it and/or
-- modify it under the terms of the GNU General Public License as
--
-- This program is distributed in the hope that it will be
-- useful, but WITHOUT ANY WARRANTY; without even the implied
-- warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
-- PURPOSE. See the GNU General Public License for more details.
@

<<*>>=

<<dom: SUPEXPR SparseUnivariatePolynomialExpressions>>

<<pkg: UTSSOL TaylorSolve>>

<<pkg: EXPRSOL ExpressionSolve>>

@
\end{document}