Opened 3 years ago

Last modified 2 years ago

#22090 closed enhancement

Gosper algorithm — at Version 8

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: 17c5e409466c4b258e1eb07fc490cf6828dff9ba
Dependencies: 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.

The test file has three tests marked as known bug. Each of them shows an area where the implementation will have to be improved:

  • expressions with algebraic coefficients (i.e. manipulations of polynomials over algebraic fields)
  • the final computation in Gosper's algorithm may result in NaN from 0*inf,0/0 or such. Here a limit computation will give the result. I didn't want to call Maxima from Pynac however.
  • enhancement of GiNaC's resultant implementation

Change History (8)

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