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:

Status badges

Description (last modified by mhansen)

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)

sage-3620.patch (2.2 KB) - added by was 13 years ago.

Download all attachments as: .zip

Change History (16)

comment:1 Changed 13 years ago by was

  • Milestone set to sage-3.0.5

But note, we may want to use our own implementation since minpoly and charpoly of *matrices* over finite fields in sage is so fast.

comment:2 Changed 13 years ago by was

  • 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 mhansen

  • Description modified (diff)

comment:4 Changed 13 years ago by mhansen

  • Description modified (diff)

comment:5 Changed 13 years ago by was

  • 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 was

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(2n). :-(

http://www.shoup.net/ntl/doc/GF2E.txt

comment:7 Changed 13 years ago by dmharvey

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 was

comment:8 Changed 13 years ago by was

  • 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 was

  1. dmharvey -- i have no clue what the point of your remark is above.
  1. the point of my patch, by the way, is just to be a first tiny step.

comment:10 Changed 13 years ago by mhansen

  • 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 dmharvey

My point is just that computing the matrix and computing its charpoly both take non-negligble time.

comment:12 Changed 13 years ago by mabshoff

  • Resolution set to fixed
  • Status changed from new to closed

Merged in Sage 3.0.4.rc3

comment:13 Changed 13 years ago by robertwb

  • 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 mabshoff

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 mabshoff

  • Resolution set to fixed
  • Status changed from reopened to closed
Note: See TracTickets for help on using tickets.