Changes http://wiki.axiom-developer.org/SsolveSpadPamphlet/diff
--
\documentclass{article}
\usepackage{axiom,amsthm,amsmath}
\newtheorem{ToDo}{ToDo}[section]
\begin{document}
\title{solve.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 SUPEXPR 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
exp(p: %): % ==
ground? p => coerce exp ground p
output(hconcat("exp p for p= ", p::OutputForm))$OutputPackage
error "SUPTRAFUN: exp only defined for elements of the
coefficient ring"
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"
asin(p: %): % ==
ground? p => coerce asin ground p
output(hconcat("asin p for p= ", p::OutputForm))$OutputPackage
error "SUPTRAFUN: asin 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"
acos(p: %): % ==
ground? p => coerce acos ground p
output(hconcat("acos p for p= ", p::OutputForm))$OutputPackage
error "SUPTRAFUN: acos 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
seriesSolve: (UTSSUPF -> UTSSUPF, List F) -> UTSF
Implementation == add
<<implementation: UTSSOL TaylorSolve>>
@
<<implementation: UTSSOL TaylorSolve>>=
seriesSolve(f, l) ==
c1 := map(#1::(SUP F), l)$ListFunctions2(F, SUP F)::(Stream SUP F)
coeffs: Stream SUP F := concat(c1, generate(monomial(1$F,1$NNI)))
-- coeffs: Stream SUP F := concat(c1, monomial(1$F,1$NNI))
@
[[coeffs]] is the stream of the already computed coefficients of the solution,
plus one which is so far undetermined. We store in [[st.2]] the complete stream
and in [[st.1]] the stream starting with the first coefficient that has
possibly not yet been computed.
\begin{ToDo}
The mathematics is not quite worked out. If [[coeffs]] is initialized as
stream with all coefficients set to the \emph{same} transcendental value,
and not enough initial values are given, then the missing ones are
implicitely assumed to be all identical. It may well happen that a solution
is produced, although it is not uniquely determined\dots
\end{ToDo}
<<implementation: UTSSOL TaylorSolve>>=
st: List Stream SUP F := [coeffs, coeffs]
@
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}
[[seriesSolve]] 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 next element was already calculated, we can simply return it:
<<implementation: UTSSOL TaylorSolve>>=
then
res := ground coeff
st.1 := rest nr
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
output(hconcat("ns: ", ns::OutputForm))
$OutputPackage
eqs: Stream SUP F := coefficients f series ns
output(hconcat("eqs: ", eqs::OutputForm))
$OutputPackage
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 "seriesSolve: equation for coefficient not
linear"
else res := (-coefficient(eq, 0$NNI)$(SUP F)
/coefficient(eq, 1$NNI)$(SUP F))
nr.1 := res::SUP F
-- concat!(st.2, monomial(1$F,1$NNI))
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)
Exports == with
seriesSolve: (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 it 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
seriesSolve(expr, op, sy, l) ==
ex := replaceDiffs(expr, op, sy)
f := compiledFunction(ex, name op, sy)$MKF
seriesSolve(f(#1, monomial(1,1)$UTSSUPF), l)$TaylorSolve(F, UTSF,
UTSSUPF)
@
%$
\section{Bugs}
<<inp: seriesSolve>>=
seriesSolve(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: seriesSolve>>=
U ==> UFPS SUPEXPR EXPR INT
seriesSolve(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 <[EMAIL PROTECTED]>
--
-- 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}
--
forwarded from http://wiki.axiom-developer.org/[EMAIL PROTECTED]
