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:  sage8.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: 
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
 Status changed from new to needs_review
comment:2 Changed 3 years ago by
 Commit changed from 837d8cff12d69f086fdf57230637216d1b55a4bf to c6251c53b4b8f5fa7e9aac50db0a1f7de4292260
comment:3 Changed 3 years ago by
 Commit changed from c6251c53b4b8f5fa7e9aac50db0a1f7de4292260 to c897ad5e74466c7a3fcc6fe69397ec8dd89c5d63
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
c897ad5  don't use Karatsuba over fraction fields

comment:4 followup: ↓ 5 Changed 3 years ago by
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
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 followup: ↓ 8 Changed 3 years ago by
 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 FractionField
s. I haven't found (yet?) a case where Karatsuba's algorithm is faster...
Looks good to me!
comment:7 followup: ↓ 9 Changed 3 years ago by
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 nonkaratsuba 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
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
FractionField
s. 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
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
 Branch changed from u/mmezzarobba/fractions_karatsuba to c897ad5e74466c7a3fcc6fe69397ec8dd89c5d63
 Resolution set to fixed
 Status changed from positive_review to closed
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
don't use Karatsuba over fraction fields