Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Performance issue with multivariate GCD for very large polynomials #35

Closed
PoslavskySV opened this issue Mar 7, 2018 · 0 comments · Fixed by #36
Closed

Performance issue with multivariate GCD for very large polynomials #35

PoslavskySV opened this issue Mar 7, 2018 · 0 comments · Fixed by #36
Assignees
Milestone

Comments

@PoslavskySV
Copy link
Owner

PoslavskySV commented Mar 7, 2018

From FORM benchmarks:

Mathematica: 872.407s
Rings: 126594.310s

After debugging, I noticed that 99,9% of time is spent in MultivariatePolynomial#evaluate method, which was used extremely inefficiently for building Vandermonde/LinZip matrices for ZippelGCD (performance dip meets only for very large polys). These will be fixed with the following:

  • use faster evaluation (with no intermediate maps) to obtain univariate result in sparse solvers (e.g. like here and here)
  • use map-based or larger cache for powers in method MultivariatePolynomial#evaluate
  • use sparse Horner scheme instead of cached powers for evaluation of very large polynomials
@PoslavskySV PoslavskySV added this to the 2.3.1 milestone Mar 7, 2018
@PoslavskySV PoslavskySV self-assigned this Mar 7, 2018
@PoslavskySV PoslavskySV changed the title Performance issue with multivariate GCD for vey large polynomials Performance issue with multivariate GCD for very large polynomials Mar 7, 2018
PoslavskySV added a commit that referenced this issue Mar 20, 2018
 - faster evaluation in Zippel interpolation
 - different methods for fast evaluation in MultivariatePolynomialZp64
PoslavskySV added a commit that referenced this issue Mar 20, 2018
PoslavskySV added a commit that referenced this issue Mar 25, 2018
- switch between sparse recursive (Horner) and plain evaluations in Zippel repeated evaluations
- degrees() array is now laze in multivariate polynomials
- minor fixes for ZippelGCDInZ
- fixes some issues in multivariate polynomials data structures

This finally fixes #35
PoslavskySV added a commit that referenced this issue Mar 25, 2018
…nomials (#36)

This fixes #35

- efficient methods for evaluation of multivariate polynomials with the use of sparse recursive Horner scheme
- switch between plain and sparse recursive evaluation methods in repeated evaluations in Zippel algorithm
- make some costly things in multivariate polynomials cacheable (first of all degrees())
- use larger primes (around 60 bit) in modular algorithm over Z when the resulting coefficients are expected to be large
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

Successfully merging a pull request may close this issue.

1 participant