22 views

Skip to first unread message

Apr 16, 2012, 11:14:36 AM4/16/12

to libsingu...@googlegroups.com

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

Apr 16, 2012, 5:21:42 PM4/16/12

to libsingu...@googlegroups.com

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.

<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

Apr 17, 2012, 5:01:08 AM4/17/12

to libsingu...@googlegroups.com

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.

Apr 17, 2012, 7:13:44 AM4/17/12

to libsingu...@googlegroups.com

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.

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

Apr 17, 2012, 7:26:51 AM4/17/12

to libsingu...@googlegroups.com, han...@mathematik.uni-kl.de

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.

> 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.

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

Apr 17, 2012, 11:07:50 AM4/17/12

to libsingu...@googlegroups.com

Okay, we are still shipping 3-1-3-3 so perhaps simply upgrading would fix the

issue for us. Thanks!

issue for us. Thanks!

Cheers,

Apr 18, 2012, 7:33:56 AM4/18/12

to libsingu...@googlegroups.com

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.> Okay, we are still shipping 3-1-3-3 so perhaps simply upgrading would fix the

> issue for us. Thanks!

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

Apr 18, 2012, 7:59:40 AM4/18/12

to libsingu...@googlegroups.com

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

Apr 18, 2012, 8:02:33 AM4/18/12

to libsingu...@googlegroups.com

be changed not to mis-identify FLINT1 as FLINT2.

Hans

Apr 24, 2012, 10:14:43 AM4/24/12

to libsingular-devel

Hi.

I guess the Singular code should read

ring r = (2,a),(x,y),dp; <- 2

repo with commit 8011f37.

Martin

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
poly f=(a + 1)*x^145*y^84 + (a + 1)*x^205*y^17 + x^32*y^112 +

x^92*y^45;

factorize(f);

repo with commit 8011f37.

Martin

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu