Opened 3 years ago

Closed 2 years ago

#22090 closed enhancement (fixed)

Gosper algorithm and Wilf-Zeilberger certificate

Reported by: rws Owned by:
Priority: major Milestone: sage-8.0
Component: symbolics Keywords:
Cc: Merged in:
Authors: Ralf Stephan Reviewers: Frédéric Chapoton
Report Upstream: N/A Work issues:
Branch: 70462e2 (Commits) Commit: 70462e26e4d02bba1bbe8c6264587b564314e417
Dependencies: #22174, #22364 Stopgaps:

Description (last modified by rws)

Pynac-0.7.3 introduces Gosper's hypergeometric summation algorithm. The ticket will implement the interface and add an extensive test file. Later tickets may call the function before delegating unsolved sums to Maxima.

Also, the WZ certificate can be computed to prove hypergeometric identities.

The test file has one test marked as known bug. Its resolution depends on handling of expressions with algebraic coefficients (i.e. manipulations of polynomials over algebraic fields).

Pynac-0.7.5 adds a crucial improvement and a faster implementation.

Change History (38)

comment:1 Changed 3 years ago by rws

  • Branch set to u/rws/gosper_algorithm

comment:2 Changed 3 years ago by git

  • Commit set to 500332755b4187104f5ed47ec701a14d185d53d9

Branch pushed to git repo; I updated commit sha1. New commits:

dda7f2dMerge branch 'develop' into t/22090/gosper_algorithm
500332722090: test file

comment:3 Changed 3 years ago by rws

  • Authors set to Ralf Stephan
  • Description modified (diff)
  • Status changed from new to needs_review

comment:4 Changed 3 years ago by rws

  • Description modified (diff)

comment:5 Changed 3 years ago by rws

  • Dependencies changed from #19461, pynac-0.7.3 to #19461, #22136

comment:6 Changed 3 years ago by rws

I concede that we don't need really need #19461.

comment:7 Changed 3 years ago by git

  • Commit changed from 500332755b4187104f5ed47ec701a14d185d53d9 to 17c5e409466c4b258e1eb07fc490cf6828dff9ba

Branch pushed to git repo; I updated commit sha1. New commits:

0e4851122136: pkg version/chksum
c636059Merge branch 't/22136/upgrade_to_pynac_0_7_3' into t/22090/gosper_algorithm
17c5e4022090: fixes

comment:8 Changed 3 years ago by rws

  • Dependencies #19461, #22136 deleted
  • Description modified (diff)
  • Milestone changed from sage-7.5 to sage-7.6

Still missing is better documentation. As to performance 75% of complicated summations are spent in computation of one symbolic matrix determinant, of which 2/3 is expansions. It is astonishing that the 12x12 matrix determinant from the summation of (((n^4-14*n^2-24*n-9) * 2^n / n^2 / (n+1)^2 / (n+2)^2 / (n+3)^2)) needs 4,316 first level expansions, even with the supposedly optimized "enhanced Laplace-expansion" determinant algorithm used.

Version 0, edited 3 years ago by rws (next)

comment:9 Changed 3 years ago by git

  • Commit changed from 17c5e409466c4b258e1eb07fc490cf6828dff9ba to 7394ee1bee57b6a0a525de62bf8a913bda687aac

Branch pushed to git repo; I updated commit sha1. New commits:

88224d4Merge branch 'develop' into t/22090/gosper_algorithm
7394ee122090: documentation

comment:10 Changed 3 years ago by dimpase

How does one "delegate to Maxima"? Does it do these "known bugs" cases?

comment:11 Changed 3 years ago by rws

Gosper summation is a subset of summation, i.e., it can handle only hypergeometric expressions (or sums of such). If one wants to use it in sum then if gosper_sum can't solve it, we would call Maxima's sum. The known bugs using Maxima's sum:

sage: (1 / (n^2 + sqrt(5)*n - 1)).sum(n,0,m)
-1/3*(m^3*(3*sqrt(5) - 7) - 3*m^2*(sqrt(5) - 1) - 2*m*(3*sqrt(5) - 2) - 6)/(m^3*(sqrt(5) - 3) - 3*m^2*(sqrt(5) - 1) - m*(sqrt(5) + 3) - 2)
sage: ((n*(n+a+b)*a^n*b^n)/factorial(n+a)/factorial(n+b)).sum(n,1,m)
-(a^(m + 1)*b^(m + 1)*factorial(a + 1)*factorial(b + 1) - ((a^2 + a)*b^2 + (a^2 + a)*b)*factorial(a + m)*factorial(b + m))/(factorial(a + m)*factorial(a + 1)*factorial(b + m)*factorial(b + 1))
sage: F(n, k) = binomial(n,k) * factorial(n) / factorial(k) / factorial(a-k) / f
....: actorial(a+n)
sage: (F(n+1, k) - F(n, k)).sum(k,0,m)
-sum(-(binomial(n + 1, k)*factorial(a + n)*factorial(n + 1) - binomial(n, k)*factorial(a + n + 1)*factorial(n))/(factorial(a - k)*factorial(k)), k, 0, m)/(factorial(a + n + 1)*factorial(a + n))

The last is clearly not solved. The first two seem correct.

I do not claim to add new functionality with this, just the starting point for speed optimizations and for Wilf-Zeilberger, which WOULD be new functionality.

comment:12 Changed 3 years ago by git

  • Commit changed from 7394ee1bee57b6a0a525de62bf8a913bda687aac to e74a4141763cec2b68ce5a27fdfe2650c88b07d4

Branch pushed to git repo; I updated commit sha1. New commits:

4f4a8b5Merge branch 'develop' into t/22090/gosper_algorithm
648e49822174: Interface expression conversion to gamma() and normalization
29446a0Merge branch 'u/rws/interface_expression_conversion_to_gamma___and_normalization' of git://trac.sagemath.org/sage into t/22090/gosper_algorithm
5b729edMerge branch 'develop' into t/22090/gosper_algorithm
11951c822219: pkg version/chksum
91973f122219: giac usage is GO
a178a7522219: doctest fixes
c7eb7ffMerge branch 'develop' into t/22219/upgrade_to_pynac_0_7_4
5fdc5ffMerge branch 't/22219/upgrade_to_pynac_0_7_4' into t/22090/gosper_algorithm
e74a41422090: add gosper_term and WZ_certificate

comment:13 Changed 3 years ago by rws

  • Dependencies set to pynac-0.7.5
  • Description modified (diff)
  • Summary changed from Gosper algorithm to Gosper algorithm and Wilf-Zeilberger certificate

comment:14 Changed 3 years ago by rws

  • Dependencies changed from pynac-0.7.5 to #22174, pynac-0.7.5
  • Description modified (diff)

comment:15 Changed 3 years ago by git

  • Commit changed from e74a4141763cec2b68ce5a27fdfe2650c88b07d4 to 2ef02d41caf973e74598feb5da656aee6a480242

Branch pushed to git repo; I updated commit sha1. New commits:

2ef02d422090: improvements, stress testing

comment:16 Changed 3 years ago by git

  • Commit changed from 2ef02d41caf973e74598feb5da656aee6a480242 to 32d1ca4399e34b129c4743b895684e0b6441795b

Branch pushed to git repo; I updated commit sha1. New commits:

32d1ca422090: more tests in gosper-sum.py

comment:17 Changed 3 years ago by dimpase

Is pynac-0.7.5 a dependence? Is there a ticket for it that should be referred to? Otherwise it's not clear how this can be reviewed.

comment:18 Changed 3 years ago by git

  • Commit changed from 32d1ca4399e34b129c4743b895684e0b6441795b to 8b0684ee66c4396d20f027f1f1053fa29192a968

Branch pushed to git repo; I updated commit sha1. New commits:

fd5ec4dMerge branch 'develop' into t/22090/gosper_algorithm
8b0684eMerge branch 'develop' into t/22090/gosper_algorithm

comment:19 Changed 3 years ago by rws

Pynac-0.7.5 is a dependence to make all doctests work. What you could already review is the Python interface code and the correctness of the doctests.

comment:20 Changed 3 years ago by dimpase

Do you mean to say that 0.7.5 isn't even on trac yet?

comment:21 Changed 3 years ago by rws

I'm still introducing new code and fleshing out bugs in Pynac master. Trying to implement a complex algorithm has been a big benefit for Pynac already.

comment:22 Changed 3 years ago by rws

Anyway, current Pynac git passes all doctests in 7 seconds, so I'll prepare a release.

comment:23 Changed 3 years ago by rws

  • Dependencies changed from #22174, pynac-0.7.5 to #22174, #22364

comment:24 Changed 3 years ago by git

  • Commit changed from 8b0684ee66c4396d20f027f1f1053fa29192a968 to e7eddf7148b0c44f168160bd99990b753f625603

Branch pushed to git repo; I updated commit sha1. New commits:

46697e0pkg version/chksum
e7eddf7Merge branch 'u/rws/upgrade_to_pynac_0_7_5' of git://trac.sagemath.org/sage into t/22090/gosper_algorithm

comment:25 Changed 3 years ago by chapoton

there is a wrong INPUT:: (should be INPUT: with no indentation on the next lines)

comment:26 Changed 3 years ago by git

  • Commit changed from e7eddf7148b0c44f168160bd99990b753f625603 to f307a8aebce7d8cd63f2a5a68f56193c85071784

Branch pushed to git repo; I updated commit sha1. New commits:

5477616Merge branch 'develop' into t/22090/gosper_algorithm
f307a8a22090: doc fix

comment:27 Changed 2 years ago by chapoton

doc (still) does not build

+[dochtml] OSError: [calculus ] docstring of sage.symbolic.expression.Expression.gosper_sum:7: WARNING: Bullet list ends without a blank line; unexpected unindent.

comment:28 Changed 2 years ago by git

  • Commit changed from f307a8aebce7d8cd63f2a5a68f56193c85071784 to 405c107a7f7ce909391b47cba8ad5dfd2388979a

Branch pushed to git repo; I updated commit sha1. New commits:

6c1cec1Merge branch 'develop' into t/22090/gosper_algorithm
405c10722090: cosmetics

comment:29 follow-up: Changed 2 years ago by chapoton

  • you should de-indent the paragraphs after INPUT:
  • {n \choose k} is deprecated latex code, and is going to trigger a patchbot plugin if a patchbot runs on this ticket ; use instead \binom{n}{k}

comment:30 Changed 2 years ago by git

  • Commit changed from 405c107a7f7ce909391b47cba8ad5dfd2388979a to 87714b4616551f3d343e6548656399cd8d4cff1a

Branch pushed to git repo; I updated commit sha1. New commits:

87714b422090: cosmetics

comment:31 in reply to: ↑ 29 Changed 2 years ago by rws

Replying to chapoton:

  • {n \choose k} is deprecated latex code, and is going to trigger a patchbot plugin if a patchbot runs on this ticket ; use instead \binom{n}{k}

Done. Does that plugin also check the output of Sage itself?

sage: latex(binomial(n,k))
{n \choose k}

comment:32 Changed 2 years ago by rws

  • Branch changed from u/rws/gosper_algorithm to u/rws/22090

comment:33 Changed 2 years ago by rws

  • Commit changed from 87714b4616551f3d343e6548656399cd8d4cff1a to f089c1345497165b7a31c9e7c5d0942f217dfc80
  • Milestone changed from sage-7.6 to sage-8.0

Squashed, rebased, and fixed doctest continuation.


New commits:

f089c1322090: Gosper algorithm and Wilf-Zeilberger certificate

comment:34 Changed 2 years ago by chapoton

  • there is a .. MATH block start that is missing a blank line just after it

otherwise, looks good to me. You can set a positive review once the minor change above is done.

comment:35 Changed 2 years ago by chapoton

  • Reviewers set to Frédéric Chapoton

comment:36 Changed 2 years ago by git

  • Commit changed from f089c1345497165b7a31c9e7c5d0942f217dfc80 to 70462e26e4d02bba1bbe8c6264587b564314e417

Branch pushed to git repo; I updated commit sha1. New commits:

70462e222090: cosmetics

comment:37 Changed 2 years ago by rws

  • Status changed from needs_review to positive_review

Thanks for the review!

comment:38 Changed 2 years ago by vbraun

  • Branch changed from u/rws/22090 to 70462e26e4d02bba1bbe8c6264587b564314e417
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.