Changes http://wiki.axiom-developer.org/FffgSpad/diff
--
\begin{spad}
++added:
+-- 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.
+
+
)abbrev package FAMR2 FiniteAbelianMonoidRingFunctions2
??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.
interpolate: (List D, List D, NonNegativeInteger) -> Fraction SUP D
++added:
+ ++ \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.
-> 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
+-------------------------------------------------------------------------------
+
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
--removed:
v
-
vectorStream(p: NonNegativeInteger, v: List NonNegativeInteger)
--removed:
cons(next, vectorStream(p, next))
-
vectorStream2(p: NonNegativeInteger, v: List NonNegativeInteger)
--removed:
cons(next2, vectorStream2(p, next2))
-
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
+
+ sum: Integer := sumEta
entry: Integer
??changed:
eta: List NonNegativeInteger
- := [(if sum < maxDegree _
+ := [(if sum < maxEta _
then (entry := sum; sum := 0) _
??changed:
then (entry := sum; sum := 0) _
- else (entry := maxDegree; sum := sum - maxDegree); _
+ else (entry := maxEta; sum := sum - maxEta); _
entry::NonNegativeInteger) for i in 1..#f]
--removed:
entry::NonNegativeInteger) for i in 1..#f]
-
- (sum > 0) => empty()$Stream(Matrix SUP D)
??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,
--removed:
Matrix SUP D)
-
-------------------------------------------------------------------------------
--removed:
else M.(1,1)/M.(2,1)
-
--- 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.
??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)
newton yl == newtonAux(1$F, 1$F, yl)
++added:
+
\end{spad}
--
forwarded from http://wiki.axiom-developer.org/[EMAIL PROTECTED]
