|
Size: 2403
Comment:
|
Size: 1869
Comment: change website; page from 2008
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 6: | Line 6: |
| It contains different program modules and is fully compatible with the ["LinBox"] linear algebra library and the Athapascan environment, which permits parallel programming." | It contains different program modules and is fully compatible with the [[LinBox]] linear algebra library and the Athapascan environment, which permits parallel programming." |
| Line 9: | Line 9: |
| http://www-lmc.imag.fr/Logiciels/givaro/ | http://givaro.forge.imag.fr/ |
| Line 12: | Line 12: |
| == Building the Givaro wrapper == Even though Givaro is included in the SAGE standard distribution it is not included into the build process by default. This is due to the fact that SAGE wraps the LinBox wrapper of Givaro and LinBox is not included with SAGE by default but may be installed as optional package. |
`GivaroGFq` is the default implementation for finite extension fields of order $\leq 2^{16}$. |
| Line 15: | Line 14: |
| To build Givaro you will need to install the optional LinBox package: sage -i linbox-1.0.0-20060727 |
= Examples and Performance = On [[http://sage.math.washington.edu|sage.math]] and with SAGE 2.5.1 we get the following timings: |
| Line 18: | Line 17: |
| Then you will need to set the variable DEVEL=True in setup.py. If you type sage -b now the finite_field_ext_givaro.pyx file should be compiled and the linbox module be built. | {{{#!python sage: k.<a> = GF(2^8) sage: type(k) <type 'sage.rings.finite_field_givaro.FiniteField_givaro'> sage: e = a^10 sage: f = a^20 |
| Line 20: | Line 24: |
| == What's covered of Givaro == Right now only the Gfq class is covered by the SAGE wrapper to supply fast finite (extension) field arithmetic. You may construct it similar to the usual finite fields in SAGE: k=linbox.GFq(256,repr="poly"). This k may be used as a base ring for (multivariate) polynomial rings, matrix spaces, etc. |
# extract the loop time sage: time for i in xrange(10^6): _ = e CPU times: user 0.24 s, sys: 0.03 s, total: 0.27 s Wall time: 0.27 |
| Line 24: | Line 29: |
| == Tips, Tricks, and Pitfalls == * linbox.GFq only supports finete fields $k$ of $\#k \leq 2^{16}$ * linbox.GFq offers three ways to perform basic arithmetic. Let $e$ and $f$ be elements of the field $k$. Then the usual $e+f$ performs the most generic addition. A little speedup (~ 10%) may be achieved by calling e.g., e.add(f), which avoids type checks. The fastest method is to use k._add(e.logint(),f.logint()) which does not create new GFq_element instances but returns and accepts ints (which Givaro uses internally to represent finite field elements). |
# the actual task sage: time for i in xrange(10^6): _ = e*f CPU times: user 0.64 s, sys: 0.00 s, total: 0.64 s Wall time: 0.63 }}} To put this in perspective, the same task in MAGMA 2.13-5 on the same machine: {{{ > k<a> := FiniteField(2^8); > e := a^10; > f := a^20; > t:= Cputime(); > for i in [1..1000000] do; r := e; end for; > Cputime(t); 0.190 > t:= Cputime(); > for i in [1..1000000] do; r := e*f; end for; > Cputime(t); 0.280 }}} |
Description
From the Givaro website:
"In the joint CNRS-INRIA / INPG-UJF project APACHE, Givaro is a C++ library for arithmetic and algebraic computations. Its main features are implementations of the basic arithmetic of many mathematical entities: Primes fields, Extensions Fields, Finite Fields, Finite Rings, Polynomials, Algebraic numbers, Arbitrary precision integers and rationals (C++ wrappers over gmp) It also provides data-structures and templated classes for the manipulation of basic algebraic objects, such as vectors, matrices (dense, sparse, structured), univariate polynomials (and therefore recursive multivariate). It contains different program modules and is fully compatible with the LinBox linear algebra library and the Athapascan environment, which permits parallel programming."
Website
Integration into SAGE
GivaroGFq is the default implementation for finite extension fields of order \leq 2^{16}.
Examples and Performance
On sage.math and with SAGE 2.5.1 we get the following timings:
1 sage: k.<a> = GF(2^8)
2 sage: type(k)
3 <type 'sage.rings.finite_field_givaro.FiniteField_givaro'>
4 sage: e = a^10
5 sage: f = a^20
6
7 # extract the loop time
8 sage: time for i in xrange(10^6): _ = e
9 CPU times: user 0.24 s, sys: 0.03 s, total: 0.27 s
10 Wall time: 0.27
11
12 # the actual task
13 sage: time for i in xrange(10^6): _ = e*f
14 CPU times: user 0.64 s, sys: 0.00 s, total: 0.64 s
15 Wall time: 0.63
To put this in perspective, the same task in MAGMA 2.13-5 on the same machine:
> k<a> := FiniteField(2^8); > e := a^10; > f := a^20; > t:= Cputime(); > for i in [1..1000000] do; r := e; end for; > Cputime(t); 0.190 > t:= Cputime(); > for i in [1..1000000] do; r := e*f; end for; > Cputime(t); 0.280