Documentation - Project LinBox

Home
Overview
News
People
Download
Documentation
Developer
Links
Support

GAP homology package
Maple-LinBox package

Online computing servers

Finite Fields in LinBox

The purpose of this page is not to present LinBox Fields as a tutorial or a documentation will do it. We just want to provide a basic support to people interested in using LinBox Fields in the best and simplest way.

What kinds of Fields are in LinBox?

LinBox provides two kinds of finite fields:

  • Prime Fields (Z/pZ)
  • Extension Fields ( GF(p^n))

Each field comes from either extern libraries or Linbox directly.

Available Library plugins in LinBox:

What are the LinBox classes defining Fields ?

Through wrappers using external libraries:

  • Givaro:

    • GivaroZpz<XXX> (XXX taken in {Std32, Std16, Log16})

      This is a template class defining a prime field with elements of type 32-bits integer with STD32 , 16-bits integer with STD16 and LOG16. The classes GivaroZpz<STD32> and GivaroZpz<STD16> use a classical modular arithmetic whereas GivaroZpz<LOG16> uses a totally tabulated arithmetic using a Zech Log representation.

    • GivaroGfq

      This class allows the user to define extension fields with elements of type "standard C" long . This class uses the Zech Log representation and so can only define extension field with a cardinality less than 2^16, since the Zech Log representation needs to tabulate some value.

  • NTL:

    • UnparametricField<XXX> (XXX took in {NTL::zz_p, NTL::ZZ_p})

      This is a template class defining prime fields with elements of type "standard C" long with NTL::zz_p and multi-precision integer with NTL::ZZ_p (based on Ntl multi-precision numbers).

  • LiDIA:

    • LidiaGfq

      This class allows the user to define extension fields with elements of type LiDIA polynomial. So this class represents elements of a field as polynomials and use polynomial arithmetic. The cardinality of field is not restricted but larger it is, the slower the arithmetic operations are.

Directly written in LinBox Library:

  • Modular<XXX> (XXX taken in {uint16, uint32, LinBox::integer})

    This class is a template class defining prime fields where the elements take their type in the class passed in template parameter. Such a class needs to have the overloaded operator (%, =, ==, +, -, *, /, +=, -=, *=, /=) to be passed as template parameter. The class LinBox::integer allows one to use multi-precision arithmetic based on gmp library.

Genericity of LinBox Fields in the library?

Most of the functions and the objects of the LinBox library are templated by a field type. This allows to use any of fields defined in LinBox in a generic way. This is possible because each fields in LinBox is defined according to a field interface which sets names and functions in a Linbox field class. The field interface is defined in a class called "FieldArchetype" in the file /linbox/field/archetype.h in the library.

What is the efficiency of Linbox Fields in the Library?


Performance of LinBox fields, 1 Ghz Pentium III, Solaris 5.8
Field Type Rep. LinBox Class + (Mops) - (Mops) * (Mops) / (Mops) axpy (Mops) Dense Au (Mops) Sparse Au (Mops) Dense AB (Mops)
Z/pZ Simple Precision GivaroZpz <Std32> 50.0 50.0 20.0 1.30 43.2 32.6 22.18 22.22
Modular <uint32> 50.0 50.0 16.0 1.70 42.1 ? 55.44 40.0
GivaroGfq 16.7 14.3 33.3 33.0 35.56 0.46 0.013 0.062
UnparametricField <NTL::zz_p> 20.0 20.0 7.14 15.0 11.1 10.8 9.24 8.695
Multi Precision Modular <LinBox::integer> 2.50 3.33 0.28 0.006 0.33 0.888 0.894 0.836
UnparametricField <NTL::ZZ_p> 2.50 3.33 1.00 0.180 1.00 1.00 1.35 ?
Totally tabulated GivaroZpz <Log16> 33.3 50.0 50.0 33.0 100.0 32.67 ? ?
GF(p^n) Polynomial LidiaGfq 0.714 0.769 0.045 6.80 0.033 0.033 0.05 0.032
Zech Log GivaroGfq 25.0 25.0 50.0 50.0 20.779 0.20 0.00777 0.028

Performance of LinBox fields, 433 Mhz Sun Ultra Sparc IIi
Field Type Rep. LinBox Class + (Mops) - (Mops) * (Mops) / (Mops) axpy (Mops) Dense Au (Mops) Sparse Au (Mops) Dense AB (Mops)
Z/pz Simple Precision GivaroZpz <Std32> 16.7 16.7 3.125 0.170 6.22 5.76 5.04 4.545
Modular <int> 16.7 16.7 3.125 0.270 6.01 ? 12.321 10.526
GivaroGfq 7.14 5.55 14.3 14.0 12.9 0.56 0.021 0.077
UnparametricField <NTL::zz_p> 7.69 8.33 2.38 0.150 3.55 3.63 2.92 3.076
Multi Precision Modular <LinBox::integer> 1.67 1.42 0.07 0.00178 0.093 0.275 0.284 0.256
UnparametricField <NTL::ZZ_p> 2.00 2.00 0.27 0.040 0.25 0.25 0.434 1.60
Totally tabulated GivaroZpz <Log16> 8.33 10.0 16.7 125.0 13.91 12.25 ? ?
GF(p^n) Polynomial LidiaGfq ? ? ? ? ? ? ? ?
Zech Log GivaroGfq 9.10 6.70 14.28 14.0 11.42 0.25 0.01 0.037

These performances have been obtained with these features:

Z/pz:

  • p = 40493 for Simple Precision Arithmetic.
  • p = 8191 for Totally Tabulated Arithmetic.
  • p = 1267650600228229401496703301361 for Multi Precision Arithmetic (about 100 bits).
  • Axpyin used 2 vectors of size : 2000 (for simple precision) and 100 (for multi precision).
  • Dense Au (product of a matrix and a vector) used one matrix of size 700*700 (for simple precision) and 200*200 (for multi precision). and one vector of size 700 (for simple precision) and 200 (for multi precision).
  • Sparse Au used the Trefethen matrix (20000*20000 with approimatively 555000 non-zero elements) and one vector of size : 20000.
  • Dense A*B (product of two matrices) used two matrices of size 100*100 (for simple precision) and 20*20 (for multi precision).

GF(p^n) :

  • p = 17 and n = 4 for Zech Log Arithmetic.
  • p = 17 and n = 6 for Polynomial Arithmetic.
  • Polynomial arithmetic: For each test, the same dimension as a prime field with multi precision arithmetic were used.
  • Zech Log arithmetic: For each test, the same dimension as a prime field with simple precision arithmetic were used.

Valid HTML 4.0! Valid CSS! Comments? Bug reports? Please contact us at linbox@yahoogroups.com
Page prepared by Pascal Giorgi <pascal.giorgi@ens-lyon.fr>
Modifications by Bradford Hovinen <bghovinen@math.uwaterloo.ca>
This page's URL: http://www.linalg.org/field.html
Page created: 30 October 2002
Page last updated: 21 December 2002