Changes http://wiki.axiom-developer.org/FffgSpadPamphlet/diff
--
??changed:
-\usepackage{axiom}
+\usepackage{axiom,amsthm}
+\newtheorem{ToDo}{ToDo}[section]
\begin{document}
??changed:
FiniteAbelianMonoidRingFunctions2(E: OrderedAbelianMonoid,
- R1: Ring,
- A1: FiniteAbelianMonoidRing(R1, E),
- R2: Ring,
- A2: FiniteAbelianMonoidRing(R2, E))
- : Exports == Implementation where
+ R1: Ring,
+ A1: FiniteAbelianMonoidRing(R1, E),
+ R2: Ring,
+ A2: FiniteAbelianMonoidRing(R2, E)) _
+ : Exports == Implementation where
Exports == with
map: (R1 -> R2, A1) -> A2
++added:
+ ++ \spad{map}(f, a) applies the map f to each coefficient in a. It is
+ ++ assumed that f maps 0 to 0
--removed:
--- we assume that 0 is mapped onto 0
map(f: R1 -> R2, a: A1): A2 ==
--removed:
CoeffAction ==> (NonNegativeInteger, NonNegativeInteger, V) -> D
--- coeffAction(k, l, f) is the coefficient of x^k in z^l f(x)
??changed:
++ Labahn.
-
--- c(k, M) computes $c_k(M)$ as in Equation (2). Note that the information
--- about $f$ is encoded in $c$.
+ ++
+ ++ The second argument, c(k, M) computes c_k(M) as in Equation (2). Note
+ ++ that the information about f is therefore encoded in c.
??changed:
interpolate: (List D, List D, NonNegativeInteger) -> Fraction SUP D
-
+ ++ \spad{interpolate(xlist, ylist, deg} returns the rational function
with
+ ++ numerator degree at most \spad{deg} and denominator degree at most
+ ++ \spad{#xlist-deg-1} that interpolates the given points using
+ ++ fraction free arithmetic. Note that rational interpolation does not
+ ++ guarantee that all given points are interpolated correctly:
+ ++ unattainable points may make this impossible.
+
+@
+
+\begin{ToDo}
+ The following function could be moved to [[FFFGF]], parallel to
+ [[generalInterpolation]]. However, the reason for moving
+ [[generalInterpolation]] for fractions to a separate package was the need of
+ a generic signature, hence the extra argument [[VF]] to [[FFFGF]]. In the
+ special case of rational interpolation, this extra argument is not necessary,
+ since we are always returning a fraction of [[SUP]]s, and ignore [[V]]. In
+ fact, [[V]] is not needed for [[fffg]] itself, only if we want to specify a
+ [[CoeffAction]].
+
+ Thus, maybe it would be better to move [[fffg]] to a separate package?
+\end{ToDo}
+
+<<package FFFG FractionFreeFastGaussian>>=
interpolate: (List Fraction D, List Fraction D, NonNegativeInteger)
-> Fraction SUP D
++added:
+ ++ \spad{interpolate(xlist, ylist, deg} returns the rational function
with
+ ++ numerator degree \spad{deg} that interpolates the given points using
+ ++ fraction free arithmetic.
??changed:
Vector V, List NonNegativeInteger) -> Matrix SUP D
- ++ \spad{generalInterpolation(l, CA, f, eta)} performs Hermite-Pade
+ ++ \spad{generalInterpolation(C, CA, f, eta)} performs Hermite-Pade
++ approximation using the given action CA of polynomials on the elements
++ eta + e.i - [1,1,...,1], where the degree of zero is -1.
++added:
+ ++
+ ++ The first argument C is the list of coefficients c_{k,k} in the
+ ++ expansion <x^k> z g(x) = sum_{i=0}^k c_{k,i} <x^i> g(x).
+ ++
+ ++ The second argument, CA(k, l, f), should return the coefficient of x^k
+ ++ in z^l f(x).
??changed:
-> Stream Matrix SUP D
- ++ \spad{generalInterpolation(l, CA, f, totalDegree, maxDegree)} applies
- ++ \spad{generalInterpolation(l, CA, f, eta)} for all possible \spad{eta}
- ++ with maximal entry \spad{maxDegree} and sum of entries
- ++ \spad{totalDegree}.
+ ++ \spad{generalInterpolation(C, CA, f, sumEta, maxEta)} applies
+ ++ \spad{generalInterpolation(C, CA, f, eta)} for all possible \spad{eta}
+ ++ with maximal entry \spad{maxEta} and sum of entries at most
+ ++ \spad{sumEta}.
+ ++
+ ++ The first argument C is the list of coefficients c_{k,k} in the
+ ++ expansion <x^k> z g(x) = sum_{i=0}^k c_{k,i} <x^i> g(x).
+ ++
+ ++ The second argument, CA(k, l, f), should return the coefficient of
x^k
+ ++ in z^l f(x).
??changed:
++ x^k in p(z)\dot f(x), where the action of z^l on a polynomial in x is
- ++ given by action.
+ ++ given by action, i.e., action(k, l, f) should return the coefficient
+ ++ of x^k in z^l f(x).
??changed:
++ \spad{DiffAction(k, l, g)} gives the coefficient of x^k in z^l g(x),
- ++ where z*(a+b*x+c*x^2+d*x^3+...) = (a*x+b*x^2+c*x^3+...).
+ ++ where z*(a+b*x+c*x^2+d*x^3+...) = (a*x+b*x^2+c*x^3+...), i.e.,
+ ++ multiplication with x.
??changed:
--- q-ShiftAction(k, l, f) is the CoeffAction appropriate for the shift
operator.
+-- q-ShiftAction(k, l, f) is the CoeffAction appropriate for the q-shift
operator.
??changed:
--- returns the lexicographically next vector with non-negative components
--- smaller than p with the same sum as v
+-------------------------------------------------------------------------------
+-- general - suitable for functions f - trying all possible degree combinations
+-------------------------------------------------------------------------------
+
+@
+
+The following function returns the lexicographically next vector with
+non-negative components smaller than [[p]] with the same sum as [[v]].
+
+<<package FFFG FractionFreeFastGaussian>>=
nextVector!(p: NonNegativeInteger, v: List NonNegativeInteger)
??changed:
pos := position(#1 < p, v)
--- pos should never be zero, since we assume that we have at least one
--- non-maximal, non-zero element.
+ zero? pos => return "failed"
if pos = 1 then
??changed:
v
-
+@
+
+The following function returns the stream of all possible degree vectors,
+beginning with [[v]], where the degree vectors are sorted in reverse
+lexicographic order. Furthermore, the entries are all less or equal to [[p]]
+and their sum equals the sum of the entries of [[v]]. We assume that the
+entries of [[v]] are also all less or equal to [[p]].
+
+<<package FFFG FractionFreeFastGaussian>>=
vectorStream(p: NonNegativeInteger, v: List NonNegativeInteger)
??changed:
cons(next, vectorStream(p, next))
-
+@
+
+[[vectorStream2]] skips every second entry of [[vectorStream]].
+
+<<package FFFG FractionFreeFastGaussian>>=
vectorStream2(p: NonNegativeInteger, v: List NonNegativeInteger)
??changed:
cons(next2, vectorStream2(p, next2))
-
+@
+
+This version of [[generalInterpolation]] returns a stream of solutions, one for
+each possible degree vector. Thus, it only needs to apply the previously
+defined [[generalInterpolation]] to each degree vector. These are generated by
+[[vectorStream]] and [[vectorStream2]] respectively.
+
+If [[f]] consists of two elements only, we can skip every second degree vector:
+note that [[fffg]], and thus also [[generalInterpolation]], returns a matrix
+with [[#f]] columns, each corresponding to a solution of the interpolation
+problem. More precisely, the $i$\textsuperscript{th} column is a solution with
+degrees [[eta]]$-(1,1,\dots,1)+e_i$. Thus, in the case of $2\times 2$ matrices,
+[[vectorStream]] would produce solutions corresponding to $(d,0), (d-1,1);
+(d-1,1), (d-2, 2); (d-2, 2), (d-3,3)\dots$, i.e., every second matrix is
+redundant.
+
+Although some redundancy exists also for higher dimensional [[f]], the scheme
+becomes much more complicated, thus we did not implement it.
+
+<<package FFFG FractionFreeFastGaussian>>=
generalInterpolation(C: List D, coeffAction: CoeffAction,
??changed:
f: Vector V,
- totalDegree: NonNegativeInteger,
- maxDegree: NonNegativeInteger)
+ sumEta: NonNegativeInteger,
+ maxEta: NonNegativeInteger)
: Stream Matrix SUP D ==
??changed:
: Stream Matrix SUP D ==
- sum: Integer := totalDegree
- entry: Integer
- eta: List NonNegativeInteger
- := [(if sum < maxDegree _
- then (entry := sum; sum := 0) _
- else (entry := maxDegree; sum := sum - maxDegree); _
- entry::NonNegativeInteger) for i in 1..#f]
-
- (sum > 0) => empty()$Stream(Matrix SUP D)
+
+ <<generate an initial degree vector>>
??changed:
map(generalInterpolation(C, coeffAction, f, #1),
- cons(eta, vectorStream2(maxDegree, eta)))
+ cons(eta, vectorStream2(maxEta, eta)))
$StreamFunctions2(List NonNegativeInteger,
??changed:
map(generalInterpolation(C, coeffAction, f, #1),
- cons(eta, vectorStream(maxDegree, eta)))
+ cons(eta, vectorStream(maxEta, eta)))
$StreamFunctions2(List NonNegativeInteger,
??changed:
Matrix SUP D)
-
+@
+
+We need to generate an initial degree vector, being the minimal element in
+reverse lexicographic order, i.e., $m, m, \dots, m, k, 0, 0, \dots$, where $m$
+is [[maxEta]] and $k$ is the remainder of [[sumEta]] divided by
+[[maxEta]]. This is done by the following code:
+
+<<generate an initial degree vector>>=
+sum: Integer := sumEta
+entry: Integer
+eta: List NonNegativeInteger
+ := [(if sum < maxEta _
+ then (entry := sum; sum := 0) _
+ else (entry := maxEta; sum := sum - maxEta); _
+ entry::NonNegativeInteger) for i in 1..#f]
+@
+
+We want to generate all vectors with sum of entries being at most
+[[sumEta]]. Therefore the following is incorrect.
+<<BUG generate an initial degree vector>>=
+-- (sum > 0) => empty()$Stream(Matrix SUP D)
+@
+
+<<package FFFG FractionFreeFastGaussian>>=
-------------------------------------------------------------------------------
??changed:
--- wegen Lemma 5.3 können M.1.(2,1) und M.1.(2,2) nicht beide verschwinden,
--- denn eta_sigma ist immer sigma-normal (Theorem 7.2) und damit auch
--- paranormal (Dfn 4.2)
-
--- wegen Lemma 5.1 ist M.1.(*,2) eine Lösung des Interpolationsproblems, wenn
--- M.1.(2,1) verschwindet.
-
+@
+Because of Lemma~5.3, [[M.1.(2,1)]] and [[M.1.(2,2)]] cannot both vanish,
+since [[eta_sigma]] is always $\sigma$-normal by Theorem~7.2 and therefore also
+para-normal, see Definition~4.2.
+
+Because of Lemma~5.1 we have that [[M.1.(*,2)]] is a solution of the
+interpolation problem, if [[M.1.(2,1)]] vanishes.
+
+<<package FFFG FractionFreeFastGaussian>>=
-------------------------------------------------------------------------------
??changed:
-> Stream Matrix SUP D
- ++ \spad{generalInterpolation(l, CA, f, totalDegree, maxDegree)} applies
+ ++ \spad{generalInterpolation(l, CA, f, sumEta, maxEta)} applies
++ generalInterpolation(l, CA, f, eta) for all possible eta with maximal
??changed:
++ generalInterpolation(l, CA, f, eta) for all possible eta with maximal
- ++ entry maxDegree and sum of entries totalDegree
+ ++ entry maxEta and sum of entries sumEta
++added:
+ for i in 1..n repeat
+ c := coefficients(f.i)
+ den.i := commonDenominator(c)$CommonDenominator(D, F, List F)
+ g.i := map(retract(#1*den.i)@D, f.i)
+ $FAMR2(NonNegativeInteger, Fraction D, VF, D, V)
+
+ M := generalInterpolation(C, coeffAction, g, eta)$FFFG(D, V)
+
+-- The following is necessary since I'm multiplying each row with a factor, not
+-- each column. Possibly I could factor out gcd den, but I'm not sure whether
+-- this is efficient.
+
+ multiplyRows!(den, M)
+
+ generalInterpolation(C: List D, coeffAction: CoeffAction,
+ f: Vector VF,
+ sumEta: NonNegativeInteger,
+ maxEta: NonNegativeInteger)
+ : Stream Matrix SUP D ==
+
+ n := #f
+ g: Vector V := new(n, 0)
+ den: Vector D := new(n, 0)
+
for i in 1..n repeat
??changed:
$FAMR2(NonNegativeInteger, Fraction D, VF, D, V)
-
- M := generalInterpolation(C, coeffAction, g, eta)$FFFG(D, V)
+
+ c: cFunction := generalCoefficient(coeffAction, g,
+ (#1-1)::NonNegativeInteger,
#2)$FFFG(D, V)
+
+
+ MS: Stream Matrix SUP D
+ := generalInterpolation(C, coeffAction, g, sumEta, maxEta)$FFFG(D, V)
--removed:
- multiplyRows!(den, M)
-
- generalInterpolation(C: List D, coeffAction: CoeffAction,
- f: Vector VF,
- totalDegree: NonNegativeInteger,
- maxDegree: NonNegativeInteger)
- : Stream Matrix SUP D ==
-
- n := #f
- g: Vector V := new(n, 0)
- den: Vector D := new(n, 0)
-
- for i in 1..n repeat
- c := coefficients(f.i)
- den.i := commonDenominator(c)$CommonDenominator(D, F, List F)
- g.i := map(retract(#1*den.i)@D, f.i)
- $FAMR2(NonNegativeInteger, Fraction D, VF, D, V)
-
- c: cFunction := generalCoefficient(coeffAction, g,
-[8 more lines...]
map(multiplyRows!(den, #1), MS)$Stream(Matrix SUP D)
Exports == with
++added:
+
newton: List F -> SparseUnivariatePolynomial F
++added:
+ ++ \spad{newton}(l) returns the interpolating polynomial for the values
+ ++ l, where the x-coordinates are assumed to be [1,2,3,...,n] and the
+ ++ coefficients of the interpolating polynomial are known to be in the
+ ++ domain F. I.e., it is a very streamlined version for a special case of
+ ++ interpolation.
+
Implementation == add
??changed:
- z:SparseUnivariatePolynomial(F) := monomial(1,1)
+ z: SparseUnivariatePolynomial(F) := monomial(1,1)
??changed:
-- 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.
+--
+-- 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.
--
forwarded from http://wiki.axiom-developer.org/[EMAIL PROTECTED]
