Opened 3 years ago

Closed 3 years ago

#25290 closed enhancement (fixed)

Don't use Karatsuba for multiplying polynomials over fraction fields

Reported by: mmezzarobba Owned by:
Priority: minor Milestone: sage-8.3
Component: basic arithmetic Keywords:
Cc: Merged in:
Authors: Marc Mezzarobba Reviewers: Bruno Grenet
Report Upstream: N/A Work issues:
Branch: c897ad5 (Commits, GitHub, GitLab) Commit: c897ad5e74466c7a3fcc6fe69397ec8dd89c5d63
Dependencies: Stopgaps:

Status badges

Description

Before:

sage: P.<x> = QQ[]
sage: Q.<y> = Frac(P)[]
sage: foo = ((-2*x^2 - 2*x + 3)/(x^2 + 1/3*x + 1/4))*y^20 + (-3/2/(-4/5*x^2))*y^19 + ((2/3*x + 4)/(1/8*x^2 - x - 1/7))*y^18 + ((1/16*x^2 + x - 1)/(-x^2 + 2*x - 5))*y^17 + ((
....: -5/716*x^2 - 1/4*x + 1/4)/(-1/2*x^2 + x - 1))*y^16 + ((-x^2 - 13*x)/(x^2 - 8*x - 2))*y^15 + ((x^2 + 4/5*x - 1)/(x^2 - 1/14*x + 1/145))*y^14 + ((-2*x^2 - 1/2*x - 1/2)/(
....: x^2 + x + 1))*y^13 + ((-x^2 + 14*x - 1)/(-6*x + 1/4))*y^12 + ((2*x^2 + 3*x - 2)/(-x^2 + 3*x - 2))*y^11 + ((-x + 1)/(1/4*x + 1/3))*y^10 + ((-1/8*x + 1/45)/(-x^2 - 1/4))
....: *y^9 + ((-9/11*x^2 - 2/7*x + 2/5)/(-4*x - 1))*y^8 + ((-x^2 + 1/2*x - 1)/(-x^2 + 7*x - 28))*y^7 + ((-3*x^2 + 2/25*x - 2)/(7*x^2 + 3/28*x))*y^6 + ((1/14*x^2 - x + 2/5)/(
....: -14*x^2 + 1/6))*y^5 + ((-3/2*x^2 + 3*x)/(1/43*x - 3))*y^4 + ((6*x^2 - 5*x + 1/27)/(1/20*x^2 + 3*x + 3))*y^3 + ((x^2 - 5*x - 4/5)/(2/5*x^2 - 2/9*x - 11/6))*y^2 + ((-1/1
....: 0*x^2 + x)/(-1/4*x^2 + 6*x - 1/2))*y + (43*x^2 + x + 1/3)/(-17/4*x - 6/7)
sage: %time _ = foo^4
CPU times: user 1.28 s, sys: 12 ms, total: 1.29 s
Wall time: 1.29 s

After:

sage: %time _ = foo^4
CPU times: user 991 ms, sys: 0 ns, total: 991 ms
Wall time: 991 ms

Change History (10)

comment:1 Changed 3 years ago by mmezzarobba

  • Status changed from new to needs_review

comment:2 Changed 3 years ago by git

  • Commit changed from 837d8cff12d69f086fdf57230637216d1b55a4bf to c6251c53b4b8f5fa7e9aac50db0a1f7de4292260

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

c6251c5don't use Karatsuba over fraction fields

comment:3 Changed 3 years ago by git

  • Commit changed from c6251c53b4b8f5fa7e9aac50db0a1f7de4292260 to c897ad5e74466c7a3fcc6fe69397ec8dd89c5d63

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

c897ad5don't use Karatsuba over fraction fields

comment:4 follow-up: Changed 3 years ago by bruno

Is it clear why it is a bad idea to use Karatusba's algorithm for polynomial over fraction fields? Since you test only one example, are you sure that this will always fasten the computation?

comment:5 in reply to: ↑ 4 Changed 3 years ago by mmezzarobba

Replying to bruno:

Is it clear why it is a bad idea to use Karatusba's algorithm for polynomial over fraction fields? Since you test only one example, are you sure that this will always fasten the computation?

My reasoning (cf. the commit message) was that Karatsuba's algorithm performs more additions in the base field, but additions in a fraction field are slower than multiplications—typically at least, I can't promise that this holds 100% of the time!

comment:6 follow-up: Changed 3 years ago by bruno

  • Reviewers set to Bruno Grenet
  • Status changed from needs_review to positive_review

I didn't read the full commit message, sorry! The argument makes sense, and my tests show that Karatsuba's algorithm indeed isn't a good idea for FractionFields. I haven't found (yet?) a case where Karatsuba's algorithm is faster...

Looks good to me!

comment:7 follow-up: Changed 3 years ago by alexjbest

Just a thought, how does extracting a common denominator, multiplying over the base integral domain (presumably with Karatsuba then), and putting the common denominators compare in general? That might be a useful approach for general fraction fields?

For comparison I get

sage: P.<x> = QQ[]
....: Q.<y> = Frac(P)[]
....: foo = ((-2*x^2 - 2*x + 3)/(x^2 + 1/3*x + 1/4))*y^20 + (-3/2/(-4/5*x^2))*y^19 + ((2/3*x + 4)/(1/
....: 8*x^2 - x - 1/7))*y^18 + ((1/16*x^2 + x - 1)/(-x^2 + 2*x - 5))*y^17 + ((-5/716*x^2 - 1/4*x + 1/
....: 4)/(-1/2*x^2 + x - 1))*y^16 + ((-x^2 - 13*x)/(x^2 - 8*x - 2))*y^15 + ((x^2 + 4/5*x - 1)/(x^2 -
....: 1/14*x + 1/145))*y^14 + ((-2*x^2 - 1/2*x - 1/2)/(x^2 + x + 1))*y^13 + ((-x^2 + 14*x - 1)/(-6*x
....: + 1/4))*y^12 + ((2*x^2 + 3*x - 2)/(-x^2 + 3*x - 2))*y^11 + ((-x + 1)/(1/4*x + 1/3))*y^10 + ((-1
....: /8*x + 1/45)/(-x^2 - 1/4))*y^9 + ((-9/11*x^2 - 2/7*x + 2/5)/(-4*x - 1))*y^8 + ((-x^2 + 1/2*x -
....: 1)/(-x^2 + 7*x - 28))*y^7 + ((-3*x^2 + 2/25*x - 2)/(7*x^2 + 3/28*x))*y^6 + ((1/14*x^2 - x + 2/5
....: )/(-14*x^2 + 1/6))*y^5 + ((-3/2*x^2 + 3*x)/(1/43*x - 3))*y^4 + ((6*x^2 - 5*x + 1/27)/(1/20*x^2
....: + 3*x + 3))*y^3 + ((x^2 - 5*x - 4/5)/(2/5*x^2 - 2/9*x - 11/6))*y^2 + ((-1/10*x^2 + x)/(-1/4*x^2
....:  + 6*x - 1/2))*y + (43*x^2 + x + 1/3)/(-17/4*x - 6/7)
....:
sage: %time t = ((foo*foo.denominator())^4)/foo.denominator()^4
CPU times: user 451 ms, sys: 2.66 ms, total: 454 ms
Wall time: 463 ms
sage: %time t = foo^4
CPU times: user 1.79 s, sys: 15.7 ms, total: 1.81 s
Wall time: 1.84 s

I didn't try your non-karatsuba version on my laptop yet but given that the speedup is a factor of 4 in this example I believe it is better for this case at least. Maybe this is better on another ticket at any rate?

comment:8 in reply to: ↑ 6 Changed 3 years ago by mmezzarobba

Replying to bruno:

I didn't read the full commit message, sorry! The argument makes sense, and my tests show that Karatsuba's algorithm indeed isn't a good idea for FractionFields. I haven't found (yet?) a case where Karatsuba's algorithm is faster...

In fact, I forgot half of the explanation in my reply: it is no longer true for large degrees that Karatsuba's algorithm does more additions than the naive algorithm, but we'd have to take into account coefficient growth (for both methods) to make a meaningful comparison, and at least the naive method still seems better for example that take several seconds.

comment:9 in reply to: ↑ 7 Changed 3 years ago by mmezzarobba

Replying to alexjbest:

Just a thought, how does extracting a common denominator, multiplying over the base integral domain (presumably with Karatsuba then), and putting the common denominators compare in general? That might be a useful approach for general fraction fields?

I also tried something like that—In fact, I have a draft branch to implement polynomials over fraction fields that use this representation throughout, but I didn't manage to make it fast. But yes, I do think some variant fo that is the way to go!

comment:10 Changed 3 years ago by vbraun

  • Branch changed from u/mmezzarobba/fractions_karatsuba to c897ad5e74466c7a3fcc6fe69397ec8dd89c5d63
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.