Opened 3 years ago

Closed 3 years ago

#25299 closed defect (fixed)

composed_op is very badly optimized

Reported by: vdelecroix Owned by:
Priority: major Milestone: sage-8.3
Component: algebra Keywords: MathExp2018
Cc: tmonteil Merged in:
Authors: Vincent Delecroix Reviewers: Marc Mezzarobba
Report Upstream: N/A Work issues:
Branch: 8a3bba3 (Commits, GitHub, GitLab) Commit: 8a3bba38b56f5c90bc017b09eb9f2cd0f3b039f5
Dependencies: Stopgaps:

Status badges


Here are two ways to perform the same computation

sage: QQT = QQ['T']
sage: QQXT.<X,T> = QQ['X,T']
sage: p = QQT(8 * T^9 + 4*T^6 - 4*T^3 - 1)
sage: pp = QQXT(p)
sage: q1 = p.composed_op(p, operator.add, algorithm='resultant')
sage: q2 = pp.subs(T=X).resultant(pp(T = T - X))
sage: print(q1 == q2)

Though direct call to resultant is 1000 times faster

sage: %timeit p.composed_op(p, operator.add, algorithm='resultant')
1 loop, best of 3: 1.68 s per loop
sage: %timeit pp(T=X).resultant(pp(T=T-X))
100 loops, best of 3: 2.38 ms per loop

This was found while checking Ramanujan inequality

sage: left = cos(2*pi/7)^(1/3) - (-cos(4*pi/7))^(1/3) - (-cos(8*pi/7))^(1/3)
sage: right = -(-(5 - 3*7^(1/3))/2)^(1/3)
sage: left.n()
sage: right.n()

Change History (4)

comment:1 Changed 3 years ago by vdelecroix

  • Authors set to Vincent Delecroix
  • Branch set to u/vdelecroix/25299
  • Commit set to 8a3bba38b56f5c90bc017b09eb9f2cd0f3b039f5
  • Status changed from new to needs_review

New commits:

8a3bba325299: one character fix!

comment:2 Changed 3 years ago by vdelecroix

And in this example, BFSS is actually faster

sage: %timeit q1 = p.composed_op(p, operator.add, algorithm='BFSS')
1000 loops, best of 3: 1.17 ms per loop

(... for another round)

comment:3 Changed 3 years ago by mmezzarobba

  • Reviewers set to Marc Mezzarobba
  • Status changed from needs_review to positive_review

comment:4 Changed 3 years ago by vbraun

  • Branch changed from u/vdelecroix/25299 to 8a3bba38b56f5c90bc017b09eb9f2cd0f3b039f5
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.