Work at SourceForge, help us to make it a better place! We have an immediate need for a Support Technician in our San Francisco or Denver office.

Close

too complex problem?

Help
2011-11-07
2012-11-20
  • Zoltan Kovacs
    Zoltan Kovacs
    2011-11-07

    Dear Developers,

    I'm new to Reduce. I tried to run the following code on Ubuntu 11.04, 64 bit, own compiled Reduce (rev 1511, -with-csl -with-wx). Here is the code I entered:

    load groebner;
    torder({a1,a2,b1,b2,c1,c2,d1,d2,e1,e2,f1,f2,g1,g2,h1,h2,i1,i2,j1,j2},'lex);
    groebner({a1*(b2 - c2) + a2*( - b1 + c1) + b1*c2 - b2*c1,d1*(e2 - f2) + d2*( - e1 + f1) 
    + e1*f2 - e2*f1,a1*( - e2 + h2) + a2*(e1 - h1) - e1*h2 + e2*h1,b1*(d2 - h2) + b2*( - d1 + h1) + d1*h2 - d2*h1,c1*(d2 - i2) + c2*( - d1 + i1)
    + d1*i2 - d2*i1,a1*( - f2 + i2) + a2*(f1 - i1) - f1*i2 + f2*i1,c1*(e2 - j2) + c2*( - e1 + j1) + e1*j2 - e2*j1,b1*( - f2 + j2) + b2*(f1 - j1) - f1*j2 + f2*j1,a1*(b2*z2 - d2*z2)
    + a2*( - b1*z2 + d1*z2) + b1*d2*z2 - b2*d1*z2 - 1,a1*(b2*z3 - e2*z3) + a2*( - b1*z3 + 
    e1*z3) + b1*e2*z3 - b2*e1*z3 - 1,h1*(i2*z1 - j2*z1) + h2*( - i1*z1 + j1*z1) + i1*j2*z1 - i2*j1*z1 - 1});
    

    The result can be seen here:


    However the calculation stopped after 6 seconds, I got two "Memory access violation detected" errors, but I was unable to continue my work, even by requesting Break. Reduce was still eating my CPU and only exiting helped.

    I also learned that Reduce doesn't like too long lines. About over 512 characters it seems to truncate the input.

    Thank you for your help in advance,
    Zoltan

     
  • Zoltan Kovacs
    Zoltan Kovacs
    2011-11-07

    Sorry, the error message seems to be due to a hardware error on my machine (CPU overheating). However, if this hardware error is not present, the calculation is still very slow (I cannot wait for the result now, but it's over 4 minutes). In Mathematica 8 the calculation requires only 3 seconds.

     
  • Thomas Sturm
    Thomas Sturm
    2011-11-07

    With torder you are not listing all the variables: The z_i are missing.

    What exactly do you want to compute? A comprehensive Groebner basis? The generic case of a comprehensive Groebner system? I suspect the latter. This you can get in a second using

    load_package cgb;
    torder …
    ggsys(…);

    The result is:

    {{z₁²⋅z₂³⋅z₃ - 2⋅z₁²⋅z₂²⋅z₃² + z₁²⋅z₂⋅z₃³ + z₁⋅z₂³⋅z₃² - z₁⋅z₂²⋅z₃³ ≠ 0

       ∧ z₁²⋅z₂³ - 2⋅z₁²⋅z₂²⋅z₃ + z₁²⋅z₂⋅z₃² + z₁⋅z₂³⋅z₃ - z₁⋅z₂²⋅z₃² ≠ 0

       ∧ z₁²⋅z₂²⋅z₃ - z₁²⋅z₂⋅z₃² + z₁⋅z₂²⋅z₃² ≠ 0 ∧ z₁⋅z₂²⋅z₃ - z₁⋅z₂⋅z₃² ≠ 0

       ∧ z₁⋅z₂² - z₁⋅z₂⋅z₃ + z₂²⋅z₃ ≠ 0 ∧ z₁⋅z₂² - z₁⋅z₂⋅z₃ ≠ 0 ∧ z₁⋅z₂⋅z₃ ≠ 0

       ∧ z₁⋅z₂ ≠ 0 ∧ z₁⋅z₃ ≠ 0 ∧ z₁ ≠ 0 ∧ z₂⋅z₃ ≠ 0 ∧ z₂ ≠ 0 ∧ z₃ ≠ 0,

      {z₁³⋅z₂⁴ - 2⋅z₁³⋅z₂³⋅z₃ + z₁³⋅z₂²⋅z₃² + z₁²⋅z₂⁴⋅z₃ - z₁²⋅z₂³⋅z₃²}}}

    Thomas

     
  • Zoltan Kovacs
    Zoltan Kovacs
    2011-11-08

    Dear Thomas,

    Thank you for your kind help!

    Indeed, the z_i variables were missing. So I added them, but the calculation is still very slow. (I'd like to get {1} because there is no common solution for the equations.) I indeed have a hardware problem, but a collegaue of mine also tried to run the code on his machine with the following result:

    I tried it on my machine. When compiling reduce (the newest  with csl - the cgb package isn't found) and trying the groebner command the program crashes after some seconds without any error message.
    When using reduce compiled with psl I can load the cgb package, but the ggsys command makes reduce using all the cpu time and more than 950 MByte of memory for now more than half an hour.
    I'll test if the groebner2 package may help.

    I also tried both Thomas' code and mine as well with a cold CPU and I got the same result as my colleague did.

    Thomas, which Reduce version are you using on approximately how big machine? Do you really get the result immediately?

    By the way, I also wanted to compile Reduce+csl+wx on another machine and I got the following:

    g++  -I/usr/include/freetype2 -fno-strict-aliasing -O2 -Wall -Wno-write-strings  -I/home/kovzol/workspace/reduce-algebra/trunk/cslbuild/i686-unknown-ubuntu11.04-wx/lib/wx/include/i686-pc-linux-gnu-gtk2-unicode-static-2.9 -I/home/kovzol/workspace/reduce-algebra/trunk/cslbuild/i686-unknown-ubuntu11.04-wx/include/wx-2.9 -D_FILE_OFFSET_BITS=64 -D__WXGTK__ -pthread   -L/usr/X11R6/lib -Wl,-hash-style=both -rdynamic  -o   csl arith01.o arith02.o arith03.o arith04.o arith05.o arith06.o arith07.o arith08.o arith09.o arith10.o arith11.o arith12.o char.o cslmpi.o eval1.o eval2.o eval3.o eval4.o fns1.o fns2.o fns3.o print.o cslread.o restart.o sysfwin.o csl.o fasl.o gc.o preserve.o wxfwin.o wxterminal.o termed.o  bytes.o stubs.o  -lnsl -lXrandr -lXcursor -lXext -lX11 -L/usr/lib/i386-linux-gnu -lfreetype -lz -lpthread -lrt -ldl -lXft -lfontconfig  -L/home/kovzol/workspace/reduce-algebra/trunk/cslbuild/i686-unknown-ubuntu11.04-wx/lib -pthread   /home/kovzol/workspace/reduce-algebra/trunk/cslbuild/i686-unknown-ubuntu11.04-wx/lib/libwx_gtk2u_html-2.9.a /home/kovzol/workspace/reduce-algebra/trunk/cslbuild/i686-unknown-ubuntu11.04-wx/lib/libwx_gtk2u_qa-2.9.a /home/kovzol/workspace/reduce-algebra/trunk/cslbuild/i686-unknown-ubuntu11.04-wx/lib/libwx_gtk2u_adv-2.9.a /home/kovzol/workspace/reduce-algebra/trunk/cslbuild/i686-unknown-ubuntu11.04-wx/lib/libwx_gtk2u_core-2.9.a /home/kovzol/workspace/reduce-algebra/trunk/cslbuild/i686-unknown-ubuntu11.04-wx/lib/libwx_baseu_net-2.9.a /home/kovzol/workspace/reduce-algebra/trunk/cslbuild/i686-unknown-ubuntu11.04-wx/lib/libwx_baseu-2.9.a -pthread -L/usr/lib/i386-linux-gnu -lgtk-x11-2.0 -lgdk-x11-2.0 -latk-1.0 -lgio-2.0 -lpangoft2-1.0 -lpangocairo-1.0 -lgdk_pixbuf-2.0 -lcairo -lpango-1.0 -lfreetype -lfontconfig -lgobject-2.0 -lgmodule-2.0 -lgthread-2.0 -lrt -lglib-2.0 -lX11 -lSM -lpng -lz -lwxregexu-2.9-i686-pc-linux-gnu -lwxzlib-2.9-i686-pc-linux-gnu -ldl -lm  
    print.o: In function `Ltmpnam':
    print.c:(.text+0x28dc): warning: the use of `tmpnam' is dangerous, better use `mkstemp'
    wxterminal.o: In function `fwinText::insertNewline()':
    wxterminal.cpp:(.text+0x1eb0): undefined reference to `utf_encode'
    wxterminal.o: In function `fwinText::unicodeInput()':
    wxterminal.cpp:(.text+0x2680): undefined reference to `insert_point'
    wxterminal.cpp:(.text+0x26c0): undefined reference to `utf_encode'
    wxterminal.cpp:(.text+0x26cc): undefined reference to `insert_point'
    wxterminal.cpp:(.text+0x26d7): undefined reference to `insert_point'
    wxterminal.cpp:(.text+0x26f0): undefined reference to `term_unicode_convert'
    wxterminal.cpp:(.text+0x2707): undefined reference to `utf_decode'
    wxterminal.o: In function `fwinText::ctrlXcommand()':
    wxterminal.cpp:(.text+0x552b): undefined reference to `unicode_names'
    wxterminal.cpp:(.text+0x5538): undefined reference to `unicode_names'
    collect2: ld returned 1 exit status
    make: ***  Error 1
    make: ***  Error 2
    make: ***  Error 2
    make: ***  Error 2

    I used the same options for configure as earlier. This is also a 64 bit Ubuntu 11.04.

    Thank you for your kind help in advance,
    Zoltan

     
  • Thomas Sturm
    Thomas Sturm
    2011-11-08

    I am using PSL Reduce on Mac Book Pro with a 2.3 GHz Intel Core 7. It takes about a second. But this was without the z_i considering them as parameters.

    When adding them to the torder declaration, then it takes long for me too.

    Suspecting that the ideal is trivial one would better use a revgradlex term order, but this does not not help here either.

    Are you actually interested in complex or in real solutions?

    Thomas

     
  • Zoltan Kovacs
    Zoltan Kovacs
    2011-11-08

    By omitting the z_i variables I get the following with CSL in 5 seconds on my Dell Inspiron N5010:

    +++ Error attempt to take car of an atom: 2
    

    I guess I should try PSL as well.
    The calculation is for proving the Pappus theorem from elementary geometry by describing collinear points with zero determinants. So I am interested in real solutions.

    Thanks, Zoltan

     
  • Zoltan Kovacs
    Zoltan Kovacs
    2011-11-09

    With PSL I get the same result as my colleague did (long run with no result within a reasonable time). Mathematica, however can solve the problem very quickly (even if I use MonomialOrder -> Lexicographic which is the default):

    kovzol@server:~$ math
    Mathematica 8.0 for Linux x86 (32-bit)
    Copyright 1988-2011 Wolfram Research, Inc.
    In[1]:= Timing[GroebnerBasis[{a1*(b2 - c2) + a2*( - b1 + c1) + b1*c2 - b2*c1,d1*(e2 - f2) + d2*( - e1 + f1) + e1*f2 - e2*f1,a1*( - e2 + h2) + a2*(e1 - h1) - e1*h2 + e2*h1,b1*(d2 - h2) + b2*( - d1 + h1) + d1*h2 - d2*h1,c1*(d2 - i2) + c2*( - d1 + i1)+ d1*i2 - d2*i1,a1*( - f2 + i2) + a2*(f1 - i1) - f1*i2 + f2*i1,c1*(e2 - j2) + c2*( - e1 + j1) + e1*j2 - e2*j1,b1*( - f2 + j2) + b2*(f1 - j1) - f1*j2 + f2*j1,a1*(b2*z2 - d2*z2)+ a2*( - b1*z2 + d1*z2) + b1*d2*z2 - b2*d1*z2 - 1,a1*(b2*z3 - e2*z3) + a2*( - b1*z3 + e1*z3) + b1*e2*z3 - b2*e1*z3 - 1,h1*(i2*z1 - j2*z1) + h2*( - i1*z1 + j1*z1) + i1*j2*z1 - i2*j1*z1 - 1},MonomialOrder -> DegreeReverseLexicographic]]
    Out[1]= {3.30821, {1}}
    

    I just tested that the calculation should be solved quickly if Mathematica can give the answer quickly.

     
  • Zoltan Kovacs
    Zoltan Kovacs
    2011-11-09

    Another results:

    Reduce-PSL gives the result after 2 minutes and 9 seconds on my machine (Intel 4x2666 MHz i5 CPU) by using 3900 MB of memory.

    Reduce-CSL also gives the result after 2 minutes and 29 seconds on an Intel 8x3200 MHz i7 CPU system by using 650 MB of memory. The same system calculates the Mathematica code in 2.52 seconds.

    I think this confirms that CSL is significantly slower for Gröbner basis and also confirms http://reduce-algebra.com/info-package.htm on Lisp (however the factor of 2 seems to be underestimated).

    As a conclusion: the groebner package calculates this problem very slow and also requires too much memory.