Singular

Dear I. Berna,

as your output shows,
[code]
out of memory in vector::SetLength()
Singular : signal 6 (v: 3040/2007112211):
Segment fault/Bus error occurred at 83f8da1 because of 0 (r:1274263428)
please inform the authors
[/code]
you are using an old version Singular 3-0-4 dating from 2007.

So upgrade to Singular-3-1-1; it you are working with LINUX go there:
http://www.mathematik.uni-kl.de/ftp/pub/Math/Singular/UNIX/

The crash, which you report here, does not occur in Singular 3-1-1,
so I will not trace the bug.

But with your code there is the problem that it may run into an infinite loop
if one is calling it with coprime multivariate polynomials.

[code]
ring R=(0,s), (a,r,u(1..4)), dp;
poly pr1=r3-2r2+r-1; // univariate in r
poly qr1 =diff(pr1,r);

poly pr2=48r3-84r2+42r-(36+s); // univariate in r, with parameter s
poly qr2 =diff(pr2,r);

poly pr3=-r^3+r^2-s*r+u(1)*s+u(2); // mulivar. variables r, u(1),u(2), param. s
poly qr3 =diff(pr3,r);

proc bergcd(poly divisor,poly resto)
{
poly dividendo, mcd;
poly pr,qr = divisor,resto; // store the input

while (resto<>0)
{
dividendo=divisor;
divisor=resto;
resto=reduce(dividendo,std(divisor));
"resto =",resto;
"deg(resto)= ", deg(resto);
"------------------";
division(dividendo,divisor);
read("");
}
mcd=divisor;
"Entrega el mcd entre", pr, "y", qr ," es ", mcd;
return(mcd);
}
[/code]

Press continously RETURN, and finally press CTRL-C in the third example.

[code]
> bergcd(pr1,qr1);
Entrega el mcd entre r^3-2*r^2+r-1 y 3*r^2-4*r+1 es 207/4

> bergcd(pr2,qr2);
Entrega el mcd entre 48*r^3-84*r^2+42*r+(-s-36) y 144*r^2-168*r+42 es (324/49*s^2+19800/49*s+302157/49)

> bergcd(pr3,qr3);
// ..... periodic loop of length 2.
// CTR-C a (abort)
[/code]

For the polynomials pr3,qr3, the rest is again a polynomial in the
variables u(1),u(2). So degree does not drop and the loop does not termiante.

See also
[code]
> ring rxy =0,(x,y),dp;
> poly f = (x+y+1)^2*(x2-y2);

> gcd(f,x+y);
x+y
> bergcd(f,x+y); // OK
x+y

> gcd(f,x+y+1);
x+y+1
> bergcd(f,x+y+1); // OK
x+y+1

// But for coprime multivariate, there is a difference.
> gcd(f,x+y+2);
1
> bergcd(f,x+y+2); // does not terminate
........
[/code]


Summary:

Use Singular's [b]gcd[/b], if you want to compute the gcd of multivariate polynomials,
and instead [b]reduce[/b] you may call [b]divsion[/b]

---
Christian Gorzel

Hi Gorzel:
This is an example: I have programmed my own algorithm to calculate gcd remaining divisions, which is what I need and Singular that would produce the copy below.

[b]//ejemplo_mcd[/b]
ring R=(0,s), (a,r,u(1..4)), dp;

//poly pr=r3-2r2+r-1;
//poly pr=48r3-84r2+42r-(36+s);
poly pr=-r^3+r^2-s*r+u(1)*s+u(2);

poly dividendo;
poly mcd;
poly qr=diff(pr,r);
poly divisor=pr;
poly resto=qr;
poly div_poly;
while (resto<>0)
{
dividendo=divisor;
divisor=resto;
div_poly=reduce(dividendo,std(divisor));
resto=div_poly;
}
mcd=divisor;
"Entrega el mcd entre pr y dpr";
mcd;
[b]
This is result:[/b]
> <"ejemplo_mcd";
out of memory in vector::SetLength()
Singular : signal 6 (v: 3040/2007112211):
Segment fault/Bus error occurred at 83f8da1 because of 0 (r:1274263428)
please inform the authors
trying to restart...
? error occurred in para_singular line 20: `div_poly=reduce(dividendo,std(divisor));`
? last reserved name was `std`
skipping text from `;` error at token `)`
Singular : signal 11 (v: 3040/2007112211):
Segment fault/Bus error occurred at 8361221 because of 0 (r:1274263428)
please inform the authors
trying to restart...

Thank for you help!!

I. Berna

[quote="Guest"]
All this is because I want to calculate the GCD of two polynomials defined by
quotient ring. I have calculated using "reduce", but the calculation is complicated and ends with computer memory, apparently Singular is not foreseen this problem.
Do you know why?
[/quote]

Note the following, as indicated in the Overwiev of zeroset.lib:
[quote]
Overview:
Algorithms for [...] factorization of univariate polynomials over Q(a)[t] where a is an algebraic number.
This library is meant as a preliminary extension of the functionality of Singular for univariate factorization
of polynomials over simple algebraic extensions in characteristic 0.
[/quote]

For some years, factorization over Q(a)[t] is already implemented in the kernel now.
So some commands of this library are somehow outdated/obsolete.

In any case, post your example to see what went wrong.

C.Gorzel

thanks for replying, I found in the library zeroset.lib the gcd calculation procedure called proc EGCDMain, which in turn calls the proc RemainderMain, which executes the function proc SimplifyPoly. From there I could check the calculations you need.
All this is because I want to calculate the GCD of two polynomials defined by
quotient ring. I have calculated using "reduce", but the calculation is complicated and ends with computer memory, apparently Cingular is not foreseen this problem.
Do you know why?

[quote="ber"]I need to know the list of running gcd procedure, someone knows where I can find it? I looked all Singular Liberies, but I can not get it. [/quote]

What does [b]'the list of running gcd procedure'[/b] mean?

[b]5.1.41 gcd[/b] and [b]5.1.28 extgcd[/b] are commands from the singular kernel.
These are not encoded in líbraries but part of the source code in (C/C++).

But you can also inspect the code of the library [b]crypto.lib[/b] (section D.11.3 Teaching)

There you will find implementations for gcd but acting on numbers (not polynommials) only.

[quote]
D.11.3.2 exgcdN compute s,t,d such that d=gcd(a,n)=s*a+t*n
D.11.3.3 eexgcdN T with sum_i L[i]*T[i]=T[n+1]=gcd(L[1],...,L[n])
D.11.3.4 gcdN compute gcd(a,b)
[/quote]

C.Gorzel

Hi, I need to know the list of running gcd procedure, someone knows where I can find it? I looked all Singular Liberia, but I can not get it. I would appreciate your help. Thank you.