Opened 3 years ago

Last modified 2 years ago

#22090 closed enhancement

Gosper algorithm and Wilf-Zeilberger certificate — at Version 13

Reported by: rws Owned by:
Priority: major Milestone: sage-8.0
Component: symbolics Keywords:
Cc: Merged in:
Authors: Ralf Stephan Reviewers:
Report Upstream: N/A Work issues:
Branch: u/rws/gosper_algorithm (Commits) Commit: e74a4141763cec2b68ce5a27fdfe2650c88b07d4
Dependencies: pynac-0.7.5 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 hypegeometric 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 (13)

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. Resultants should be later computed in Pynac via Singular which apparently uses a subresultant algorithm.

Last edited 3 years ago by rws (previous) (diff)

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
Note: See TracTickets for help on using tickets.