Setting up a large GivaroZpz<Integer> field
oliver
This might be a dumb question, but I was wondering if anyone could
tell me how to set up a "GivaroZpz<Integer>" Field with order of some
very large prime (bigger than than what can fit inside a 64 bit
integer).
Thanks,
Oliver
B.David Saunders
to work. The example below, shows construction of large prime fields in 3
representations.
-dave
/** \file examples/fields/big-fields.C
* \author bds
* \brief illustrate three reps of large prime fields
*/
#include "linbox/linbox-config.h"
#include <iostream>
#include "linbox/field/ntl-ZZ_p.h"
#include "linbox/field/modular.h"
#include "linbox/field/givaro-zpz.h"
using namespace LinBox;
using namespace std;
int main() {
integer q;
cout << "Enter modulus: "; cin >> q;
UnparametricField<NTL::ZZ_p> G(q);
NTL::ZZ_p a, b, c;
G.init(a, 23); G.init(b, 22);
G.div(c, a, b);
cout << a << "/" << b << " = " << c << " mod " << q << " in NTL" << endl;
integer d, e, f;
Modular<integer> H(q);
H.init(d, 23); H.init(e, 22); H.div(f, d, e);
cout << d << "/" << e << " = " << f << " mod " << q << " in Modular<integer>"
<< endl;
GivaroZpz<integer> F(q);
F.init(d, 23); F.init(e, 22); F.div(f, d, e);
cout << d << "/" << e << " = " << f << " mod " << q << " in GivaroZpz<integer>
" << endl;
return 0;
oliver
Now I see I am setting up the fields correctly. My problem is I want
to perform operations (ie RANK) on matrices over such a field, but
whenever I set the field order to be greater than what can fit inside
a 32 bit integer, the rank commentator reports the wrong field.
-oliver
Jean-Guillaume Dumas
>
> Thanks,
>
> Now I see I am setting up the fields correctly. My problem is I want
> to perform operations (ie RANK) on matrices over such a field, but
> whenever I set the field order to be greater than what can fit inside
> a 32 bit integer, the rank commentator reports the wrong field.
Yes, I corrected this a few days ago, this was a bug in the linbox
wrapper for givaro.
The patch is in the svn, or you can get it there:
http://ljk.imag.fr/membres/Jean-Guillaume.Dumas/Softwares/Patches/givaro-zpz.h.patch.07092009.
By the way, the rank of olivermatrix2 is
Rank : 78645 over GF (65521) done (1231.53 s)
the sparse elimination method with reordering works well.
Best,
--
Jean-Guillaume Dumas.
____________________________________________________________
Jean-Guill...@imag.fr Tél.: +353 1 716 5318
Université Joseph Fourier Grenoble, France
Claude Shannon Institute, University College Dublin, CASL 1J
Belfield, Dublin 4, Ireland
http://ljk.imag.fr/membres/Jean-Guillaume.Dumas
____________________________________________________________
oliver
I just wanted to ask how you know the integer rank of my matrix is
equal to the rank over GF (65521).
Oliver
On Sep 7, 2:24 am, "Jean-Guillaume Dumas" <Jean-
Guillaume.Du...@imag.fr> wrote:
>
>
>
> > Thanks,
>
> > Now I see I am setting up the fields correctly. My problem is I want
> > to perform operations (ie RANK) on matrices over such a field, but
> > whenever I set the field order to be greater than what can fit inside
> > a 32 bit integer, the rank commentator reports the wrong field.
>
> Yes, I corrected this a few days ago, this was a bug in the linbox
> wrapper for givaro.
> By the way, the rank of olivermatrix2 is
> Rank : 78645 over GF (65521) done (1231.53 s)
>
> the sparse elimination method with reordering works well.
>
> Best,
> --
> Jean-Guillaume Dumas.
> ____________________________________________________________
Jean-Guillaume Dumas
>
> Thank you! That helps a lot.
>
> I just wanted to ask how you know the integer rank of my matrix is
> equal to the rank over GF (65521).
Pardon me, I don't know that this is the integer rank, I just picked
my favorite prime to have an idea ...
Since then I computed it also modulo 1048573 and modulo 2, both also give:
Rank : 78645 over GF (2) done (509.412 s)
Rank : 78645 over GF (1048573) done (1247.48 s)
thus we gain confidence that this is indeed the integer rank.
To improve confidence one could:
-/ Pick other primes
There are e.g. 105099271 primes lower than 2^31, and Hadamard bound
for your matrix is 2^167073, thus less than 1 chance over 629 to pick
a bad prime lower than 2^31 each time.
-/ Pick larger primes
-> slows down computations
-/ Probabilistically compute a set which should contain all the bad primes
-> either by the valence, I have few hopes for this, the matrix seems
not well behaved with this regard
-> or compute the largest invariant factor ...
-/ Use sparse elimination over the integers
-> Unfortunately there, the LinBox version is exponential time in the
worst-case
etc.
Best regards,
--
Jean-Guillaume Dumas.
____________________________________________________________
Jean-Guill...@imag.fr Tél.: +353 1 716 5318