2006-01-16-pari_ntl_benchmark.txt

THIS IS PARI/NTL Linear algebra benchmark:

Looking at what PARI now does for matrices, it seems like 
it does a lot.  It computes kernels and images pretty
efficiently.   It might be easy to get from the PARI kernel
to the echelon form, depending on the format of the PARI kernel.

Here are some examples of using the SAGE/PARI-C interface to
make matrices over finite fields in PARI and computer their kernel.

First a small example so what is going on is clearer:

sage: k,a = GF(2^8).objgen()
sage: A = MatrixSpace(k,3,5)([k.random_element() for _ in range(3*5)])
sage: A
[                a^5 + a^3 + a^2             a^7 + a^6 + a^2 + 1           a^7 + a^6 + a^4 + a^2                   a^3 + a^2 + a                         a^6 + 1]
[                      a^5 + a^3             a^5 + a^4 + a^2 + 1                       a^6 + a^2             a^7 + a^6 + a^3 + 1                         a^5 + 1]
[        a^7 + a^4 + a^3 + a + 1 a^7 + a^5 + a^4 + a^3 + a^2 + 1   a^7 + a^4 + a^3 + a^2 + a + 1             a^7 + a^4 + a^2 + 1 a^6 + a^5 + a^4 + a^3 + a^2 + a]
sage: B = pari(A)
sage: B
[Mod(Mod(1, 2)*a^5 + Mod(1, 2)*a^3 + Mod(1, 2)*a^2, ...
(a *huge* matrix to look at!)
sage: B.matker()
[Mod(Mod(1, 2)*a^6 + Mod(1, 2)*a^5 + Mod(1, 2)*a^2 + Mod(1, 2)*a + Mod(1, 2),
   ... again *huge*
This looks beter:
sage: B.matker().lift().lift()
[a^6 + a^5 + a^2 + a + 1, a^6 + a^3; 
a^6 + a^4 + a^3 + a^2, a^7 + a^5 + a^4 + a^3 + a^2 + a + 1; 
a^4 + a^2 + 1, a^6 + a^5 + a^4 + a^3; 1, 0; 0, 1]

Note: matrices act from the right in SAGE, so 
sage: A.transpose().kernel()
Vector space of degree 5 and dimension 2 over Finite field in a of size 2^8
Basis matrix:
[                          1                           0                     a^4 + a a^7 + a^6 + a^5 + a^4 + a^2               a^3 + a^2 + a]
[                          0                           1             a^7 + a^4 + a^2         a^5 + a^4 + a^2 + 1     a^7 + a^5 + a^3 + a + 1]

-----

OK, now here's an example to get a sense of speed:

sage: k,a = GF(2^8).objgen()
sage: A = MatrixSpace(k,50,50)([k.random_element() for _ in range(50*50)])
sage: B = pari(A)
sage: time v= B.matker()
Time: CPU 0.69 s, Wall: 0.79 s

With your NTL interface code it did a 100x100 matrix in 0.08 seconds.
So NTL appears to currently be *vastly* faster than PARI 
(even in C library mode) for 
working over finite field extensions.  This is good information
to have. 

--------------

From Martin Albrecht:
I've implemented the NTL GF2E matrices and did some initial benchmarks:

NTL:

  sage: ntl.set_GF2E_modulus(ntl.GF2X([1,1,0,1,1,0,0,0,1]))
  sage: m=ntl.mat_GF2E(100,100,[ ntl.GF2E_random() for i in xrange(100*100) ])
  sage: time m.echelon_form()
  _10 = 100
  Time: CPU 0.08 s, Wall: 0.09 s