factoring can be quite slow randomly

[Martin Albrecht]

Hi,

Paul Zimmermann reported this issue:

http://trac.sagemath.org/sage_trac/ticket/12846

Sage code:

sage: K.<a> = GF(4)
sage: R.<x,y> = K[]
sage: f=(a + 1)*x^145*y^84 + (a + 1)*x^205*y^17 + x^32*y^112 + x^92*y^45
sage: time r=f.factor(proof=False)

Singular code:

ring r = (0,a),(x,y),dp;
minpoly = a^2 + a + 1;
poly f=(a + 1)*x^145*y^84 + (a + 1)*x^205*y^17 + x^32*y^112 + x^92*y^45;
factorize(f);

This code can either take 1 second or not terminate after 1 minute.

Any ideas?

Cheers,
Martin

--
name: Martin Albrecht
_pgp: http://pgp.mit.edu:11371/pks/lookup?op=get&search=0x8EF0DC99
_otr: 47F43D1A 5D68C36F 468BAEBA 640E8856 D7951CCF
_www: http://martinralbrecht.wordpress.com/
_jab: martinr...@jabber.ccc.de

[William Stein]

On Mon, Apr 16, 2012 at 8:14 AM, Martin Albrecht
<martinr...@googlemail.com> wrote:
> Hi,
>
> Paul Zimmermann reported this issue:
>
> http://trac.sagemath.org/sage_trac/ticket/12846
>
> Sage code:
>
> sage: K.<a> = GF(4)
> sage: R.<x,y> = K[]
> sage: f=(a + 1)*x^145*y^84 + (a + 1)*x^205*y^17 + x^32*y^112 + x^92*y^45
> sage: time r=f.factor(proof=False)
>
> Singular code:
>
> ring r = (0,a),(x,y),dp;
> minpoly = a^2 + a + 1;
> poly f=(a + 1)*x^145*y^84 + (a + 1)*x^205*y^17 + x^32*y^112 + x^92*y^45;
> factorize(f);
>
> This code can either take 1 second or not terminate after 1 minute.

I think this isn't recent. My recollection is that Singular has
always "sucked" at multivariate factorization (spectacularly, relative
to Magma, say), since the first time I used it. I remember being in
Kaiserslautern about two years ago, and some very sharp guy was being
hired to rewrite multivariate factorization. Maybe he has made
progress by now. Otherwise, one can hope something will come out of
FLINT.

William

>
> Any ideas?
>
> Cheers,
> Martin
>
> --
> name: Martin Albrecht
> _pgp: http://pgp.mit.edu:11371/pks/lookup?op=get&search=0x8EF0DC99
> _otr: 47F43D1A 5D68C36F 468BAEBA 640E8856 D7951CCF
> _www: http://martinralbrecht.wordpress.com/
> _jab: martinr...@jabber.ccc.de
>

> --
> You received this message because you are subscribed to the Google Groups "libsingular-devel" group.
> To post to this group, send email to libsingu...@googlegroups.com.
> To unsubscribe from this group, send email to libsingular-de...@googlegroups.com.
> For more options, visit this group at http://groups.google.com/group/libsingular-devel?hl=en.
>

--
William Stein
Professor of Mathematics
University of Washington
http://wstein.org

[Martin Albrecht]

Hi,

On Monday 16 Apr 2012, William Stein wrote:
> On Mon, Apr 16, 2012 at 8:14 AM, Martin Albrecht
>
> <martinr...@googlemail.com> wrote:
> > Hi,
> >
> > Paul Zimmermann reported this issue:
> >
> > http://trac.sagemath.org/sage_trac/ticket/12846
> >
> > Sage code:
> >
> > sage: K.<a> = GF(4)
> > sage: R.<x,y> = K[]
> > sage: f=(a + 1)*x^145*y^84 + (a + 1)*x^205*y^17 + x^32*y^112 + x^92*y^45
> > sage: time r=f.factor(proof=False)
> >
> > Singular code:
> >
> > ring r = (0,a),(x,y),dp;
> > minpoly = a^2 + a + 1;
> > poly f=(a + 1)*x^145*y^84 + (a + 1)*x^205*y^17 + x^32*y^112 + x^92*y^45;
> > factorize(f);
> >
> > This code can either take 1 second or not terminate after 1 minute.
>
> I think this isn't recent. My recollection is that Singular has
> always "sucked" at multivariate factorization (spectacularly, relative
> to Magma, say), since the first time I used it. I remember being in
> Kaiserslautern about two years ago, and some very sharp guy was being
> hired to rewrite multivariate factorization. Maybe he has made
> progress by now. Otherwise, one can hope something will come out of
> FLINT.

To clarify (Singular team please correct me if I am wrong): for a long time no
one was dedicated to factoring in the Singular team. With Martin Lee (aka the
very sharp guy :)) this changed. Hence, it is my understanding that it makes
sense to point our performance issues with factoring now. Factoring improved a
lot in the last year or so, e.g. there are no known wrong answers.

[han...@mathematik.uni-kl.de]

Hi,
I tried the example with the current Singular (3-1-4-2) and had
differences in running time of ca. +/- 5 % around 4.3 sec (on a slow
computer).
Martin Lee really did a good job for the factorization over extension
fields. But it is not yet finished: we want to replace NTL by FLINT,
but depend currently on both.

Hans

[Alexander Dreyer]

Hi,

> Martin Lee really did a good job for the factorization over extension
> fields. But it is not yet finished: we want to replace NTL by FLINT,
> but depend currently on both.

Indeed, if the FLINT project in GSoC would succeed, this would be a
major step in that direction.

Regards,
Alexander

--
Dr. rer. nat. Dipl.-Math. Alexander Dreyer

Abteilung "Systemanalyse, Prognose und Regelung"
Fraunhofer Institut f�r Techno- und Wirtschaftsmathematik (ITWM)
Fraunhofer-Platz 1
67663 Kaiserslautern

Telefon +49 (0) 631-31600-4318
Fax +49 (0) 631-31600-1099
E-Mail alexande...@itwm.fraunhofer.de
Internet http://www.itwm.fraunhofer.de/sys/dreyer.html

[Martin Albrecht]

Okay, we are still shipping 3-1-3-3 so perhaps simply upgrading would fix the
issue for us. Thanks!

Cheers,

[han...@mathematik.uni-kl.de]

On Tue, Apr 17, 2012 at 04:07:50PM +0100, Martin Albrecht wrote:
> Okay, we are still shipping 3-1-3-3 so perhaps simply upgrading would fix the
> issue for us. Thanks!

Yes, would be good.
But beware: factory now would like to link with flint,
which requires mpir and mpfr (build with mpir).
But all other place include gmp.h which usually is not mpir...
Maybe that is easier to solve for the sage build environment than for us.

Hans

[Burcin Erocal]

Sage doesn't have FLINT2 yet and FLINT versions 1 and 2 cannot be
installed side by side. This update will have to wait until Sage
updates to FLINT2.

Cheers,
Burcin

[han...@mathematik.uni-kl.de]

It also works without FLINT, maybe the test for FLINT in factory has to
be changed not to mis-identify FLINT1 as FLINT2.

Hans

[Martin Lee]

Hi.
I guess the Singular code should read
ring r = (2,a),(x,y),dp; <- 2

minpoly = a^2 + a + 1;
poly f=(a + 1)*x^145*y^84 + (a + 1)*x^205*y^17 + x^32*y^112 +
x^92*y^45;
factorize(f);

If you try this in 3-1-4-2, it gets stuck. But I fixed it in our git
repo with commit 8011f37.

Martin