#4627: [with patch, with positive review] CRT_list in HNF dominates computation
-----------------------------------------+----------------------------------
Reporter: ncalexan | Owner: was
Type: enhancement | Status: new
Priority: major | Milestone: sage-3.2.1
Component: linear algebra | Resolution:
Keywords: hermite normal form hnf gcd |
-----------------------------------------+----------------------------------
Changes (by craigcitro):
* summary: [with patch, needs review] CRT_list in HNF dominates
computation => [with patch, with positive
review] CRT_list in HNF dominates computation
Comment:
Looks good! Nick pointed out a nice example of a test case:
BEFORE:
{{{
sage: y = polygen(ZZ)
sage: M.<a> = NumberField(y^20 - 2*y^19 + 10*y^17 - 15*y^16 + 40*y^14 -
64*y^13 + 46*y^12 + 8*y^11 - 32*y^10 + 8*y^9 + 46*y^8 - 64*y^7 + 40*y^6 -
15*y^4 + 10*y^3 - 2*y + 1)
sage: time M.ideal(prod(prime_range(6000,6200))).free_module()
CPU times: user 33.71 s, sys: 2.02 s, total: 35.73 s
Wall time: 36.06 s
Free module of degree 20 and rank 20 over Integer Ring
User basis matrix:
20 x 20 dense matrix over Rational Field
}}}
AFTER:
{{{
sage: y = polygen(ZZ)
sage: M.<a> = NumberField(y^20 - 2*y^19 + 10*y^17 - 15*y^16 + 40*y^14 -
64*y^13 + 46*y^12 + 8*y^11 - 32*y^10 + 8*y^9 + 46*y^8 - 64*y^7 + 40*y^6 -
15*y^4 + 10*y^3 - 2*y + 1)
sage: time M.ideal(prod(prime_range(6000,6200))).free_module()
CPU times: user 0.65 s, sys: 0.05 s, total: 0.70 s
Wall time: 0.70 s
Free module of degree 20 and rank 20 over Integer Ring
User basis matrix:
20 x 20 dense matrix over Rational Field
}}}
Speedup of 50X -- not too shabby! In particular, it seems to apply when
you have really large coefficients compared to the size of the matrix.
(This seems reasonable, given that for small entries, the CRT simply
doesn't get applied that many times, since one has a bound on the size of
the output.)
I added another doctest (which really needs compared between versions with
`%timeit`), and committed the patch in Nick's name.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/4627#comment:3>
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
-~----------~----~----~----~------~----~------~--~---
