Re: GSoC applications for lmonade
100 views
Skip to first unread message
Burcin Erocal
Mar 27, 2014, 8:45:07 AM3/27/14
to Marco Cecchetti, lmnd-...@googlegroups.com, Severin Neumann, Martin Albrecht
Hi Marco,
I'm CC'ing lmnd-devel@, as well as Severin and Martin who can help
mentor this project.
On Thu, 27 Mar 2014 12:41:50 +0100
Marco Cecchetti <mrce...@gmail.com> wrote:
> Hi Burcin,
> thank you for having pointed out the misleading message.If the
> deadline date is next Monday, I think I need to tackle a task soon.
> Please, could you, or whoever wants to mentor for Groebner Basis
> project, assign one to me ? I would prefer something realated to the
> project, for instance something related to Severin's ParallelGBC
> implementation.
Here are two small tasks Severin suggested in an email quite a while
ago. I don't know if there was any progress on these issues in the mean
time:
----------------
- Generalization of the CoeffField. Currently it is only useable only
for prime fields F_p with a fix possible size of bits.
Since also M4RI/M4RIE and Daniel's linear algebra part of F4v6 are
candidates for the framework this is one requirement.
One way to achieve this is to use inheritance, another is templates. I
think the first one should be preferred, the second
one could maybe(!) have a better performance
- Serialization and Deserialization of intermediate results: One nice
future might be the possibility to stop a computation after
n steps and save the current result (Gröbner basis, remaining
S-polynomials, ...) in a format which could be used to continue
computation. This is especially interesting if one wants to redo a
certain degree again and again, for finding bugs or create
specific timings for the matrix of this degree.
----------------
> Unfortunately I still lack a tentative time-line for the project.
> I have a good knowledge of Groebner bases theory and of the
> Buchberger's algorithm, but it is difficult to get a good idea of the
> project without reading a lot of articles, and existent algorithm
> implementations.
>
> I gave a quick look at all references listed on the Groebner bases
> project page. Only Faugère-Lachartre in LELA and Daniel Cabarcas'
> F4v6 are complete implementations, the other ones look more
> interesting for their implementation of algorithms about echelon
> reduced form.
IIRC, the Faugère-Lachartre implementation in LELA is also only the
linear algebra part. LELA is a Library for Exact Linear Algebra after
all.
The project is all about plugging different linear algebra engines into
ParallelGBC and comparing their performance. There can be improvements
in the bookkeeping part as well, but that is an independent task we
didn't include in the scope.
> I browsed most of ParallelGBC source code and I gave a glance to
> Bjarke's documentation paper about MathicGB. My idea would be to
> enhance ParallelGBC, making it more modularized. In order to achieve
> this goal I would exploit modern C++ features (e.g. templates, move
> semantics, etc).
>
> A possible list of deliverables could be:
>
> 1) Implement support for different type of coefficients.
> 2) make the various algorithms listed in the Groebner bases project
> independent by the frameworks they belong to.
> 3) modularize the F4 implementation, by providing a simple way to
> plug in different implementation of the reduction step.
> 4) modularize ParallelGBC in order to make it supports several
> parallel computation technologies.
What do you mean by the last one?
These sound good overall. But as you mention below, you need to be more
concrete and come up with a feasible looking plan of how to get there.
Note that we don't expect you to write a perfect proposal from scratch
all on your own. You need to start talking to the mentors early and
decide on the milestones and timeline with their help. Writing good
proposals is also a skill that needs to be learned. IMHO, that is the
first stage of mentoring we provide in the GSoC. :)
> I know it should be a bit more elaborated, but as I said there is a
> lot of stuff to read. I hope that my previous GSoC experiences and my
> mathematical background are worth something.
> I have not yet received no comment about my project proposal, is that
> a bad sign ?
It's OK to refine the proposal after the application deadline, but your
proposal needs a lot of work. You will need to work very hard (that's
very much an understatement) to make up for the difference if you want
to make the cut.
Cheers,
Burcin
I'm CC'ing lmnd-devel@, as well as Severin and Martin who can help
mentor this project.
On Thu, 27 Mar 2014 12:41:50 +0100
Marco Cecchetti <mrce...@gmail.com> wrote:
> Hi Burcin,
> thank you for having pointed out the misleading message.If the
> deadline date is next Monday, I think I need to tackle a task soon.
> Please, could you, or whoever wants to mentor for Groebner Basis
> project, assign one to me ? I would prefer something realated to the
> project, for instance something related to Severin's ParallelGBC
> implementation.
Here are two small tasks Severin suggested in an email quite a while
ago. I don't know if there was any progress on these issues in the mean
time:
----------------
- Generalization of the CoeffField. Currently it is only useable only
for prime fields F_p with a fix possible size of bits.
Since also M4RI/M4RIE and Daniel's linear algebra part of F4v6 are
candidates for the framework this is one requirement.
One way to achieve this is to use inheritance, another is templates. I
think the first one should be preferred, the second
one could maybe(!) have a better performance
- Serialization and Deserialization of intermediate results: One nice
future might be the possibility to stop a computation after
n steps and save the current result (Gröbner basis, remaining
S-polynomials, ...) in a format which could be used to continue
computation. This is especially interesting if one wants to redo a
certain degree again and again, for finding bugs or create
specific timings for the matrix of this degree.
----------------
> Unfortunately I still lack a tentative time-line for the project.
> I have a good knowledge of Groebner bases theory and of the
> Buchberger's algorithm, but it is difficult to get a good idea of the
> project without reading a lot of articles, and existent algorithm
> implementations.
>
> I gave a quick look at all references listed on the Groebner bases
> project page. Only Faugère-Lachartre in LELA and Daniel Cabarcas'
> F4v6 are complete implementations, the other ones look more
> interesting for their implementation of algorithms about echelon
> reduced form.
IIRC, the Faugère-Lachartre implementation in LELA is also only the
linear algebra part. LELA is a Library for Exact Linear Algebra after
all.
The project is all about plugging different linear algebra engines into
ParallelGBC and comparing their performance. There can be improvements
in the bookkeeping part as well, but that is an independent task we
didn't include in the scope.
> I browsed most of ParallelGBC source code and I gave a glance to
> Bjarke's documentation paper about MathicGB. My idea would be to
> enhance ParallelGBC, making it more modularized. In order to achieve
> this goal I would exploit modern C++ features (e.g. templates, move
> semantics, etc).
>
> A possible list of deliverables could be:
>
> 1) Implement support for different type of coefficients.
> 2) make the various algorithms listed in the Groebner bases project
> independent by the frameworks they belong to.
> 3) modularize the F4 implementation, by providing a simple way to
> plug in different implementation of the reduction step.
> 4) modularize ParallelGBC in order to make it supports several
> parallel computation technologies.
What do you mean by the last one?
These sound good overall. But as you mention below, you need to be more
concrete and come up with a feasible looking plan of how to get there.
Note that we don't expect you to write a perfect proposal from scratch
all on your own. You need to start talking to the mentors early and
decide on the milestones and timeline with their help. Writing good
proposals is also a skill that needs to be learned. IMHO, that is the
first stage of mentoring we provide in the GSoC. :)
> I know it should be a bit more elaborated, but as I said there is a
> lot of stuff to read. I hope that my previous GSoC experiences and my
> mathematical background are worth something.
> I have not yet received no comment about my project proposal, is that
> a bad sign ?
It's OK to refine the proposal after the application deadline, but your
proposal needs a lot of work. You will need to work very hard (that's
very much an understatement) to make up for the difference if you want
to make the cut.
Cheers,
Burcin
Marco Cecchetti
Mar 27, 2014, 12:37:52 PM3/27/14
to Burcin Erocal, lmnd-...@googlegroups.com, Severin Neumann, Martin Albrecht
Il 27/03/2014 13:45, Burcin Erocal ha scritto:
> Hi Marco,
Hi Burcin,
> I'm CC'ing lmnd-devel@, as well as Severin and Martin who can help
> mentor this project.
or suggesting any other task, I would really appreciate, and start
working on one of them.
>
skip
>
>> I browsed most of ParallelGBC source code and I gave a glance to
>> Bjarke's documentation paper about MathicGB. My idea would be to
>> enhance ParallelGBC, making it more modularized. In order to achieve
>> this goal I would exploit modern C++ features (e.g. templates, move
>> semantics, etc).
>>
>> A possible list of deliverables could be:
>>
>> 1) Implement support for different type of coefficients.
>> 2) make the various algorithms listed in the Groebner bases project
>> independent by the frameworks they belong to.
>> 3) modularize the F4 implementation, by providing a simple way to
>> plug in different implementation of the reduction step.
>> 4) modularize ParallelGBC in order to make it supports several
>> parallel computation technologies.
>
> What do you mean by the last one?
surely it provides good performance, anyway it would be interesting to
make the implementation as independent as possible by the utilized
concurrent library.
> These sound good overall. But as you mention below, you need to be more
> concrete and come up with a feasible looking plan of how to get there.
>
> Note that we don't expect you to write a perfect proposal from scratch
> all on your own. You need to start talking to the mentors early and
> decide on the milestones and timeline with their help. Writing good
> proposals is also a skill that needs to be learned. IMHO, that is the
> first stage of mentoring we provide in the GSoC. :)
>
achieving a deep knowledge of the concepts related to this project, and
for getting a clear view of all the details.
>> I know it should be a bit more elaborated, but as I said there is a
>> lot of stuff to read. I hope that my previous GSoC experiences and my
>> mathematical background are worth something.
>> I have not yet received no comment about my project proposal, is that
>> a bad sign ?
>
> It's OK to refine the proposal after the application deadline, but your
> proposal needs a lot of work. You will need to work very hard (that's
> very much an understatement) to make up for the difference if you want
> to make the cut.
proposal.
>
> Cheers,
> Burcin
Cheers,
-- Marco
Severin Neumann
Mar 28, 2014, 8:00:22 AM3/28/14
to Marco Cecchetti, Burcin Erocal, lmnd-...@googlegroups.com, Severin Neumann, Martin Albrecht
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA512
Hi Marco,
short reply today, some updates later:
>> - Generalization of the CoeffField. Currently it is only useable
>> only for prime fields F_p with a fix possible size of bits. Since
>> also M4RI/M4RIE and Daniel's linear algebra part of F4v6 are
>> candidates for the framework this is one requirement. One way to
>> achieve this is to use inheritance, another is templates. I think
>> the first one should be preferred, the second one could maybe(!)
>> have a better performance
>>
>> - Serialization and Deserialization of intermediate results: One
>> nice future might be the possibility to stop a computation after
>> n steps and save the current result (Gröbner basis, remaining
>> S-polynomials, ...) in a format which could be used to continue
>> computation. This is especially interesting if one wants to redo
>> a certain degree again and again, for finding bugs or create
>> specific timings for the matrix of this degree.
>>
>
> They look both interesting, if Severin could update me on their
> state, or suggesting any other task, I would really appreciate, and
> start working on one of them.
Both tasks are still open, so I would be happy, if you can implement
one or both.
>>> I browsed most of ParallelGBC source code and I gave a glance
>>> to Bjarke's documentation paper about MathicGB. My idea would
>>> be to enhance ParallelGBC, making it more modularized. In order
>>> to achieve this goal I would exploit modern C++ features (e.g.
>>> templates, move semantics, etc).
>>>
>>> A possible list of deliverables could be:
>>>
>>> 1) Implement support for different type of coefficients. 2)
>>> make the various algorithms listed in the Groebner bases
>>> project independent by the frameworks they belong to. 3)
>>> modularize the F4 implementation, by providing a simple way to
>>> plug in different implementation of the reduction step. 4)
>>> modularize ParallelGBC in order to make it supports several
>>> parallel computation technologies.
>>
>> What do you mean by the last one?
>
> Well, for instance I see that ParallelGBC utilizes Intel TBB
> library, surely it provides good performance, anyway it would be
> interesting to make the implementation as independent as possible
> by the utilized concurrent library.
3) + 4) are the same task, my implementation of the reduction step
should be only one within the framework. So by taking a different
implementation for the reduction step, the IntelTBB shouldn't be a
requirement.
Things become more difficult if you consider distributed computations
Regards,
Severin
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.22 (GNU/Linux)
iQJ8BAEBCgBmBQJTNWRWXxSAAAAAAC4AKGlzc3Vlci1mcHJAbm90YXRpb25zLm9w
ZW5wZ3AuZmlmdGhob3JzZW1hbi5uZXRCNkMwNkY0MEIyNzNEOTg0RUQyRkU4RTJE
Mjg4NDQ2RTJCNzhGQjk4AAoJENKIRG4rePuYf5sP/1of+PHPPy9jOznHoU2w1o06
+XhaH8SUk0Lv5c2S1xam3RD6ARsWF/OciS2ij4cJvLsjuYP//dPHzTf2TZRJvUyX
nr8FOs39ez7YRgjg/JCCP0VMJH9+Gzm3jmZxix0YGm9qjjm7GMLgaYs50OxaKjop
CmRz9dmHpWcroP2pNEIMHE3pa71XaOxwsknGUVj1DEfoI1CdvbVjiMUCDgGvRIza
FMCuUvKdhy5b7UKuRIZlgvqreHcJQsxEn8JzSI55tHnCQtMcSzTO0TU6nxRP4fYa
iUmRiWvs1NRU3EMb/UKH+D6mgN6u39PPct79ML/sW+zLuXQuKHzynswbNIAqVaRC
1x2Bd9RIEOdQj54r8Bina3UsyWyrJ4ubPnbORXDDN5pqjFD5SIMLxYL7/VvZO5zU
Bruaxw6RRld+G3TnEXTmzOxGXnDINlJS1sqfy7GUCnHHQXEZYiGNLCZOfBzNrqFE
fB6IXE/rfzHhhFDSY3dOGMun9/HfK24QYAQINn+hYq4nlsTei4XSo15ZCkvTiD2J
PZZWJIMkkqKIgm/CtIw7G2RKmvXMUYuVhOfWzRRpgFFvDewGC6bIVYRw0+3giwqs
+mBbWH0e5pIyxV0XcRqwfqdmsj7DmghIuPnWfQWH9DDQ6SvwNUPDwOCEL1yVrhBd
Ov6pFTp8o8faPs23TVLh
=YxJa
-----END PGP SIGNATURE-----
Hash: SHA512
Hi Marco,
short reply today, some updates later:
>> - Generalization of the CoeffField. Currently it is only useable
>> only for prime fields F_p with a fix possible size of bits. Since
>> also M4RI/M4RIE and Daniel's linear algebra part of F4v6 are
>> candidates for the framework this is one requirement. One way to
>> achieve this is to use inheritance, another is templates. I think
>> the first one should be preferred, the second one could maybe(!)
>> have a better performance
>>
>> - Serialization and Deserialization of intermediate results: One
>> nice future might be the possibility to stop a computation after
>> n steps and save the current result (Gröbner basis, remaining
>> S-polynomials, ...) in a format which could be used to continue
>> computation. This is especially interesting if one wants to redo
>> a certain degree again and again, for finding bugs or create
>> specific timings for the matrix of this degree.
>>
>
> They look both interesting, if Severin could update me on their
> state, or suggesting any other task, I would really appreciate, and
> start working on one of them.
one or both.
>>> I browsed most of ParallelGBC source code and I gave a glance
>>> to Bjarke's documentation paper about MathicGB. My idea would
>>> be to enhance ParallelGBC, making it more modularized. In order
>>> to achieve this goal I would exploit modern C++ features (e.g.
>>> templates, move semantics, etc).
>>>
>>> A possible list of deliverables could be:
>>>
>>> 1) Implement support for different type of coefficients. 2)
>>> make the various algorithms listed in the Groebner bases
>>> project independent by the frameworks they belong to. 3)
>>> modularize the F4 implementation, by providing a simple way to
>>> plug in different implementation of the reduction step. 4)
>>> modularize ParallelGBC in order to make it supports several
>>> parallel computation technologies.
>>
>> What do you mean by the last one?
>
> Well, for instance I see that ParallelGBC utilizes Intel TBB
> library, surely it provides good performance, anyway it would be
> interesting to make the implementation as independent as possible
> by the utilized concurrent library.
should be only one within the framework. So by taking a different
implementation for the reduction step, the IntelTBB shouldn't be a
requirement.
Things become more difficult if you consider distributed computations
Regards,
Severin
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.22 (GNU/Linux)
iQJ8BAEBCgBmBQJTNWRWXxSAAAAAAC4AKGlzc3Vlci1mcHJAbm90YXRpb25zLm9w
ZW5wZ3AuZmlmdGhob3JzZW1hbi5uZXRCNkMwNkY0MEIyNzNEOTg0RUQyRkU4RTJE
Mjg4NDQ2RTJCNzhGQjk4AAoJENKIRG4rePuYf5sP/1of+PHPPy9jOznHoU2w1o06
+XhaH8SUk0Lv5c2S1xam3RD6ARsWF/OciS2ij4cJvLsjuYP//dPHzTf2TZRJvUyX
nr8FOs39ez7YRgjg/JCCP0VMJH9+Gzm3jmZxix0YGm9qjjm7GMLgaYs50OxaKjop
CmRz9dmHpWcroP2pNEIMHE3pa71XaOxwsknGUVj1DEfoI1CdvbVjiMUCDgGvRIza
FMCuUvKdhy5b7UKuRIZlgvqreHcJQsxEn8JzSI55tHnCQtMcSzTO0TU6nxRP4fYa
iUmRiWvs1NRU3EMb/UKH+D6mgN6u39PPct79ML/sW+zLuXQuKHzynswbNIAqVaRC
1x2Bd9RIEOdQj54r8Bina3UsyWyrJ4ubPnbORXDDN5pqjFD5SIMLxYL7/VvZO5zU
Bruaxw6RRld+G3TnEXTmzOxGXnDINlJS1sqfy7GUCnHHQXEZYiGNLCZOfBzNrqFE
fB6IXE/rfzHhhFDSY3dOGMun9/HfK24QYAQINn+hYq4nlsTei4XSo15ZCkvTiD2J
PZZWJIMkkqKIgm/CtIw7G2RKmvXMUYuVhOfWzRRpgFFvDewGC6bIVYRw0+3giwqs
+mBbWH0e5pIyxV0XcRqwfqdmsj7DmghIuPnWfQWH9DDQ6SvwNUPDwOCEL1yVrhBd
Ov6pFTp8o8faPs23TVLh
=YxJa
-----END PGP SIGNATURE-----
Marco Cecchetti
Mar 31, 2014, 3:09:39 PM3/31/14
to Severin Neumann, Burcin Erocal, lmnd-...@googlegroups.com, Severin Neumann, Martin Albrecht
Hi Severin,
I tried to tackle the serialization task, unfortunately it requires more
time which one could believe. I cannot get it ready for the deadline
time for posting a code sample.
Anyway for implementing serialization I got the decision to utilize
boost::serialization library. After studying several examples I started
implementing serialization for TOrdering and its subclasses. It works.
Now I am trying with TMonoid TermInstance and Term classes, but I got
some odd (and long) compilation error message, with a large template
boilerplate that does not help in catching the failure cause.
As soon as I succeed in getting better result, I will let you know.
Regards,
-- Marco
Severin Neumann
Apr 2, 2014, 3:10:10 AM4/2/14
to Marco Cecchetti, Burcin Erocal, lmnd-...@googlegroups.com, Severin Neumann, Martin Albrecht
Hi Marco,
i think it isn't a good idea to serialize TMonoid, TermInstance and
Term using boost::serialization because you don't need them to save an
intermediate result and they are maybe not prepared for that.
Please have a look at the F4 algorithm (Buchberger's algorithm is also
fine): If you stop computation after a reduction step you only need to
save some informations: the not-yet finished Gröbner basis, the
remaining S-pairs, the ordering and the coefficient field. Finally you
need to store the simplify data or the sugar degree of the polynomials
if you use one of the two. Maybe I forgot something...
If you do /real/ serialization with boost::serialization this is still
not an easy task. But if you chose an parsable intermediate format, you
can just write everything to a file. E.g. store the polynomials in the
input format, the s-pairs als integer tuples, etc.
Regards,
Severin
Am 31.03.2014 21:09, schrieb Marco Cecchetti:
>
> Hi Severin, I tried to tackle the serialization task, unfortunately
> it requires more time which one could believe. I cannot get it
> ready for the deadline time for posting a code sample. Anyway for
> implementing serialization I got the decision to utilize
> boost::serialization library. After studying several examples I
> started implementing serialization for TOrdering and its
> subclasses. It works. Now I am trying with TMonoid TermInstance and
> Term classes, but I got some odd (and long) compilation error
> message, with a large template boilerplate that does not help in
> catching the failure cause. As soon as I succeed in getting better
> result, I will let you know.
>
>
> Regards, -- Marco
>
>
>
> Il 28/03/2014 13:00, Severin Neumann ha scritto: Hi Marco,
i think it isn't a good idea to serialize TMonoid, TermInstance and
Term using boost::serialization because you don't need them to save an
intermediate result and they are maybe not prepared for that.
Please have a look at the F4 algorithm (Buchberger's algorithm is also
fine): If you stop computation after a reduction step you only need to
save some informations: the not-yet finished Gröbner basis, the
remaining S-pairs, the ordering and the coefficient field. Finally you
need to store the simplify data or the sugar degree of the polynomials
if you use one of the two. Maybe I forgot something...
If you do /real/ serialization with boost::serialization this is still
not an easy task. But if you chose an parsable intermediate format, you
can just write everything to a file. E.g. store the polynomials in the
input format, the s-pairs als integer tuples, etc.
Regards,
Severin
Am 31.03.2014 21:09, schrieb Marco Cecchetti:
>
> Hi Severin, I tried to tackle the serialization task, unfortunately
> it requires more time which one could believe. I cannot get it
> ready for the deadline time for posting a code sample. Anyway for
> implementing serialization I got the decision to utilize
> boost::serialization library. After studying several examples I
> started implementing serialization for TOrdering and its
> subclasses. It works. Now I am trying with TMonoid TermInstance and
> Term classes, but I got some odd (and long) compilation error
> message, with a large template boilerplate that does not help in
> catching the failure cause. As soon as I succeed in getting better
> result, I will let you know.
>
>
> Regards, -- Marco
>
>
>
Reply all
Reply to author
Forward
0 new messages