Sorry, I have hit send too quickly. Re-sending with the patch.
>
> I propose the following modification to guessing package. The main
> change is removal of stream version of 'generalInteropolation'.
> Intead inside GUESS 'guessInterpolate2' generates apropriate stream
> of solution. Additionaly, after the change 'guessInterpolate' may
> return 'failed' indicating that there is no solutions.
>
> Functionally the change is almost a no-op -- in some cases we may
> do more calls to 'generalInteropolation' than in the past.
>
> Currently genVectorStream2 is unused, it is provided in case
> we want to exactly match old behaviour.
>
> The change is intended to make easier additional modifications to
> guessing package.
Index: src/algebra/mantepse.spad.pamphlet
===================================================================
--- src/algebra/mantepse.spad.pamphlet (revision 648)
+++ src/algebra/mantepse.spad.pamphlet (working copy)
@@ -2198,7 +2198,7 @@
<<implementation: Guess - guessInterpolate>>=
guessInterpolate(guessList: List SUP F, eta: List NNI, D: HPSPEC)
- : Matrix SUP S ==
+ : Union(Matrix SUP S, "failed") ==
if F is S then
vguessList: Vector SUP S := vector(guessList pretend List(SUP(S)))
generalInterpolation((D.C)(reduce(_+, eta)), D.A,
@@ -2212,26 +2212,30 @@
to Fraction S"
@
-[[guessInterpolate2]] calls the appropriate [[generalInterpolation]] from
-[[FFFG]], for all degree vectors with given [[sumEta]] and [[maxEta]].
+[[guessInterpolate2]] calls the appropriate [[guessInterpolate]]
+for all degree vectors with given [[sumEta]] and [[maxEta]].
<<implementation: Guess - guessInterpolate2>>=
-guessInterpolate2(guessList: List SUP F,
- sumEta: NNI, maxEta: NNI,
- D: HPSPEC): Stream Matrix SUP S ==
- if F is S then
- vguessList: Vector SUP S := vector(guessList pretend List(SUP(S)))
- generalInterpolation((D.C)(sumEta), D.A,
- vguessList, sumEta, maxEta)
- $FFFG(S, SUP S)
- else if F is Fraction S then
- vguessListF: Vector SUP F := vector(guessList)
- generalInterpolation((D.C)(sumEta), D.A,
- vguessListF, sumEta, maxEta)
- $FFFGF(S, SUP S, SUP F)
- else error "Guess: type parameter F should be either equal to S or equal _
- to Fraction S"
+-- 'if true' to adjust indentation
+if true then
+ guessInterpolate3(guessList: List SUP F, D: HPSPEC,
+ vs : Stream List NonNegativeInteger)_
+ : Stream Matrix SUP S == delay
+ explicitlyEmpty? vs or empty? vs => empty()$Stream(Matrix SUP S)
+ M0 := guessInterpolate(guessList, frst vs, D)
+ M0 case Matrix SUP S =>
+ M: Matrix SUP S := M0 :: Matrix SUP S
+ concat(M, guessInterpolate3(guessList, D, rst vs))
+ guessInterpolate3(guessList, D, rst vs)
+
+
+ guessInterpolate2(guessList: List SUP F, _
+ sumEta: NNI, maxEta: NNI, _
+ D: HPSPEC): Stream Matrix SUP S ==
+ vs := genVectorStream(sumEta, maxEta, #guessList)$FFFG(S, SUP S)
+ guessInterpolate3(guessList, D, vs)
+
@
[[testInterpolant]] checks whether [[resi]] is really a solution.
@@ -2650,7 +2654,9 @@
MS := rest MS
else
- M: Matrix SUP S := guessInterpolate(guessList, eta, D)
+ M0 := guessInterpolate(guessList, eta, D)
+ if M0 case Matrix SUP S then
+ M: Matrix SUP S := M0 :: Matrix SUP S
for i in 1..o repeat
res := testInterpolant(entries column(M, i),
Index: src/algebra/fffg.spad.pamphlet
===================================================================
--- src/algebra/fffg.spad.pamphlet (revision 648)
+++ src/algebra/fffg.spad.pamphlet (working copy)
@@ -120,20 +120,6 @@
++ The second argument, CA(k, l, f), should return the coefficient of x^k
++ in z^l f(x).
- generalInterpolation: (List D, CoeffAction,
- Vector V, NonNegativeInteger, NonNegativeInteger)
- -> Stream Matrix SUP D
- ++ \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).
-
generalCoefficient: (CoeffAction, Vector V,
NonNegativeInteger, Vector SUP D) -> D
++ \spad{generalCoefficient(action, f, k, p)} gives the coefficient of
@@ -172,6 +158,17 @@
++ g(x) = sum_{i=0}^k c_{k,i} <x^i> g(x), where z acts on g(x) by
++ shifting. In fact, the result is [1,q,q^2,...]
+ genVectorStream : (NonNegativeInteger, NonNegativeInteger, _
+ NonNegativeInteger) -> Stream List NonNegativeInteger
+ ++ \spad{genVectorStream(sumEta, maxEta, k)} generates stream
+ ++ of all possible non-increasing lists \spad{eta}
+ ++ with maximal entry \spad{maxEta} and sum of entries at most
+ ++ \spad{sumEta}.
+
+ genVectorStream2 : (NonNegativeInteger, NonNegativeInteger, _
+ NonNegativeInteger) -> Stream List NonNegativeInteger
+ ++ like genVectorStream, but skips every second vector.
+
Implementation ==> add
-------------------------------------------------------------------------------
@@ -310,11 +307,6 @@
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
@@ -327,49 +319,33 @@
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,
- f: Vector V,
- sumEta: NonNegativeInteger,
- maxEta: NonNegativeInteger)
- : Stream Matrix SUP D ==
- <<generate an initial degree vector>>
-
- if #f = 2 then
- map(x +-> generalInterpolation(C, coeffAction, f, x),
- cons(eta, vectorStream2(maxEta, eta)))
- $StreamFunctions2(List NonNegativeInteger,
- Matrix SUP D)
- else
- map(x +-> generalInterpolation(C, coeffAction, f, x),
- cons(eta, vectorStream(maxEta, eta)))
- $StreamFunctions2(List NonNegativeInteger,
- 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]
-@
+<<package FFFG FractionFreeFastGaussian>>=
-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)
-@
+ initialVector(sum : NonNegativeInteger, maxEta : NonNegativeInteger,
+ n : NonNegativeInteger)_
+ : List NonNegativeInteger ==
+ entry: Integer
+ [(if sum < maxEta _
+ then (entry := sum; sum := 0) _
+ else (entry := maxEta; sum := (sum - maxEta)::NonNegativeInteger);
_
+ entry::NonNegativeInteger) for i in 1..n]
-<<package FFFG FractionFreeFastGaussian>>=
+ genVectorStream(sum: NonNegativeInteger, max: NonNegativeInteger,
+ k : NonNegativeInteger) : Stream List NonNegativeInteger ==
+ eta := initialVector(sum, max, k)
+ cons(eta, vectorStream(max, eta))
+
+ genVectorStream2(sum: NonNegativeInteger, max: NonNegativeInteger,
+ k : NonNegativeInteger) : Stream List NonNegativeInteger ==
+ eta := initialVector(sum, max, k)
+ cons(eta, vectorStream2(max, eta))
+
-------------------------------------------------------------------------------
-- rational interpolation
-------------------------------------------------------------------------------
@@ -552,13 +528,6 @@
++ diagonal are given by eta. The degrees of column i are in this case
++ eta + e.i - [1,1,...,1], where the degree of zero is -1.
- generalInterpolation: (List D, CoeffAction,
- Vector VF, NonNegativeInteger, NonNegativeInteger)
- -> Stream Matrix SUP D
- ++ \spad{generalInterpolation(l, CA, f, sumEta, maxEta)} applies
- ++ generalInterpolation(l, CA, f, eta) for all possible eta with maximal
- ++ entry maxEta and sum of entries sumEta
-
Implementation == add
multiplyRows!(v: Vector D, M: Matrix SUP D): Matrix SUP D ==
@@ -589,36 +558,6 @@
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
- c := coefficients(f.i)
- den.i := commonDenominator(c)$CommonDenominator(D, F, List F)
- g.i := map(x +-> retract(x*den.i)@D, f.i)
- $FAMR2(NonNegativeInteger, Fraction D, VF, D, V)
-
- c: cFunction := (x, y) +-> generalCoefficient(coeffAction, g,
- (x - 1)::NonNegativeInteger,
- y)$FFFG(D, V)
-
-
- MS: Stream Matrix SUP D
- := generalInterpolation(C, coeffAction, g, sumEta, maxEta)$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.
-
- map(x +-> multiplyRows!(den, x), MS)$Stream(Matrix SUP D)
-
@
--
Waldek Hebisch
[email protected]
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"FriCAS - computer algebra system" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/fricas-devel?hl=en
-~----------~----~----~----~------~----~------~--~---
