Re: Fw: About expanding the fplll library

[Martin R. Albrecht]

Hi Arnaud,

I think such a question is best discussed on fplll-devel:

https://groups.google.com/forum/#!forum/fplll-devel

Arnaud Sipasseuth <as...@uowmail.edu.au> writes:
> As explained in the transferred messages I wanted to add the
> computation of the determinant and hermite normal form to fplll
> (for integer matrices only).
>
> You seem to be more active than Damien in the development of the
> library nowadays (he said himself he wasn't active) so I'm
> asking you if you think it is a good idea to add those features.
>
>
> Following Damien's suggestion I looked at linking fplll to
> linpack and it seemed a bit hard for me (I couldn't find quickly
> with a search where the HNF code was).
>
> However linpack uses FLINT as an optional dependency, which
> contains the fmpz_mat module that does everything we want to.
> FLINT, like fplll, have much more than what I want initially and
> FLINT even have their own LLL implementation.
>
> Therefore, using FLINT (linking to FLINT, or look at the code
> inside and implement inside fplll the algorithms themselves and
> referencing it in comments and docs), I was thinking of doing
> several things :

I’d vote against adding dependencies unless absolutely necessary.
C(++) doesn’t have great dependency management and thus adding
dependencies makes it harder to use a bit of code.

AFAIK implementing fast HNF algorithms is non-trivial, but I
agree, it might be nice to have.
>
> -add "-a hnf" to "fplll" to compute the Hermite Normal Form
> (given an integer lattice basis)

Do we need that as a command line option?

> -add "-a det" to "fplll" to compute the Determinant (of an
> integer lattice)

> -add "h n x" to "latticegen" to generate an optimal HNF (one
> single non-trivial column) of dimension n and determinant x

> -add "h n x1 ... xk" to "latticegen" to generate an HNF (one
> single non-trivial column) of dimension n>=k and where the
> diagonal coefficients are x1, x2, ... xk, 1, ... 1.

TBH, I personally don’t have much of an opinion on these. Thus,
CCing fplll-devel. :)

Cheers,
Martin

>
> Do you think it's a good idea ?
>
>
> Kind regards,
>
> Arnaud Sipasseuth


Cheers,
Martin
>
> ________________________________
> From: Damien Stehlé <damien...@gmail.com>
> Sent: Wednesday, 3 January 2018 00:28
> To: Arnaud Sipasseuth
> Subject: Re: About expanding the fplll library
>
> Hi Arnaud
>
> Register to the mailing list. The coding weeks are announced
> there (and on the website too, I think). Note that it's not
> always in Lyon.
>
> Regards
> Damien
>
> Le 2 janv. 2018 12:37, "Arnaud Sipasseuth"
> <as...@uowmail.edu.au<mailto:as...@uowmail.edu.au>> a écrit :
>
> Hi Damien,
>
>
> Thanks for the advice, I searched inside the linbox github and I
> was a bit confused so I contacted Clément Pernet about this (I
> know about FLINT though, which is an optional dependy for
> linbox).
>
>
> Is it possible for me to join one of those somewhat periodic
> coding weeks in Lyon?
>
>
> Happy 2018 to you too!
>
> Kind regards,
>
> Arnaud Sipasseuth
>
> ________________________________
> From: Damien Stehlé
> <damien...@gmail.com<mailto:damien...@gmail.com>>
> Sent: Tuesday, 2 January 2018 4:30:02 AM
> To: Arnaud Sipasseuth
> Subject: Re: About expanding the fplll library
>
> Hi Arnaud,
>
> I'm not involved myself too much in fplll these days, by lack of
> time. But it's very active anyways. See
> https://github.com/fplll/fplll/blob/master/CONTRIBUTING.md
> for how to communicate with the developers and how to
> contribute.
>
> We also have somewhat periodic coding weeks. There was one just
> 2 weeks ago in Lyon, for example.
>
> In my opinion, HNF and determinant computation would be valuable
> inside fplll. Or nice linking to libraries that do that well
> (did you try linbox?).
> It should typically be much faster than LLL and can serve as
> preprocessing.
>
> Regards
> (And happy 2018)
> Damien
>
>
>
> Le 1 janv. 2018 09:03, "Arnaud Sipasseuth"
> <as...@uowmail.edu.au<mailto:as...@uowmail.edu.au>> a écrit :
> Hi Damien,
>
> I am Thomas Plantard's PhD student, and he advised me to contact
> you.
>
> During my PhD, I successfully used your library fplll.
>
> Nevertheless, I still used some other library such as NTL to do
> some other lattice operations I needed to do.
>
> In particular, computing a HNF basis and computing its
> determinant did not seem to be part of your library, and was
> really needed for my tests.
>
> Did you or your staff plan to add such functionality to your
> library?
>
> If not, I was intending to add it for myself.
>
> Would it interest you to also add it to the official library?
>
> In any case, I will be in France until the 19 of February and I
> would be happy to discuss with you about it or even visit you.
>
> Please let me know.
>
> Best regards,
>
> Arnaud.
>
> Télécharger Outlook pour Android<https://aka.ms/ghei36>


--

_pgp: https://keybase.io/martinralbrecht
_www: https://martinralbrecht.wordpress.com
_jab: martinr...@jabber.ccc.de
_otr: 47F43D1A 5D68C36F 468BAEBA 640E8856 D7951CCF

[Arnaud Sipasseuth]

Hello,

For the command line option it's not hard to add once you get the functions, I think it's nice for users who don't do C and just want to use fplll inside a bash script.

[Martin R. Albrecht]

Hi all,

agreed it’s not much to add it so I’m not strongly committed
either way. But for completeness: I’d recommend fpylll for those
use-cases.

In any case, I’m all for having an HNF in fplll.

Cheers,
Martin

[Shi Bai]

Hi Arnaud,

It will be nice to have the HNF code. It also seems good for me to
have the option "-a hnf" in fplll.

Not too sure on computing the determinant. I don't think we need a
specific function for that as dumpgso will almost give that.

Cheers,
Shi

> --
> You received this message because you are subscribed to the Google Groups
> "fplll-devel" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to fplll-devel...@googlegroups.com.
> To post to this group, send email to fplll...@googlegroups.com.
> To view this discussion on the web visit
> https://groups.google.com/d/msgid/fplll-devel/87lgh4k7ax.fsf%40royalholloway.ac.uk.
>
> For more options, visit https://groups.google.com/d/optout.

[Arnaud Sipasseuth]

Hello,

Thanks for the reply, I'll work on HNF then!

[Huck Bennett]

Hi everyone,

From a quick look it seems like HNF did not end up getting added to fplll/fpylll. Is that right?

Assuming not, I'd like to bump this as a feature request too.

- Huck

[Martin R. Albrecht]

Hi Huck,

Yep, we don’t have any HNF implementation right now. Adding *some* should be relatively easy, adding something fast would be non-trivial as AFAIK it requires multi-modular arithmetic so we’d need to import some mod p library, too.

Cheers,
Martin

--

_pgp: https://keybase.io/martinralbrecht
_www: https://malb.io
_prn: he/him or they/them