Opened 9 years ago

Closed 15 months ago

#7253 closed defect (wontfix)

inefficient polynomial powering for positive characteristic

Reported by: robertwb Owned by: tbd
Priority: major Milestone: sage-duplicate/invalid/wontfix
Component: algebra Keywords:
Cc: Merged in:
Authors: Reviewers:
Report Upstream: Fixed upstream, in a later stable release. Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by robertwb)

One can take advantage of the fact that (a+b)p = ap + bp to quickly expand fn = fqp * fr (as r<p, and fp is sparse, the resulting product is easy to compute).

See http://groups.google.com/group/sage-support/browse_thread/thread/38c3d619a7684a90

Change History (7)

comment:1 Changed 9 years ago by robertwb

  • Description modified (diff)

comment:2 Changed 3 years ago by kedlaya

  • Report Upstream set to Reported upstream. No feedback yet.

This behavior still appears to be present in 2016. Since the underlying representation of multivariate polynomials over a finite field appears to be in Singular, I've raised the issue upstream:

http://www.singular.uni-kl.de/forum/viewtopic.php?f=10&t=2523

For univariate polynomials over a finite field, the underlying representation is in FLINT, and there this seems to be handled correctly (although I haven't looked at the source or asked a developer to confirm):

sage: F = GF(7)
sage: P.<x> = PolynomialRing(F)
sage: u = (x^3 + 1)^3
sage: time v = u^(7^7); # a large power!
CPU times: user 1.17 s, sys: 44 ms, total: 1.21 s
Wall time: 1.21 s
sage: time v = u^1000000; # even larger! 
CPU times: user 1.58 s, sys: 36 ms, total: 1.62 s
Wall time: 1.62 s

comment:3 Changed 17 months ago by kedlaya

  • Report Upstream changed from Reported upstream. No feedback yet. to Fixed upstream, in a later stable release.

This has been resolved upstream (see previous Singular link), so I propose to close this ticket.

comment:4 Changed 16 months ago by kedlaya

  • Milestone changed from sage-wishlist to sage-duplicate/invalid/wontfix

comment:5 Changed 16 months ago by kedlaya

  • Status changed from new to needs_review

comment:6 Changed 16 months ago by roed

  • Status changed from needs_review to positive_review

comment:7 Changed 15 months ago by embray

  • Resolution set to wontfix
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.