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

[Martin Rubey]

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
> >
> >     add
> >
> >         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}
\title{ssolve.spad}
\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

    Implementation == SparseUnivariatePolynomial R add

        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
better readability:
\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]].

\section{License}
<<license>>=
-- Copyright (C) 2006 Martin Rubey <address@hidden>
--
-- This program is free software; you can redistribute it and/or
-- modify it under the terms of the GNU General Public License as
-- published by the Free Software Foundation; either version 2 of
-- the License, or (at your option) any later version.
--
-- 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.
@


<<*>>=
<<license>>

<<dom: SUPEXPR SparseUnivariatePolynomialExpressions>>

<<pkg: UTSSOL TaylorSolve>>

<<pkg: EXPRSOL ExpressionSolve>>

@
\end{document}