Opened 13 years ago
Closed 13 years ago
#3620 closed defect (fixed)
[with patch; positive review] minpoly absurdly slow for elements of finte fields
Reported by: | robertwb | Owned by: | tbd |
---|---|---|---|
Priority: | blocker | Milestone: | sage-3.0.4 |
Component: | algebra | Keywords: | |
Cc: | Merged in: | ||
Authors: | Reviewers: | ||
Report Upstream: | Work issues: | ||
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
It goes via pari calls, rather than invoking ntl directly. e.g., computing the minpoly of a random element in GF(2^300) takes about a minute in sage and a second in Magma. It's slow because PARI is really really slow. Just getting the matrix and asking for its charpoly is vastly vaster in sage already, so doing that would be a good first step.
Attachments (1)
Change History (16)
comment:1 Changed 13 years ago by
- Milestone set to sage-3.0.5
comment:2 Changed 13 years ago by
- Description modified (diff)
- Summary changed from minpoly slow for finte fields to minpoly absurdly slow for elements of finte fields
comment:3 Changed 13 years ago by
- Description modified (diff)
comment:4 Changed 13 years ago by
- Description modified (diff)
comment:5 Changed 13 years ago by
- Milestone changed from sage-3.0.5 to sage-3.0.4
- Priority changed from major to blocker
comment:6 Changed 13 years ago by
Here is an example that illustrates the difference:
sage: k.<a> = GF(2^100) sage: time g = k.random_element().charpoly() CPU times: user 1.17 s, sys: 0.02 s, total: 1.18 s Wall time: 1.36 s sage: magma.eval('time f := CharacteristicPolynomial(Random(GF(2^100)));') 'Time: 0.000'
Here's the sage code that does the charpoly computation:
sage: a.charpoly?? from sage.rings.polynomial.polynomial_ring_constructor import PolynomialRing R = PolynomialRing(self.parent().prime_subfield(), var) return R(self._pari_().charpoly('x').lift())
It turns out that pari is just totally abysmal at computing charpolys of Mod's.
sage: f = k.random_element()._pari_() sage: time g = f.charpoly('x') CPU times: user 1.13 s, sys: 0.01 s, total: 1.14 s Wall time: 1.26 s sage: f.type() 't_POLMOD'
Fortunately Sage matrices aren't quite as bad, though of course this is still vastly slower than Magma:
sage: time g = k.random_element().matrix().charpoly() CPU times: user 0.36 s, sys: 0.00 s, total: 0.36 s Wall time: 0.37 s
Asymptotically though this is still vastly better than the current situation:
age: k.<a> = GF(2^200) sage: time g = k.random_element().matrix().charpoly() CPU times: user 2.21 s, sys: 0.03 s, total: 2.24 s Wall time: 2.24 s sage: time g = k.random_element().charpoly() CPU times: user 14.14 s, sys: 0.08 s, total: 14.22 s Wall time: 14.27 s
But still this sucks compared to magma
sage: magma.eval('time f := CharacteristicPolynomial(Random(GF(2^200)));') 'Time: 0.000' sage: magma.eval('time f := CharacteristicPolynomial(Random(GF(2^200)));') 'Time: 0.000' sage: magma.eval('time f := CharacteristicPolynomial(Random(GF(2^300)));') 'Time: 0.000' sage: magma.eval('time f := CharacteristicPolynomial(Random(GF(2^400)));') 'Time: 0.010' sage: magma.eval('time f := CharacteristicPolynomial(Random(GF(2^600)));') 'Time: 0.010' sage: magma.eval('time f := CharacteristicPolynomial(Random(GF(2^1000)));') 'Time: 0.030'
I looked at NTL seems to have no functions at all for charpoly or minpoly of elements of GF(2^{n). :-( }
comment:7 Changed 13 years ago by
also note:
sage: k.<a> = GF(2^500) sage: time g = k.random_element() CPU times: user 0.06 s, sys: 0.00 s, total: 0.06 s Wall time: 0.06 s sage: time m = g.matrix() CPU times: user 11.59 s, sys: 0.82 s, total: 12.41 s Wall time: 12.41 s sage: time f = m.charpoly() CPU times: user 20.51 s, sys: 0.01 s, total: 20.52 s Wall time: 20.51 s
Changed 13 years ago by
comment:8 Changed 13 years ago by
- Summary changed from minpoly absurdly slow for elements of finte fields to [with patch; needs review] minpoly absurdly slow for elements of finte fields
comment:9 Changed 13 years ago by
- dmharvey -- i have no clue what the point of your remark is above.
- the point of my patch, by the way, is just to be a first tiny step.
comment:10 Changed 13 years ago by
- Summary changed from [with patch; needs review] minpoly absurdly slow for elements of finte fields to [with patch; positive review] minpoly absurdly slow for elements of finte fields
Looks good to me. Should there be another ticket for improving this further.
comment:11 Changed 13 years ago by
My point is just that computing the matrix and computing its charpoly both take non-negligble time.
comment:12 Changed 13 years ago by
- Resolution set to fixed
- Status changed from new to closed
Merged in Sage 3.0.4.rc3
comment:13 Changed 13 years ago by
- Resolution fixed deleted
- Status changed from closed to reopened
It looks like NTL does have minimal polynomial computations, though provided in http://www.shoup.net/ntl/doc/GF2X.txt rather than http://www.shoup.net/ntl/doc/GF2E.txt . We should probably use the proof flag to decide the algorithm. Trace could be wrapped as well.
Also, the computation of matrix() is using the completely generic code, which has got to be sub-optimal for manipulating elements of GF(2).
comment:14 Changed 13 years ago by
Robert,
I see no reason to reason to reopen this ticket since what you describe seems to be an improvement/additional change. Please open another ticket since the attached patch has been merged in Sage 3.0.4.
Cheers,
Michael
comment:15 Changed 13 years ago by
- Resolution set to fixed
- Status changed from reopened to closed
But note, we may want to use our own implementation since minpoly and charpoly of *matrices* over finite fields in sage is so fast.