Hi all;
I'm having difficulty compiling a program to use Wiedemann's method.
I'm using version 1.1.5 rc0. I'm specifying a WiedemannTraits
structure as
I've tried using the solve routine from the solutions interface
similar to the examples:
LinBox::solve(soln, Mat, in, MW);
but when I compile I get a list of over 200 errors.
I tried instantiating the WiedemannSolver explicitly:
WiedemannSolver<Field> ws(F, MW);
ws.solve(Mat, soln, in, cert);
but it gives the same list of errors.
Using a different routine in WiedemannSolver, it compiles fine:
ws.findNullspaceElement(soln, Mat);
However, findNullspaceElement does not seem to apply the
preconditioning method specified in the WiedemannTraits, so it is
unable to compute a solution most of the time with the large sparse
systems I'm working with.
I've included below a short test program that gives the compile
errors.
The compilation fails, because the field your are using is not supported by givaro-extension, in order to run Wiedemann algorithm (extensions are used by the preconditioner).
The way you create a finite field is incorrect: Unparametric<X> is meant to be a characteristic 0 ring. And I have the impression that you are trying to use it for the finite field GF(27).
Can you tell us more about what is you computation domain?
For GF(27), you should use GivaroExtension F (3,3)
Alternatively, you can also use other base field implementation, eg Modular<int>, for GF(3) and create the extension as follows
> Hi all; > I'm having difficulty compiling a program to use Wiedemann's method. > I'm using version 1.1.5 rc0. I'm specifying a WiedemannTraits > structure as
> I've tried using the solve routine from the solutions interface > similar to the examples: > LinBox::solve(soln, Mat, in, MW); > but when I compile I get a list of over 200 errors.
> I tried instantiating the WiedemannSolver explicitly: > WiedemannSolver<Field> ws(F, MW); > ws.solve(Mat, soln, in, cert); > but it gives the same list of errors.
> Using a different routine in WiedemannSolver, it compiles fine: > ws.findNullspaceElement(soln, Mat); > However, findNullspaceElement does not seem to apply the > preconditioning method specified in the WiedemannTraits, so it is > unable to compute a solution most of the time with the large sparse > systems I'm working with.
> I've included below a short test program that gives the compile > errors.
Actually, I want to solve over (Z/nZ), where n is a large composite (ZZ type) with known prime factorization. My plan was to solve the system modulo each prime factor of n and then use CRT to combine the results.
I haven't found too much documentation for Givaro, so I'm just trying to extrapolate the constructions from the examples. This probably isn't the best forum to ask, but are the examples the best source?
> The compilation fails, because the field your are using is not supported > by givaro-extension, in order to run Wiedemann algorithm (extensions are > used by the preconditioner).
> The way you create a finite field is incorrect: > Unparametric<X> is meant to be a characteristic 0 ring. > And I have the impression that you are trying to use it for the finite > field GF(27).
> Can you tell us more about what is you computation domain?
> For GF(27), you should use > GivaroExtension F (3,3)
> Alternatively, you can also use other base field implementation, eg > Modular<int>, for GF(3) > and create the extension as follows
> Let me know if I am completely wrong about your intensions.
> Cheers, > Clément
> Jonathan a écrit : >> Hi all; >> I'm having difficulty compiling a program to use Wiedemann's method. >> I'm using version 1.1.5 rc0. I'm specifying a WiedemannTraits >> structure as
>> I've tried using the solve routine from the solutions interface >> similar to the examples: >> LinBox::solve(soln, Mat, in, MW); >> but when I compile I get a list of over 200 errors.
>> I tried instantiating the WiedemannSolver explicitly: >> WiedemannSolver<Field> ws(F, MW); >> ws.solve(Mat, soln, in, cert); >> but it gives the same list of errors.
>> Using a different routine in WiedemannSolver, it compiles fine: >> ws.findNullspaceElement(soln, Mat); >> However, findNullspaceElement does not seem to apply the >> preconditioning method specified in the WiedemannTraits, so it is >> unable to compute a solution most of the time with the large sparse >> systems I'm working with.
>> I've included below a short test program that gives the compile >> errors.
Sorry, I was actually looking at the wrong module. The linbox doc
directory under field seems to contain the required information,
wrapping the givaro methods.
Thanks for the GivaroExtension suggestion. I'll look into it some
more.
Jonathan
On Mar 6, 1:19 pm, "Jonathan F. Hammell" <jhamm...@cpsc.ucalgary.ca>
wrote:
> Actually, I want to solve over (Z/nZ), where n is a large composite (ZZ
> type) with known prime factorization. My plan was to solve the system
> modulo each prime factor of n and then use CRT to combine the results.
> I haven't found too much documentation for Givaro, so I'm just trying to
> extrapolate the constructions from the examples. This probably isn't
> the best forum to ask, but are the examples the best source?
> Thanks for your help.
> Jonathan
> Clement Pernet wrote:
> > Hi Jonathan,
> > The compilation fails, because the field your are using is not supported
> > by givaro-extension, in order to run Wiedemann algorithm (extensions are
> > used by the preconditioner).
> > The way you create a finite field is incorrect:
> > Unparametric<X> is meant to be a characteristic 0 ring.
> > And I have the impression that you are trying to use it for the finite
> > field GF(27).
> > Can you tell us more about what is you computation domain?
> > For GF(27), you should use
> > GivaroExtension F (3,3)
> > Alternatively, you can also use other base field implementation, eg
> > Modular<int>, for GF(3)
> > and create the extension as follows
> > Let me know if I am completely wrong about your intensions.
> > Cheers,
> > Clément
> > Jonathan a écrit :
> >> Hi all;
> >> I'm having difficulty compiling a program to use Wiedemann's method.
> >> I'm using version 1.1.5 rc0. I'm specifying a WiedemannTraits
> >> structure as
> >> I've tried using the solve routine from the solutions interface
> >> similar to the examples:
> >> LinBox::solve(soln, Mat, in, MW);
> >> but when I compile I get a list of over 200 errors.
> >> I tried instantiating the WiedemannSolver explicitly:
> >> WiedemannSolver<Field> ws(F, MW);
> >> ws.solve(Mat, soln, in, cert);
> >> but it gives the same list of errors.
> >> Using a different routine in WiedemannSolver, it compiles fine:
> >> ws.findNullspaceElement(soln, Mat);
> >> However, findNullspaceElement does not seem to apply the
> >> preconditioning method specified in the WiedemannTraits, so it is
> >> unable to compute a solution most of the time with the large sparse
> >> systems I'm working with.
> >> I've included below a short test program that gives the compile
> >> errors.
try {
// Compute a vector in the kernel of Mat
vector<Field::Element> in(numrows);
vector<Field::Element> v(numcols);
for (long i = 0; i < numcols; i++)
v[i] = RandomBnd(p);
Mat.apply(in, v);
LinBox::solve(soln, Mat, in, MW);
for(long i = 0; i < numcols; i++)
kervec[i] = soln[i] - v[i];
> Sorry, I was actually looking at the wrong module. The linbox doc
> directory under field seems to contain the required information,
> wrapping the givaro methods.
> Thanks for the GivaroExtension suggestion. I'll look into it some
> more.
> Jonathan
> On Mar 6, 1:19 pm, "Jonathan F. Hammell" <jhamm...@cpsc.ucalgary.ca>
> wrote:
> > Actually, I want to solve over (Z/nZ), where n is a large composite (ZZ
> > type) with known prime factorization. My plan was to solve the system
> > modulo each prime factor of n and then use CRT to combine the results.
> > I haven't found too much documentation for Givaro, so I'm just trying to
> > extrapolate the constructions from the examples. This probably isn't
> > the best forum to ask, but are the examples the best source?
> > Thanks for your help.
> > Jonathan
> > Clement Pernet wrote:
> > > Hi Jonathan,
> > > The compilation fails, because the field your are using is not supported
> > > by givaro-extension, in order to run Wiedemann algorithm (extensions are
> > > used by the preconditioner).
> > > The way you create a finite field is incorrect:
> > > Unparametric<X> is meant to be a characteristic 0 ring.
> > > And I have the impression that you are trying to use it for the finite
> > > field GF(27).
> > > Can you tell us more about what is you computation domain?
> > > For GF(27), you should use
> > > GivaroExtension F (3,3)
> > > Alternatively, you can also use other base field implementation, eg
> > > Modular<int>, for GF(3)
> > > and create the extension as follows
> > > Let me know if I am completely wrong about your intensions.
> > > Cheers,
> > > Clément
> > > Jonathan a écrit :
> > >> Hi all;
> > >> I'm having difficulty compiling a program to use Wiedemann's method.
> > >> I'm using version 1.1.5 rc0. I'm specifying a WiedemannTraits
> > >> structure as
> > >> I've tried using the solve routine from the solutions interface
> > >> similar to the examples:
> > >> LinBox::solve(soln, Mat, in, MW);
> > >> but when I compile I get a list of over 200 errors.
> > >> I tried instantiating the WiedemannSolver explicitly:
> > >> WiedemannSolver<Field> ws(F, MW);
> > >> ws.solve(Mat, soln, in, cert);
> > >> but it gives the same list of errors.
> > >> Using a different routine in WiedemannSolver, it compiles fine:
> > >> ws.findNullspaceElement(soln, Mat);
> > >> However, findNullspaceElement does not seem to apply the
> > >> preconditioning method specified in the WiedemannTraits, so it is
> > >> unable to compute a solution most of the time with the large sparse
> > >> systems I'm working with.
> > >> I've included below a short test program that gives the compile
> > >> errors.
The sparse matrix that your are building is the 0 matrix, since your function get_vector does not modify v outside of its scope. LinBox wiedemann algorithm segfaults with a matrix of rank 0 (to be fixed).
Simply replacing
void get_vector(int p, vec_long v, long length) { by void get_vector(int p, vec_long& v, long length) {
makes it work the way you want.
Now I also sugest that you do not set the zero entries, in order to keep the matrix sparse.
After these modifications, the execution raises a Solve Failed exception, which I still did not investigated.
However, I found that we do have a function sampling a vector from the kernel in WiedemannSolver (algorithms/wiedemann.h).
So doing the following WiedemannSolver<Field> WS(F, MW); WS.findNullspaceElement (soln, Mat); for(long i = 0; i < numcols; i++) kervec[i] = soln[i]; seems to work for me. It finds very often the 0 vector when p is small, but this gets better for larger p. A work around could be to loop while you get the 0 vector, although there might be a more clever technique, which is probably not yet implemented.
Sorry for not having driven you directly to this function, since I am not so familiar with this part of the library.
Attached is my version of your code, summarizing the mods I have just described.
> try { > // Compute a vector in the kernel of Mat > vector<Field::Element> in(numrows); > vector<Field::Element> v(numcols); > for (long i = 0; i < numcols; i++) > v[i] = RandomBnd(p); > Mat.apply(in, v); > LinBox::solve(soln, Mat, in, MW);
> for(long i = 0; i < numcols; i++) > kervec[i] = soln[i] - v[i];
> On Mar 6, 2:29 pm, Jonathan <jhamm...@cpsc.ucalgary.ca> wrote:
>> Sorry, I was actually looking at the wrong module. The linbox doc >> directory under field seems to contain the required information, >> wrapping the givaro methods.
>> Thanks for the GivaroExtension suggestion. I'll look into it some >> more.
>> Jonathan
>> On Mar 6, 1:19 pm, "Jonathan F. Hammell" <jhamm...@cpsc.ucalgary.ca> >> wrote:
>>> Actually, I want to solve over (Z/nZ), where n is a large composite (ZZ >>> type) with known prime factorization. My plan was to solve the system >>> modulo each prime factor of n and then use CRT to combine the results.
>>> I haven't found too much documentation for Givaro, so I'm just trying to >>> extrapolate the constructions from the examples. This probably isn't >>> the best forum to ask, but are the examples the best source?
>>> Thanks for your help.
>>> Jonathan
>>> Clement Pernet wrote:
>>>> Hi Jonathan,
>>>> The compilation fails, because the field your are using is not supported >>>> by givaro-extension, in order to run Wiedemann algorithm (extensions are >>>> used by the preconditioner).
>>>> The way you create a finite field is incorrect: >>>> Unparametric<X> is meant to be a characteristic 0 ring. >>>> And I have the impression that you are trying to use it for the finite >>>> field GF(27).
>>>> Can you tell us more about what is you computation domain?
>>>> For GF(27), you should use >>>> GivaroExtension F (3,3)
>>>> Alternatively, you can also use other base field implementation, eg >>>> Modular<int>, for GF(3) >>>> and create the extension as follows
>>>> Let me know if I am completely wrong about your intensions.
>>>> Cheers, >>>> Clément
>>>> Jonathan a écrit :
>>>>> Hi all; >>>>> I'm having difficulty compiling a program to use Wiedemann's method. >>>>> I'm using version 1.1.5 rc0. I'm specifying a WiedemannTraits >>>>> structure as
>>>>> I've tried using the solve routine from the solutions interface >>>>> similar to the examples: >>>>> LinBox::solve(soln, Mat, in, MW); >>>>> but when I compile I get a list of over 200 errors.
>>>>> I tried instantiating the WiedemannSolver explicitly: >>>>> WiedemannSolver<Field> ws(F, MW); >>>>> ws.solve(Mat, soln, in, cert); >>>>> but it gives the same list of errors.
>>>>> Using a different routine in WiedemannSolver, it compiles fine: >>>>> ws.findNullspaceElement(soln, Mat); >>>>> However, findNullspaceElement does not seem to apply the >>>>> preconditioning method specified in the WiedemannTraits, so it is >>>>> unable to compute a solution most of the time with the large sparse >>>>> systems I'm working with.
>>>>> I've included below a short test program that gives the compile >>>>> errors.
