On Tuesday, November 4, 2014 8:48:21 PM UTC+1, Richard Fateman wrote:
>
> I think your citing of Karr's paper is OK; the more modern notation seems
> to be
> sum (i in the set{M} of f(i)) which avoids the order of enumeration
> of elements of M.
>
> As far as the best known algorithm, what about
>
> Bill Gosper's?
> e.g.
> http://mathworld.wolfram.com/GospersAlgorithm.html
>
> and the umpteen related papers some of which are in the references there?
> (which don't mention Karr;
> in fact, it seems mathematica ignores him!)
>
> While I have not recently read Karr's paper (the one in J. ACM) I recall
> it being quite lengthy and not contributing
> anything new that could be programmed in Macsyma. At least not programmed
> by me.
> Not to say that anything in it is wrong. Just not helpful.
>
> Other work, Zeilberger, Wilf. .. has been put into Maxima, I think.
>
> RJF
>
>
Karr's algorithm is much more general than Gosper's algorithm -- it
encompasses Gosper's algorithm as a special case, but is also able to deal
with q-hypergeometric series and holonomic series. For example, it can be
used to simplify horrible-looking nested sums involving generalized
harmonic numbers. This has some applications -- there's a very active
research project going on at RISC and DESY (Deutsches Elektronen
Synchrotron) that uses Karr's algorithm to evaluate Feynman diagrams, which
amount to precisely such sums
(http://www.risc.jku.at/research/combinat/subgroups/QFT/index.html)
It's quite accurate to desribe Karr's algorithm as an analog of the Risch
algorithm, only in the setting of difference fields instead of differential
fields. Why is it much less well known than Risch's algorithm? To begin
with, symbolic integration is probably considered a more important problem
for the obvious practical reason: it's often less painful to compute a
numerical value from a closed form of an integral than doing numerical
integration, but you usually don't need a closed form to evaluate a finite
sum. Moreover, hypergeometric series already cover the most common
applications, so Gosper's algorithm plus some pattern matching goes a long
way. In terms of practical importance, you could almost compare
hypergeometric terms to elementary functions in the
differential/integration setting (algebraically, however, hypergeometric
terms are arguably a more restricted class than elementary functions).
A second reason why Karr's work is much less known is that his papers
indeed are rather theoretical. You could compare it to Risch's work in a
sense. Risch provided the theoretical foundations, but the hard work of
actually making all the steps of the algorithm concrete and implementing it
in software was done later by Manuel Bronstein and others. The same has now
been done with Karr's algorithm, and it might just be a historical accident
that this development is less well-known. Carsten Schneider (RISC) has
implemented Karr's algorithm in his Mathematica package Sigma, and also
extended the algorithm. He has written numerous papers about this, for
example http://arxiv.org/abs/0808.2543 and he very clearly attributes the
whole machinery to Karr, so I think it's fair to follow that example.
Probably a third reason is that in the summation setting, some things are
just harder. In the Risch algorithm, the hardest part is integrating
algebraic functions, but this problem has been solved, at least in theory
(it seems to be extremely difficult to implement completely). In Karr's
difference field setting, the counterpart of algebraic functions are terms
like (-1)^n. These are clearly important in practice, but Karr's theory
basically breaks down when you include them. The field extension for such a
term is not transcendental, and Karr's algorithm like the Risch algorithm
depends on using transcendental extensions (and yes, a factor (-1)^n is not
a problem in a hypergeometric series, but that's a trivial special case). I
don't think the problem of supporting such terms has been completely solved
yet. Burcin Erocal did some work on this problem in his thesis, and I think
Carsten Schneider has made more progress recently, but I don't recall the
details.
Fredrik
--
You received this message because you are subscribed to the Google Groups
"sympy" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sympy.
To view this discussion on the web visit
https://groups.google.com/d/msgid/sympy/df57bb04-2ad0-4fb1-9fbf-d00b9c2889fe%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
