#5213: make charpoly/minpoly of number field elements use matrix()
---------------------------------------------------+------------------------
Reporter: ncalexan | Owner: was
Type: defect | Status: new
Priority: minor | Milestone: sage-3.3
Component: number theory | Resolution:
Keywords: number field element minpoly charpoly |
---------------------------------------------------+------------------------
Comment (by AlexGhitza):
Some experiments indicate that pari is faster (sometimes significantly)
than sage for degrees up to about 20, after which sage becomes
significantly faster than pari. I am attaching a .sage file that has a
tuning function in it. Use it as follows:
{{{
sage: load tune_charpoly_nf
sage: tune_charpoly_nf(dmin=2, dmax=30) # dmin to dmax is the range of
degrees to test
degree = 2
pari wins 4.00543212891e-06
sage 0.000656795501709
degree = 3
pari wins 1.13964080811e-05
sage 0.000749778747559
degree = 4
pari wins 1.55925750732e-05
sage 0.00109262466431
degree = 5
pari wins 3.01837921143e-05
sage 0.00100917816162
degree = 6
pari wins 4.68254089355e-05
sage 0.00144081115723
degree = 7
pari wins 6.31809234619e-05
sage 0.00146918296814
degree = 8
pari wins 0.000140428543091
sage 0.00191378593445
degree = 9
pari wins 0.000134992599487
sage 0.00177617073059
degree = 10
pari wins 0.000328207015991
sage 0.00198397636414
degree = 11
pari wins 0.000636005401611
sage 0.00321359634399
degree = 12
pari wins 0.000763988494873
sage 0.00339140892029
degree = 13
pari wins 0.000882387161255
sage 0.00338182449341
degree = 14
pari wins 0.00109162330627
sage 0.00367736816406
degree = 15
pari wins 0.00157079696655
sage 0.0045955657959
degree = 16
pari wins 0.00219879150391
sage 0.00466103553772
degree = 17
pari wins 0.00490641593933
sage 0.00696640014648
degree = 18
pari wins 0.00486760139465
sage 0.00733642578125
degree = 19
pari wins 0.00619320869446
sage 0.00774478912354
degree = 20
pari wins 0.00522680282593
sage 0.00600438117981
degree = 21
pari 0.0129831790924
sage wins 0.0107915878296
degree = 22
pari 0.0156112194061
sage wins 0.0101305961609
degree = 23
pari 0.0110792160034
sage wins 0.00913519859314
degree = 24
pari 0.0374025821686
sage wins 0.0117425918579
degree = 25
pari 0.0204313755035
sage wins 0.00851321220398
degree = 26
pari 0.0463576316833
sage wins 0.017144203186
degree = 27
pari 0.0754494190216
sage wins 0.0211450099945
degree = 28
pari 0.0682522296906
sage wins 0.0146000385284
degree = 29
pari 0.0482114315033
sage wins 0.016219997406
degree = 30
pari 0.129074573517
sage wins 0.0263453960419
}}}
I hope the output is fairly self-explanatory (the times are in seconds).
The above run, on which it appears that degree=21 is a good point to
switch algorithms, was on my laptop:
{{{
[ghi...@artin 5213]$ uname -a
Linux artin 2.6.28-ARCH #1 SMP PREEMPT Sun Feb 8 10:13:45 UTC 2009 i686
Intel(R) Core(TM)2 Duo CPU T9300 @ 2.50GHz GenuineIntel GNU/Linux
}}}
Michael said he'd run the tuning on a lot of architectures, so we can pick
a switch point for the algorithms.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/5213#comment:5>
Sage <http://sagemath.org/>
Sage - Open Source Mathematical Software: Building the Car Instead of
Reinventing the Wheel
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en
-~----------~----~----~----~------~----~------~--~---
