ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Wed, 02 Sep 2020 23:41:22 +0200Rewriting linear combination of Groebner basis in terms of original termshttps://ask.sagemath.org/question/53267/rewriting-linear-combination-of-groebner-basis-in-terms-of-original-terms/ Let assume I have an ideal given by
x,y,z = QQ['x,y,z'].gens()
I = ideal(f1,f2,f3)
B = I.groebner_basis()
where f1,f2,f3 are just polynomials in variables x,y,z. Let's say B=(g1,g2).
Let's assume I happen to take a polynomial,h, that is in my ideal I. Then doing polynomial division, I can write
h=h1*g1+h2*g2
Basically I can write h as a linear combination of the elements in my Groebner basis. Is there a function that converts a linear combination in terms of Groebner to linear combination of terms in my ideal I? i.e.I can write
h=q1*f1+q2*f2+q3*f3
whatupmattWed, 02 Sep 2020 23:41:22 +0200https://ask.sagemath.org/question/53267/does sage allow computation of a groebner basis of an ideal J in the quotient ring Z/pZ[X_1,...X_r]/I?https://ask.sagemath.org/question/52493/does-sage-allow-computation-of-a-groebner-basis-of-an-ideal-j-in-the-quotient-ring-zpzx_1x_ri/I define the following rings and ideals:
sage: F = ZZ.quo(3*ZZ); F
Ring of integers modulo 3
sage: A.<X, Y, Z> = PolynomialRing(F); A
Multivariate Polynomial Ring in X, Y, Z
over Ring of integers modulo 3
sage: I = ideal(X^2 - 1, Y^2 - 1, Z^2 - 1); I
Ideal (X^2 + 2, Y^2 + 2, Z^2 + 2)
of Multivariate Polynomial Ring in X, Y, Z
over Ring of integers modulo 3
sage: R = A.quotient_ring(I); R
Quotient of Multivariate Polynomial Ring in X, Y, Z
over Ring of integers modulo 3
by the ideal (X^2 + 2, Y^2 + 2, Z^2 + 2)
sage: x, y, z = R.gens()
sage: J = ideal(x*y + z, x + x*z, x*z + y); J
Ideal (Xbar*Ybar + Zbar, Xbar*Zbar + Xbar, Xbar*Zbar + Ybar)
of Quotient of Multivariate Polynomial Ring in X, Y, Z
over Ring of integers modulo 3
by the ideal (X^2 + 2, Y^2 + 2, Z^2 + 2)
I then compute:
sage: B = J.groebner_basis()
and examine the result of that computation:
sage: B
[Xbar + 2*Ybar, Zbar + 1]
Is it really the Groebner basis of `J`?
Did Sage really compute in A/I and not in A?andriamThu, 16 Jul 2020 11:50:36 +0200https://ask.sagemath.org/question/52493/RuntimeError Groebner basis for a Boolean systemhttps://ask.sagemath.org/question/51072/runtimeerror-groebner-basis-for-a-boolean-system/ Hello everyone,
i've started using sage for a few days and i'm having a rough time trying to use groebner basis with big boolean systems. Right now my goal is to verify the time it takes to solve these systems in this way: keep in mind that these equation are extracted from a cipher, and they are roughly 150 for 130 variables.
var = "x01, x02, x03, x04, x05, x06, x07, x08, x09, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19, x20, x21, x22, x23, x24, x25, x26, x27, x28, x29, x30, x31, x32, x33, x34, x35, x36, x37, x38, x39, x40, x41, x42, x43, x44, x45, x46, x47, x49, x54, x70, x81, x89, x92, x93, y01, y02, y03, y04, y05, y06, y07, y08, y09, y10, y11, y12, y13, y14, y15, y16, y17, y18, y19, y20, y21, y22, y23, y24, y25, y26, y27, y28, y29, y30, y31, y32, y33, y34, y35, y36, y37, y38, y39, y40, y41, y42, y43, y44, y45, y46, y47, y48, y49, y50, y52, y80, y83, y84"
B = BooleanPolynomialRing(var)
System = [B('x93 + y84'), B('x92 +y83'), B('x89 + y80'), B('x54 + x81'), B('x49 + y52')]
I = ideal(System)
G = I.groebner_basis()
The thing is that when i try to call the method 'variety' on the ideal 'I', i get a runtime error (even with this reduced example):
RuntimeError: error in Singular function call 'groebner':
int overflow in hilb 1
error occurred in or before standard.lib::stdhilb line 299: ` intvec hi = hilb( Id(1),1,W );`
expected intvec-expression. type 'help intvec;'
leaving standard.lib::stdhilb
leaving standard.lib::groebner
Do you have any idea why this happens? Or if you have any suggestions with the approach i could take, i'm happy to listen to them.
Thank you in advance for your time.torresMon, 27 Apr 2020 18:59:50 +0200https://ask.sagemath.org/question/51072/Solving Groebner Basis of an ideal that includes parameters with order=lex yields non triangular equationshttps://ask.sagemath.org/question/43808/solving-groebner-basis-of-an-ideal-that-includes-parameters-with-orderlex-yields-non-triangular-equations/From this reference, it seems that a Groebner basis with respect to lexicographic order should yield a 'triangular system': www `dot` scholarpedia.org/article/Groebner_basis. My system has three equations and three unknowns, which I want to transform into a series of three 1-D root finding problems.
R.<x0,x1,x2,x3,x4,x5,x6,x7,x8> = PolynomialRing(QQ)
F=R.fraction_field()
S.<x9,x10,x11> = PolynomialRing(F,order='lex');
I = S.ideal(
-x7*x10*x9 + x8*x2*x11**2 + x3*x0*x11 - x4*x10,
-x7*x10*x9 + x8*x2*x11**2 + 2*x5*x1*x11**2 - 2*x6*x9**2,
2*x7*x10*x9 - 2*x8*x2*x11**2 - x3*x0*x11 + x4*x10 - 2*x5*x1*x11**2 + 2*x6*x9**2
)
B = I.groebner_basis()
print('\n\n'.join(map(str,B)))
This yields four equations (rather than 3) which do not seem to exhibit this triangular property (first three equations mention all three variables x9,x10,x11, and the last one involves both x9 and x10).
x9^2 + ((-x4)/(2*x6))*x10 + ((-2*x1*x5)/(2*x6))*x11^2 + x0*x3/(2*x6)*x11
x9*x10 + x4/x7*x10 + ((-x2*x8)/x7)*x11^2 + ((-x0*x3)/x7)*x11
x9*x11^2 + 2*x0*x3/(2*x2*x8)*x9*x11 + ((-x4*x7)/(2*x2*x6*x8))*x10^2 + ((-2*x1*x5*x7)/(2*x2*x6*x8))*x10*x11^2 + x0*x3*x7/(2*x2*x6*x8)*x10*x11 + 2*x4^2/(2*x2*x7*x8)*x10 + ((-2*x4)/(2*x7))*x11^2 + ((-2*x0*x3*x4)/(2*x2*x7*x8))*x11
x10^3 + 2*x1*x5/x4*x10^2*x11^2 + ((-x0*x3)/x4)*x10^2*x11 + ((-2*x4*x6)/x7^2)*x10^2 + 4*x2*x6*x8/x7^2*x10*x11^2 + 4*x0*x3*x6/x7^2*x10*x11 + ((-2*x2^2*x6*x8^2)/(x4*x7^2))*x11^4 + ((-4*x0*x2*x3*x6*x8)/(x4*x7^2))*x11^3 + ((-2*x0^2*x3^2*x6)/(x4*x7^2))*x11^2
Do I have a misunderstanding about what to expect from Sage's output? Or is there a test to see if my system of equations is pathological in some way?
If I ignore the fact that variables x1...x8 are parameters, I am surprised to get a basis of three equations which is also not triangularizable with respect to x9,x10,x11.
S.<x0,x1,x2,x3,x4,x5,x6,x7,x8,x9,x10,x11> = PolynomialRing(QQ,order='lex');
I = S.ideal(
-x7*x10*x9 + x8*x2*x11**2 + x3*x0*x11 - x4*x10,
-x7*x10*x9 + x8*x2*x11**2 + 2*x5*x1*x11**2 - 2*x6*x9**2,
2*x7*x10*x9 - 2*x8*x2*x11**2 - x3*x0*x11 + x4*x10 - 2*x5*x1*x11**2 + 2*x6*x9**2
)
B = I.groebner_basis()
print('\n\n'.join(map(str,B)))
>>x0*x3*x6*x9^2 + 1/2*x0*x3*x7*x9*x10 - x1*x4*x5*x10*x11 - x1*x5*x7*x9*x10*x11 - 1/2*x2*x4*x8*x10*x11 + x2*x6*x8*x9^2*x11
x0*x3*x11 + x2*x8*x11^2 - x4*x10 - x7*x9*x10
x1*x5*x11^2 + 1/2*x2*x8*x11^2 - x6*x9^2 - 1/2*x7*x9*x10ksbTue, 02 Oct 2018 00:19:02 +0200https://ask.sagemath.org/question/43808/Solving a system of 5 polynomial equationshttps://ask.sagemath.org/question/40346/solving-a-system-of-5-polynomial-equations/I have a system of 5 polynomial equations. I solved the equations in Maple but I'm trying to solve them also in sagemath since it's open source. I've been trying for a long time (weeks) and still couldn't solve the equations in sagemath (Maple finds all the solutions in 10 seconds). I don't need the complex solutions (if exist). only the real solutions.
I have posted before a similar question but with 18 equations and it took Maple 40 minutes to solve them. But since then I was able to reduce the number of equations from 18 to 5. This time Maple solved the equations much faster (10 seconds instead of 40 minutes). But unfortunately, still can't solve the equations with sagemath.
The goal is to find all the possible (real) solutions of the equations. Maple did it and found 20 solutions (the code is attached bellow). But I wasn't able to solve the equations in sagemath at all (I attached the code for sagemath bellow as well).
I tried to use groebner basis in sagemath but there are so many different implementations with different order of the polynomials ('lex', 'degrevlex',etc). I tried many of them and none of them could solve the equations.
I will appreciate if anyone can suggest other ways to solve the equations. Maybe not groebner? any method that works and returns all the 20 solutions.
This is the code in Maple that defines the 5 equations and finds all the solutions:
restart;
eq1:=-18889.48706*qd+467.29186*qb+2982.844413*qd*qc*qb+30136.14351*qc-1115.07186*qc^2*qd-45629.75749*qa*qd*qb-23697.88597*qd^2*qc+4316.66628*qa*qc*qb-15135.14056*qb^2*qc-21851.63993*qa*qd*qc+7902.042467*qb^2*qd-5483.40637*qd^2*qb-11776.45729*qc^2*qb+40621.75090*qa+11348.58548*qd^3-18144.72833*qb^3-19544.23125*qc^3+2*b*qa+32521.65211*qa*qc^2+25623.87525*qa*qd^2+26225.65173*qa*qb^2;
eq2:=-29579.52853*qd+73144.02842*qb+8748.09605*qd*qc*qb+2240.035087*qc+26343.71460*qc^2*qd+2344.316752*qa*qd*qb-25331.91138*qd^2*qc+1444.808993*qa*qc*qb+6290.87549*qb^2*qc+2982.844337*qa*qd*qc+49189.98407*qb^2*qd-29432.25353*qd^2*qb-17559.89085*qc^2*qb-7338.23254*qa+2*b*qb+21944.51817*qd^3-11930.76271*qb^3+2394.88100*qc^3-3970.93290*qa*qc^2+2322.11803*qa*qd^2-23212.08740*qa*qb^2;
eq3:=-3375.795773*qd+2240.03510*qb+7057.67167*qd*qc*qb+56197.14569*qc+52577.03189*qc^2*qd+2982.84431*qa*qd*qb-17977.24342*qd^2*qc-136.341409*qa*qc*qb-23855.89112*qb^2*qc-15689.91200*qa*qd*qc+15299.86799*qb^2*qd-25331.91138*qd^2*qb+11501.30926*qc^2*qb+19564.44679*qa-963.74805*qd^3+658.069730*qb^3-24654.25363*qc^3-16345.90692*qa*qc^2-13126.18932*qa*qd^2-4563.44385*qa*qb^2+2*b*qc;
eq4:=37246.67872*qd-29579.52855*qb-46347.15644*qd*qc*qb-3375.795773*qc-11079.46666*qc^2*qd+12449.76046*qa*qd*qb-24742.88407*qd^2*qc+2982.844222*qa*qc*qb+15299.86800*qb^2*qc-15680.68187*qa*qd*qc-28830.47715*qb^2*qd+20203.79697*qd^2*qb+26343.71462*qc^2*qb-14402.89763*qa-14953.58829*qd^3+31606.58056*qb^3+24809.55728*qc^3-5601.66129*qa*qc^2+16099.39874*qa*qd^2+3415.45305*qa*qb^2+2*b*qd;
eq5:=qa^2+qb^2+qc^2+qd^2-1;
vars:=[b, qa, qb, qc, qd];
polysys:={eq1,eq2,eq3,eq4,eq5};
sols:=CodeTools:-Usage(RootFinding:-Isolate(polysys, vars, output = numeric, method = RS));
These are all the solutions that Maple found (20 solutions):
sols :=
[[b = -6104.435348, qa = -.2144080500, qb = -.2880353207, qc = -.1836576407, qd = -.9150599506],
[b = -12366.14419, qa = -.5402828747, qb = -.3634451559, qc = .1841090309, qd = -.7362784111],
[b = -24212.37926, qa = .2546299302, qb = .6836963191, qc = -.4499174642, qd = -.5150701091],
[b = -23961.92853, qa = .2585879982, qb = .7021280140, qc = -.4278033463, qd = -.5070826324],
[b = -6007.960508, qa = -.3010769760, qb = -.1196072448, qc = .8107192013, qd = -.4876280735],
[b = -22102.25884, qa = .7018528580, qb = -.1525453855, qc = -.5362892523, qd = -.4433128793],
[b = -26791.96626, qa = .3384082623, qb = -.1163579699, qc = -.8287561155, qd = -.4302371112],
[b = -26003.78615, qa = 0.7746836766e-1, qb = -.1265934010, qc = -.9030243373, qd = -.4031374569],
[b = -27290.86178, qa = .3563297191, qb = .8341751821, qc = .4195778650, qd = -0.3369439196e-1],
[b = -39895.97736, qa = -.5758752754, qb = .7983140794, qc = -.1758240948, qd = -0.1217314478e-1],
[b = -39895.97736, qa = .5758752754, qb = -.7983140794, qc = .1758240948, qd = 0.1217314478e-1],
[b = -27290.86178, qa = -.3563297191, qb = -.8341751821, qc = -.4195778650, qd = 0.3369439196e-1],
[b = -26003.78615, qa = -0.7746836766e-1, qb = .1265934010, qc = .9030243373, qd = .4031374569],
[b = -26791.96626, qa = -.3384082623, qb = .1163579699, qc = .8287561155, qd = .4302371112],
[b = -22102.25884, qa = -.7018528580, qb = .1525453855, qc = .5362892523, qd = .4433128793],
[b = -6007.960508, qa = .3010769760, qb = .1196072448, qc = -.8107192013, qd = .4876280735],
[b = -23961.92853, qa = -.2585879982, qb = -.7021280140, qc = .4278033463, qd = .5070826324],
[b = -24212.37926, qa = -.2546299302, qb = -.6836963191, qc = .4499174642, qd = .5150701091],
[b = -12366.14419, qa = .5402828747, qb = .3634451559, qc = -.1841090309, qd = .7362784111],
[b = -6104.435348, qa = .2144080500, qb = .2880353207, qc = .1836576407, qd = .9150599506]]
And this is the code in sagemath that I couldn't solve. Same equations as before, only converted them to rational coefficients using eq_i=P(eq_i). It is stuck in the last line of code (I.variety(RR)).
P.<b, qa, qb, qc, qd>=PolynomialRing(QQ,order='degrevlex')
eq1=-18889.48706*qd+467.29186*qb+2982.844413*qd*qc*qb+30136.14351*qc-1115.07186*qc^2*qd-45629.75749*qa*qd*qb-23697.88597*qd^2*qc+4316.66628*qa*qc*qb-15135.14056*qb^2*qc-21851.63993*qa*qd*qc+7902.042467*qb^2*qd-5483.40637*qd^2*qb-11776.45729*qc^2*qb+40621.75090*qa+11348.58548*qd^3-18144.72833*qb^3-19544.23125*qc^3+2*b*qa+32521.65211*qa*qc^2+25623.87525*qa*qd^2+26225.65173*qa*qb^2
eq2=-29579.52853*qd+73144.02842*qb+8748.09605*qd*qc*qb+2240.035087*qc+26343.71460*qc^2*qd+2344.316752*qa*qd*qb-25331.91138*qd^2*qc+1444.808993*qa*qc*qb+6290.87549*qb^2*qc+2982.844337*qa*qd*qc+49189.98407*qb^2*qd-29432.25353*qd^2*qb-17559.89085*qc^2*qb-7338.23254*qa+2*b*qb+21944.51817*qd^3-11930.76271*qb^3+2394.88100*qc^3-3970.93290*qa*qc^2+2322.11803*qa*qd^2-23212.08740*qa*qb^2
eq3=-3375.795773*qd+2240.03510*qb+7057.67167*qd*qc*qb+56197.14569*qc+52577.03189*qc^2*qd+2982.84431*qa*qd*qb-17977.24342*qd^2*qc-136.341409*qa*qc*qb-23855.89112*qb^2*qc-15689.91200*qa*qd*qc+15299.86799*qb^2*qd-25331.91138*qd^2*qb+11501.30926*qc^2*qb+19564.44679*qa-963.74805*qd^3+658.069730*qb^3-24654.25363*qc^3-16345.90692*qa*qc^2-13126.18932*qa*qd^2-4563.44385*qa*qb^2+2*b*qc
eq4=37246.67872*qd-29579.52855*qb-46347.15644*qd*qc*qb-3375.795773*qc-11079.46666*qc^2*qd+12449.76046*qa*qd*qb-24742.88407*qd^2*qc+2982.844222*qa*qc*qb+15299.86800*qb^2*qc-15680.68187*qa*qd*qc-28830.47715*qb^2*qd+20203.79697*qd^2*qb+26343.71462*qc^2*qb-14402.89763*qa-14953.58829*qd^3+31606.58056*qb^3+24809.55728*qc^3-5601.66129*qa*qc^2+16099.39874*qa*qd^2+3415.45305*qa*qb^2+2*b*qd
eq5=qa^2+qb^2+qc^2+qd^2-1
eq1=P(eq1)
eq2=P(eq2)
eq3=P(eq3)
eq4=P(eq4)
eq5=P(eq5)
I=Ideal(eq1, eq2, eq3, eq4, eq5)
I.groebner_basis('libsingular:std')
I.variety(RR)
Anyone knows how to make it work?
Thanksdavid_cFri, 29 Dec 2017 03:25:53 +0100https://ask.sagemath.org/question/40346/Using Singular's solve.libhttps://ask.sagemath.org/question/40490/using-singulars-solvelib/ I am trying to use Singular's `solve.lib` from Sage, but I am running into issues with getting the result out of Singular. I tried using the Singular interface and was able to make it this far:
sage: singular.lib('solve.lib')
sage: r = singular.ring('complex', '(x,y)', 'lp')
sage: I = singular.ideal('(x-5)*y/32', 'y^2-x^3-5*x-10')
sage: R = singular.fglm_solve(I)
sage: singular.setring(R)
at which point the result is stored in a list `rlist` inside of `R`. I can do `singular.eval('rlist')` and see the answer, but in order to get it back into Sage I would have to parse the resulting string. Is there a better way to get `rlist`?
Alternatively, I tried to use `libSingular` as follows:
sage: from sage.libs.singular.function import singular_function, lib
sage: lib('solve.lib')
sage: fglm_solve = singular_function('fglm_solve')
sage: P = PolynomialRing(QQ,'x,y',order='lex'); x,y = P.gens()
sage: I = Ideal((x-5)*y/32, y^2-x^3-5*x-10)
sage: R = fglm_solve(I)
// 'fglm_solve' created a ring, in which a list rlist of numbers (the
// complex solutions) is stored.
// To access the list of complex solutions, type (if the name R was assigned
// to the return value):
setring R; rlist;
<RingWrap>
But then `R` is a `<RingWrap>` instance and this time I don't even know how to go about seeing the answer. Also, I would prefer to work over the complex field, but I couldn't get `fglm_solve` to accept an ideal in `CC['x,y']`
Any help in either direction would be greatly appreciated.jaebondSat, 06 Jan 2018 04:35:56 +0100https://ask.sagemath.org/question/40490/Getting the error message: The dimension of the ideal is 1, but it should be 0https://ask.sagemath.org/question/40404/getting-the-error-message-the-dimension-of-the-ideal-is-1-but-it-should-be-0/I'm trying to solve a system of 5 polynomial equations.
Here's the code I tried to run:
P.<b, qa, qb, qc, qd>=PolynomialRing(QQ,order='degrevlex')
eq1=P(-25997.02495*qc+73589.75314*qa+19275.89428*qb^3+42024.09724*qc^3-35275.79436*qd^3+31409.96375*qd-22475.53767*qb+11165.49567*qc*qa*qd+38392.81504*qd*qb*qc-5354.736466*qc*qa*qb-40769.13796*qd*qb*qa-50708.36034*qc^2*qa-67780.84581*qd*qb^2+39326.95066*qd^2*qb+5359.28038*qb^2*qa-35437.12402*qd*qc^2+48529.90789*qd^2*qc-6801.32966*qb^2*qc+13747.85604*qc^2*qb+9197.21841*qd^2*qa+2*b*qa)
eq2=-P(1938.516702*qc-9153.752714*qa-15279.24300*qb^3+8131.520743*qc^3+35208.27094*qd^3-25334.07110*qd+71321.57867*qb+38392.81500*qc*qa*qd-48554.44832*qd*qb*qc-64028.43710*qc*qa*qb-58696.44966*qd*qb*qa+2*b*qb+426.071103*qc^2*qa+26980.57949*qd*qb^2-29944.11326*qd^2*qb+4540.542985*qb^2*qa-1130.66934*qd*qc^2-8809.128406*qd^2*qc-9514.136166*qb^2*qc-21010.04302*qc^2*qb+26005.16567*qd^2*qa)
eq3=P(1938.516702*qc-9153.752714*qa-15279.24300*qb^3+8131.520743*qc^3+35208.27094*qd^3-25334.07110*qd+71321.57867*qb+38392.81500*qc*qa*qd-48554.44832*qd*qb*qc-64028.43710*qc*qa*qb-58696.44966*qd*qb*qa+2*b*qb+426.071103*qc^2*qa+26980.57949*qd*qb^2-29944.11326*qd^2*qb+4540.542985*qb^2*qa-1130.66934*qd*qc^2-8809.128406*qd^2*qc-9514.136166*qb^2*qc-21010.04302*qc^2*qb+26005.16567*qd^2*qa)
eq4=P(2123.141846*qc+5788.216407*qa+22583.23914*qb^3-8500.597767*qc^3-9489.15234*qd^3+75013.55778*qd-25334.07110*qb+46634.03800*qc*qa*qd-22972.99327*qd*qb*qc+38392.81504*qc*qa*qb+38688.54642*qd*qb*qa+2*b*qd-9815.37666*qc^2*qa-33782.05127*qd*qb^2+64855.67483*qd^2*qb-42159.09845*qb^2*qa-35072.07256*qd*qc^2-8694.617828*qd^2*qc-29859.97200*qb^2*qc-1130.66933*qc^2*qb-3340.393775*qd^2*qa)
eq5= P(qa^2+qb^2+qc^2+qd^2-1)
I = Ideal(eq1, eq2, eq3, eq4, eq5)
I.groebner_basis('libsingular:std')
I.variety(RR)
At the last line of code:
I.variety(RR)
I get this error:
The dimension of the ideal is 1, but it should be 0
Anyone knows why? or alternatively, how to get the solutions of the equations?
Thanksdavid_cSun, 31 Dec 2017 23:24:09 +0100https://ask.sagemath.org/question/40404/Solving a system of 18 polynomial equations in sagemathhttps://ask.sagemath.org/question/39998/solving-a-system-of-18-polynomial-equations-in-sagemath/I'm trying to solve a system of 18 polynomial equations in sage.
The system is for sure solvable since I already solved it in Maple and got ALL the possible solutions (only real solutions). In most cases I got between 10 to 25 solutions.
But since Maple is not an open source I cannot really use it.
I'm trying to solve the same equations in sage. but so far I did not succeed.
Since it's the first time I write here, I'm not allowed to attach the Maple and Sage code (two files) that I wanted to attach. Instead, I copied them bellow.
It took Maple 25 minutes to solve the equations (in the code bellow). and it found 22 solutions to the equations (I wrote below all the 22 solutions that Maple found).
I used the command 'Isolate' in Maple to solve the equations (this command is used for solving polynomial equations).
Unfortunately I cannot know how the 'Isolate' command is implemented (I can use the command 'showstat' in Maple and see partial implementation of 'Isolate' since some of the commands that are used inside 'Isolate' are compiled).
But I could see that 'Isolate' uses 'Groebner basis' in order to solve the equations.
Therefore I tried to convert the 18 polynomial equations in sage to groebner basis but the command I.groebner_basis() never finishes (in the example below).
Is there maybe another way of getting the groebner basis of the 18 equations? or any other way of solving the problem (I wrote below) so that the solution is for sure correct?
I'm attaching bellow both Maple's code (that succeeded to solve the equations) and Sage's code (that did not succeed).
I'd appreciate any idea of how to solve the equations.
If it helps, here's the mathematical problem that I'm trying to solve:
given a set of n 3D points P={p_1,p_2,...,p_n} and another set of n 3D lines H={h_1,h_2,...,h_n} (each line h_i is represented by a 3D point and a 3D unit vector). I'm trying to find the rotation matrix R=[r1,r2,r3;r4,r5,r6;r7,r8,r9] and a translation vector T=[t1,t2,t3] such that rotating the set P by R and then translating it by T will result in a new set of points PT={pt_1,...,pt_n} such that the sum of square distances between H and PT (sum_{i=1 to n}(dist(h_i,pt_i)^2)) will be minimal. So this is an optimization problem with constraints (the constraints are R*R^T=I). so there are 12 variables in R and T. Using Lagrange Multipliers algorithm I added 6 more variables b1,...,b6 (the number of constraints from R*R^T=I) and created a new function 'h' with 18 variables. the 18 equations are the derivation of 'h' by all the 18 variables (equal to zero). it is gurantee that one of the solutions to the 18 equations is the (global) minimum for R and T. but for that I have to find ALL the solutions to the equations (22 solutions in this example) just like Maple did.
Thanks
Here is Maple code: (and below sage's code)
restart;
g1:=r1^2+r4^2+r7^2-1;
g2:=r1*r2+r4*r5+r7*r8;
g3:=r1*r3+r4*r6+r7*r9;
g4:=r2^2+r5^2+r8^2-1;
g5:=r2*r3+r5*r6+r8*r9;
g6:=r3^2+r6^2+r9^2-1;
sum_sqr_distances:=(-34.5792590705286*r1+17.0635530183776*r4-2.30671047587914*r7+.533429751140582*t1-18.2777571201152+5.34368522421251*r2-2.6369060119417*r5+.356466130795291*r8-.0824332491501039*t2+31.8951297362284*r3-15.7390369840122*r6+2.12765778880161*r9-.492023587996135*t3)^2+(-63.880273658711*r2+31.5224925463221*r5-4.26132023642126*r8+.98543576110074*t2+5.20415366982094+5.34368522429473*r1-2.63690601164137*r4+.356466130730839*r7-.0824332491771907*t1+5.63520538121055*r3-2.78076015494726*r6+.375912834341308*r9-.0869303242748373*t3)^2+(-31.1892504431195*r3+15.3907123123387*r6-2.08057004842228*r9+.481134487803446*t3+16.460313265992+31.8951297380977*r1-15.7390369788429*r4+2.12765778852522*r7-.492023588007365*t1+5.63520538145412*r2-2.78076015435067*r5+.375912834360444*r8-.086930324248257*t2)^2+(-20.1477543311821*r1+7.55350991666248*r4+20.8920429846501*r7+.506802937949341*t1-13.5125935907312+7.82881106057577*r2-2.9350666574299*r5-8.1180192368411*r8-.19692837123503*t2+18.2686582928059*r3-6.84902591482382*r6-18.9435302828672*r9-.459535566231505*t3)^2+(-36.6286508786965*r2+13.7322935856179*r5+37.9817688885839*r8+.921368583909397*t2-34.3325081149272+7.82881105959312*r1-2.93506665641182*r4-8.11801923407865*r7-.196928371252735*t1+7.29448206284227*r3-2.7347436184352*r6-7.56395131161327*r9-.183487691946913*t3)^2+(-22.7328194787774*r3+8.52266582628087*r6+23.5726043680174*r9+.5718284781815*t3+29.2151845257836+18.2686582944502*r1-6.84902591329222*r4-18.9435302865599*r7-.459535566194367*t1+7.2944820644144*r2-2.73474361877224*r5-7.56395131566163*r8-.183487691915587*t2)^2+(-33.7370053449296*r1+38.9258336170637*r4-60.1132663033064*r7+.996042632734926*t1-4.98803179031169+1.08999592941726*r2-1.25763978603382*r5+1.94217639880877*r8-.0321807583045741*t2+1.8259306385537*r3-2.10676292990297*r6+3.25347948355056*r9-.0539083045951421*t3)^2+(-25.0073507347857*r2+28.8535382444551*r5-44.5585943124607*r8+.738310564652533*t2+4.93804814541239+1.08999592907818*r1-1.25763978578301*r4+1.94217639918338*r7-.0321807583046471*t1+14.8482131236429*r3-17.1319021236029*r6+26.4568411007238*r9-.438374809459876*t3)^2+(-8.9977349393474*r3+10.3816070715198*r6-16.0323428536159*r9+.265646802616713*t3-2.58161819993127+1.82593063830369*r1-2.1067629296129*r4+3.25347948341273*r7-.0539083045952243*t1+14.8482131262288*r2-17.1319021246606*r5+26.4568410945*r8-.438374809459549*t2)^2+(-56.6725654800191*r1-43.1813795970078*r4-58.3887310201578*r7+.980525398272198*t1+49.0916863573367+5.78296846451955*r2+4.40630407967054*r5+5.95808902028457*r8-.100054539766321*t2+5.50887455808305*r3+4.19745958942679*r6+5.67569496876523*r9-.0953122798368383*t3)^2+(-28.0870406673401*r2-21.400781038534*r5-28.937575861748*r8+.48595041543225*t2+19.4018945247715+5.78296846409823*r1+4.40630407900952*r4+5.95808902050728*r7-.100054539765808*t1+28.302910438969*r3+21.5652619383799*r6+29.1599826218892*r9-.489685305322089*t3)^2+(-30.836717169852*r3-23.4958833859599*r6-31.7705184032215*r9+.533524186319051*t3-30.3978529558191+5.50887455772671*r1+4.19745958933706*r4+5.67569496903033*r7-.0953122798304703*t1+28.3029104392002*r2+21.5652619411541*r5+29.1599826221612*r8-.489685305291881*t2)^2+(-57.8205382202822*r1-33.3924384768228*r4-34.894277849845*r7+.850839830317679*t1-12.5672620764049+10.7191476042258*r2+6.19050752309509*r5+6.46892827657879*r8-.157734223996209*t2+21.7070640341081*r3+12.5362340547815*r6+13.1000566054682*r9-.319423430626817*t3)^2+(-56.6217108878986*r2-32.7000933511969*r5-34.1707942023208*r8+.833198866184046*t2-1.62153141633832+10.7191476020505*r1+6.19050752434099*r4+6.46892827744991*r7-.15773422401843*t1+22.9548337765416*r3+13.2568443369017*r6+13.8530766468144*r9-.337784591359295*t3)^2+(-21.4717881919623*r3-12.4003578706288*r6-12.9580693345224*r9+.315961303486945*t3+6.66922254237138+21.7070640313443*r1+12.5362340557455*r4+13.1000566039334*r7-.319423430651098*t1+22.9548337782773*r2+13.2568443352531*r5+13.8530766433259*r8-.337784591337385*t2)^2+(-65.9377723150761*r1-12.678533244879*r4-65.0293030974106*r7+.955841723390729*t1+11.5835324790697+7.68982596884022*r2+1.47860188124137*r5+7.5838780437921*r8-.111472624096221*t2+11.9049207597142*r3+2.28908148248606*r6+11.7408986260292*r9-.17257513524552*t3)^2+(-49.571881779333*r2-9.53169524975009*r5-48.8888964859373*r8+.718599844159693*t2+14.0432100287845+7.6898259693682*r1+1.47860188123288*r4+7.58387804187672*r7-.111472624065637*t1+30.0526392395535*r3+5.77852985094098*r6+29.6385837317152*r9-.435646602436962*t3)^2+(-22.4583184276267*r3-4.31829173040524*r6-22.1488950108346*r9+.32555843242268*t3-12.0350031966363+11.904920759546*r1+2.28908148261245*r4+11.7408986234862*r7-.172575135204147*t1+30.0526392370654*r2+5.77852985129325*r5+29.6385837327811*r8-.435646602452044*t2)^2+(-40.2818933934206*r1+37.3415461911863*r4-17.5121421408269*r7+.688992135032061*t1+41.1079956272437+18.3480006638221*r2-17.0087018409058*r5+7.97660607993154*r8-.313829045441664*t2+19.8946971640516*r3-18.4424983689296*r6+8.64901659965967*r9-.340284150555745*t3)^2+(-39.9505168284587*r2+37.0343582140755*r5-17.3680795584234*r8+.68332418286889*t2-19.0229410779165+18.3480006624515*r1-17.0087018386759*r4+7.97660607742464*r7-.313829045473842*t1+20.0751637635565*r3-18.6097919416627*r6+8.72747261243189*r9-.343370898899277*t3)^2+(-36.6974975173012*r3+34.0187906543919*r6-15.9538626068613*r9+.627683682093741*t3-20.0272581058992+19.8946971612448*r1-18.4424983632605*r4+8.64901659883117*r7-.340284150571336*t1+20.0751637622239*r2-18.609791938382*r5+8.72747261433876*r8-.343370898879803*t2)^2+(-19.9003018252227*r1+2.10723968998899*r4-5.99083386660634*r7+.268355364500816*t1-6.36217996635187+32.4452671740533*r2-3.43562400998522*r5+9.76739986562233*r8-.437524092703596*t2+5.19806634264006*r3-.550422390906632*r6+1.56483817002714*r9-.0700958709468267*t3)^2+(-54.7542305404035*r2+5.79791647536792*r5-16.4833428943737*r8+.738360233327084*t2+12.3293109763825+32.4452671726755*r1-3.43562401018043*r4+9.76739986673756*r7-.437524092757061*t1+3.1084479408544*r3-.329153041695288*r6+.935774510511675*r9-.0419173883795401*t3)^2+(-73.6585215390464*r3+7.79968874305612*r6-22.1743353083965*r9+.99328440217389*t3-10.5500615738974+5.19806634229016*r1-.550422390946524*r4+1.5648381697327*r7-.0700958709446797*t1+3.10844794077716*r2-.329153041700441*r5+.935774510228754*r8-.041917388373134*t2)^2;
h:=sum_sqr_distances+g1*b1+g2*b2+g3*b3+g4*b4+g5*b5+g6*b6;
diff_t1:=diff(h,t1);
diff_t2:=diff(h,t2);
diff_t3:=diff(h,t3);
diff_r1:=diff(h,r1);
diff_r2:=diff(h,r2);
diff_r3:=diff(h,r3);
diff_r4:=diff(h,r4);
diff_r5:=diff(h,r5);
diff_r6:=diff(h,r6);
diff_r7:=diff(h,r7);
diff_r8:=diff(h,r8);
diff_r9:=diff(h,r9);
diff_b1:=diff(h,b1);
diff_b2:=diff(h,b2);
diff_b3:=diff(h,b3);
diff_b4:=diff(h,b4);
diff_b5:=diff(h,b5);
diff_b6:=diff(h,b6);
vars := [op(indets(h, And(name, Non(constant))))];
polysys:={diff_t1,diff_t2,diff_t3,diff_r1,diff_r4,diff_r7,diff_r2,diff_r5,diff_r8,diff_r3,diff_r6,diff_r9,diff_b1,diff_b2,diff_b3,diff_b4,diff_b5,diff_b6};
sols := CodeTools:-Usage(RootFinding:-Isolate(polysys, vars, output = numeric, method = RS));
And this is sage code (that couldn't find the groebner basis):
P.<r1,r2,r3,r4,r5,r6,r7,r8,r9,t1,t2,t3,b1,b2,b3,b4,b5,b6>=PolynomialRing(QQ,order='degrevlex')
g1=r1^2+r4^2+r7^2-1
g2=r1*r2+r4*r5+r7*r8
g3=r1*r3+r4*r6+r7*r9
g4=r2^2+r5^2+r8^2-1
g5=r2*r3+r5*r6+r8*r9
g6=r3^2+r6^2+r9^2-1
sum_sqr_distances=(-34.5792590705286*r1+17.0635530183776*r4-2.30671047587914*r7+.533429751140582*t1-18.2777571201152+5.34368522421251*r2-2.6369060119417*r5+.356466130795291*r8-.0824332491501039*t2+31.8951297362284*r3-15.7390369840122*r6+2.12765778880161*r9-.492023587996135*t3)^2+(-63.880273658711*r2+31.5224925463221*r5-4.26132023642126*r8+.98543576110074*t2+5.20415366982094+5.34368522429473*r1-2.63690601164137*r4+.356466130730839*r7-.0824332491771907*t1+5.63520538121055*r3-2.78076015494726*r6+.375912834341308*r9-.0869303242748373*t3)^2+(-31.1892504431195*r3+15.3907123123387*r6-2.08057004842228*r9+.481134487803446*t3+16.460313265992+31.8951297380977*r1-15.7390369788429*r4+2.12765778852522*r7-.492023588007365*t1+5.63520538145412*r2-2.78076015435067*r5+.375912834360444*r8-.086930324248257*t2)^2+(-20.1477543311821*r1+7.55350991666248*r4+20.8920429846501*r7+.506802937949341*t1-13.5125935907312+7.82881106057577*r2-2.9350666574299*r5-8.1180192368411*r8-.19692837123503*t2+18.2686582928059*r3-6.84902591482382*r6-18.9435302828672*r9-.459535566231505*t3)^2+(-36.6286508786965*r2+13.7322935856179*r5+37.9817688885839*r8+.921368583909397*t2-34.3325081149272+7.82881105959312*r1-2.93506665641182*r4-8.11801923407865*r7-.196928371252735*t1+7.29448206284227*r3-2.7347436184352*r6-7.56395131161327*r9-.183487691946913*t3)^2+(-22.7328194787774*r3+8.52266582628087*r6+23.5726043680174*r9+.5718284781815*t3+29.2151845257836+18.2686582944502*r1-6.84902591329222*r4-18.9435302865599*r7-.459535566194367*t1+7.2944820644144*r2-2.73474361877224*r5-7.56395131566163*r8-.183487691915587*t2)^2+(-33.7370053449296*r1+38.9258336170637*r4-60.1132663033064*r7+.996042632734926*t1-4.98803179031169+1.08999592941726*r2-1.25763978603382*r5+1.94217639880877*r8-.0321807583045741*t2+1.8259306385537*r3-2.10676292990297*r6+3.25347948355056*r9-.0539083045951421*t3)^2+(-25.0073507347857*r2+28.8535382444551*r5-44.5585943124607*r8+.738310564652533*t2+4.93804814541239+1.08999592907818*r1-1.25763978578301*r4+1.94217639918338*r7-.0321807583046471*t1+14.8482131236429*r3-17.1319021236029*r6+26.4568411007238*r9-.438374809459876*t3)^2+(-8.9977349393474*r3+10.3816070715198*r6-16.0323428536159*r9+.265646802616713*t3-2.58161819993127+1.82593063830369*r1-2.1067629296129*r4+3.25347948341273*r7-.0539083045952243*t1+14.8482131262288*r2-17.1319021246606*r5+26.4568410945*r8-.438374809459549*t2)^2+(-56.6725654800191*r1-43.1813795970078*r4-58.3887310201578*r7+.980525398272198*t1+49.0916863573367+5.78296846451955*r2+4.40630407967054*r5+5.95808902028457*r8-.100054539766321*t2+5.50887455808305*r3+4.19745958942679*r6+5.67569496876523*r9-.0953122798368383*t3)^2+(-28.0870406673401*r2-21.400781038534*r5-28.937575861748*r8+.48595041543225*t2+19.4018945247715+5.78296846409823*r1+4.40630407900952*r4+5.95808902050728*r7-.100054539765808*t1+28.302910438969*r3+21.5652619383799*r6+29.1599826218892*r9-.489685305322089*t3)^2+(-30.836717169852*r3-23.4958833859599*r6-31.7705184032215*r9+.533524186319051*t3-30.3978529558191+5.50887455772671*r1+4.19745958933706*r4+5.67569496903033*r7-.0953122798304703*t1+28.3029104392002*r2+21.5652619411541*r5+29.1599826221612*r8-.489685305291881*t2)^2+(-57.8205382202822*r1-33.3924384768228*r4-34.894277849845*r7+.850839830317679*t1-12.5672620764049+10.7191476042258*r2+6.19050752309509*r5+6.46892827657879*r8-.157734223996209*t2+21.7070640341081*r3+12.5362340547815*r6+13.1000566054682*r9-.319423430626817*t3)^2+(-56.6217108878986*r2-32.7000933511969*r5-34.1707942023208*r8+.833198866184046*t2-1.62153141633832+10.7191476020505*r1+6.19050752434099*r4+6.46892827744991*r7-.15773422401843*t1+22.9548337765416*r3+13.2568443369017*r6+13.8530766468144*r9-.337784591359295*t3)^2+(-21.4717881919623*r3-12.4003578706288*r6-12.9580693345224*r9+.315961303486945*t3+6.66922254237138+21.7070640313443*r1+12.5362340557455*r4+13.1000566039334*r7-.319423430651098*t1+22.9548337782773*r2+13.2568443352531*r5+13.8530766433259*r8-.337784591337385*t2)^2+(-65.9377723150761*r1-12.678533244879*r4-65.0293030974106*r7+.955841723390729*t1+11.5835324790697+7.68982596884022*r2+1.47860188124137*r5+7.5838780437921*r8-.111472624096221*t2+11.9049207597142*r3+2.28908148248606*r6+11.7408986260292*r9-.17257513524552*t3)^2+(-49.571881779333*r2-9.53169524975009*r5-48.8888964859373*r8+.718599844159693*t2+14.0432100287845+7.6898259693682*r1+1.47860188123288*r4+7.58387804187672*r7-.111472624065637*t1+30.0526392395535*r3+5.77852985094098*r6+29.6385837317152*r9-.435646602436962*t3)^2+(-22.4583184276267*r3-4.31829173040524*r6-22.1488950108346*r9+.32555843242268*t3-12.0350031966363+11.904920759546*r1+2.28908148261245*r4+11.7408986234862*r7-.172575135204147*t1+30.0526392370654*r2+5.77852985129325*r5+29.6385837327811*r8-.435646602452044*t2)^2+(-40.2818933934206*r1+37.3415461911863*r4-17.5121421408269*r7+.688992135032061*t1+41.1079956272437+18.3480006638221*r2-17.0087018409058*r5+7.97660607993154*r8-.313829045441664*t2+19.8946971640516*r3-18.4424983689296*r6+8.64901659965967*r9-.340284150555745*t3)^2+(-39.9505168284587*r2+37.0343582140755*r5-17.3680795584234*r8+.68332418286889*t2-19.0229410779165+18.3480006624515*r1-17.0087018386759*r4+7.97660607742464*r7-.313829045473842*t1+20.0751637635565*r3-18.6097919416627*r6+8.72747261243189*r9-.343370898899277*t3)^2+(-36.6974975173012*r3+34.0187906543919*r6-15.9538626068613*r9+.627683682093741*t3-20.0272581058992+19.8946971612448*r1-18.4424983632605*r4+8.64901659883117*r7-.340284150571336*t1+20.0751637622239*r2-18.609791938382*r5+8.72747261433876*r8-.343370898879803*t2)^2+(-19.9003018252227*r1+2.10723968998899*r4-5.99083386660634*r7+.268355364500816*t1-6.36217996635187+32.4452671740533*r2-3.43562400998522*r5+9.76739986562233*r8-.437524092703596*t2+5.19806634264006*r3-.550422390906632*r6+1.56483817002714*r9-.0700958709468267*t3)^2+(-54.7542305404035*r2+5.79791647536792*r5-16.4833428943737*r8+.738360233327084*t2+12.3293109763825+32.4452671726755*r1-3.43562401018043*r4+9.76739986673756*r7-.437524092757061*t1+3.1084479408544*r3-.329153041695288*r6+.935774510511675*r9-.0419173883795401*t3)^2+(-73.6585215390464*r3+7.79968874305612*r6-22.1743353083965*r9+.99328440217389*t3-10.5500615738974+5.19806634229016*r1-.550422390946524*r4+1.5648381697327*r7-.0700958709446797*t1+3.10844794077716*r2-.329153041700441*r5+.935774510228754*r8-.041917388373134*t2)^2
sum_sqr_distances=P(sum_sqr_distances)
h=sum_sqr_distances+g1*b1+g2*b2+g3*b3+g4*b4+g5*b5+g6*b6
diff_t1=diff(h,t1)
diff_t2=diff(h,t2)
diff_t3=diff(h,t3)
diff_r1=diff(h,r1)
diff_r2=diff(h,r2)
diff_r3=diff(h,r3)
diff_r4=diff(h,r4)
diff_r5=diff(h,r5)
diff_r6=diff(h,r6)
diff_r7=diff(h,r7)
diff_r8=diff(h,r8)
diff_r9=diff(h,r9)
diff_b1=diff(h,b1)
diff_b2=diff(h,b2)
diff_b3=diff(h,b3)
diff_b4=diff(h,b4)
diff_b5=diff(h,b5)
diff_b6=diff(h,b6)
I=Ideal(diff_t1,diff_t2,diff_t3,diff_r1,diff_r2,diff_r3,diff_r4,diff_r5,diff_r6,diff_r7,diff_r8,diff_r9,diff_b1,diff_b2,diff_b3,diff_b4,diff_b5,diff_b6)
I.groebner_basis()
I.variety(RR)
And these are the 22 solutions the Maple found (all the real solutions that solve the equations):
The goal is to get the same solutions from sage.
[[b1 = -6405.651236, b2 = 1097.011411, b3 = 6432.603484, b4 = -3486.767199, b5 = 2786.505511, b6 = -2066.461540, r1 = -.2735272365, r2 = -.4584555697, r3 = -.8455775195, r4 = .9594115168, r5 = -0.6729917007e-1, r6 = -.2738619418, r7 = -0.6864686727e-1, r8 = .8861655107, r9 = -.4582557095, t1 = -31.53181188, t2 = -3.035192389, t3 = -64.33835896],
[b1 = -663.0587184, b2 = 1206.645590, b3 = -935.8274112, b4 = -2827.613858, b5 = 1260.996624, b6 = -676.9562322, r1 = .8750945364, r2 = -.1796187040, r3 = -.4493847723, r4 = -.4474525861, r5 = -.6540696330, r6 = -.6099008922, r7 = -.1843793253, r8 = .7347993170, r9 = -.6527436159, t1 = 24.66279957, t2 = 6.035593829, t3 = -55.14919482],
[b1 = -5334.007938, b2 = -147.4788994, b3 = 6381.507728, b4 = -1654.278431, b5 = 3038.269718, b6 = -2677.888758, r1 = 0.1140465611e-1, r2 = -.8980265159, r3 = -.4397934863, r4 = .8207951804, r5 = .2596099997, r6 = -.5088201253, r7 = -.5711087512, r8 = .3551774554, r9 = -.7400565989, t1 = -38.50311082, t2 = -47.94244185, t3 = -52.00642291],
[b1 = -3711.964527, b2 = 3878.643381, b3 = -871.0350173, b4 = -4720.758037, b5 = 5739.216423, b6 = -3328.445679, r1 = -.3452025304, r2 = -.5900255619, r3 = -.7298664599, r4 = -.5720856277, r5 = .7487785844, r6 = -.3347367116, r7 = .7440115910, r8 = .3019941520, r9 = -.5960254060, t1 = 4.420063381, t2 = -25.83338983, t3 = -49.39760950],
[b1 = -6771.196603, b2 = 3126.930183, b3 = 3836.296676, b4 = -2119.174006, b5 = -1053.266216, b6 = -647.0603393, r1 = -0.5288779601e-1, r2 = .2948075346, r3 = -.9540919235, r4 = .9579998211, r5 = -.2546859938, r6 = -.1318005592, r7 = .2818496477, r8 = .9209905331, r9 = .2689557845, t1 = -1.568329794, t2 = 41.81946440, t3 = -47.91552928],
[b1 = -426.4877331, b2 = 1777.234977, b3 = -1396.594665, b4 = -4704.976941, b5 = 6548.202362, b6 = -2797.527674, r1 = .6772160397, r2 = -.2551001296, r3 = -.6901466217, r4 = -.3808728417, r5 = .6809888166, r6 = -.6254519247, r7 = .6295349982, r8 = .6864241804, r9 = .3640158382, t1 = 51.90734298, t2 = -10.61796786, t3 = -36.65155778],
[b1 = -8345.957097, b2 = -5992.141964, b3 = 9771.580880, b4 = -9281.942970, b5 = 14067.10170, b6 = -7238.069438, r1 = -.4112595863, r2 = -.5902847582, r3 = -.6945714196, r4 = -.9059223617, r5 = .1803855392, r6 = .3831001589, r7 = .1008475446, r8 = -.7867813937, r9 = .6089374444, t1 = -25.97531493, t2 = -66.23689116, t3 = -31.46159720],
[b1 = -5343.147703, b2 = 183.2763579, b3 = 5426.240402, b4 = -11788.39198, b5 = 16609.81042, b6 = -7181.846374, r1 = -.2988639430, r2 = -.6827291572, r3 = -.6667542587, r4 = .7307518828, r5 = -.6130817579, r6 = .3002206588, r7 = -.6137442703, r8 = -.3975068000, r9 = .6821336486, t1 = -51.64655336, t2 = -55.45375783, t3 = -29.08482105],
[b1 = -4075.023103, b2 = 6883.346857, b3 = -1945.068213, b4 = -3311.752332, b5 = 3039.918275, b6 = -921.4062369, r1 = .5825663050, r2 = .8122102291, r3 = 0.3051301418e-1, r4 = -.8079724338, r5 = .5827884450, r6 = -0.8682266235e-1, r7 = 0.8830088656e-1, r8 = -0.2592628327e-1, r9 = -.9957563865, t1 = 23.77615250, t2 = 40.91304243, t3 = -28.03945694],
[b1 = -6187.757714, b2 = 838.7708899, b3 = 6066.514065, b4 = -441.1250637, b5 = -851.5589307, b6 = -1128.553632, r1 = .2065219306, r2 = .9631666887, r3 = -.1722167877, r4 = .8113374284, r5 = -.2669555392, r6 = -.5200637629, r7 = -.5468823178, r8 = -0.3232135326e-1, r9 = -.8365853576, t1 = -21.72396020, t2 = 62.90274148, t3 = -22.56105906],
[b1 = -3971.638517, b2 = 5211.591913, b3 = -2909.389068, b4 = -3415.632999, b5 = 2348.040874, b6 = -1624.438321, r1 = -.6376325216, r2 = -.7577247398, r3 = -.1388451874, r4 = -.6573617358, r5 = .6291742407, r6 = -.4147473004, r7 = .4016221056, r8 = -.1731848536, r9 = -.8992812078, t1 = -24.08083201, t2 = -42.77528618, t3 = -16.88667732],
[b1 = -1107.397052, b2 = -1352.354473, b3 = 559.8732630, b4 = -682.7595891, b5 = 1919.821403, b6 = -459.8284277, r1 = -.5540008534, r2 = .8147846552, r3 = -.1709064659, r4 = .3838720628, r5 = .4321713781, r6 = .8160086638, r7 = .7387322206, r8 = .3864632785, r9 = -.5521963786, t1 = -3.462811975, t2 = 66.31134317, t3 = -11.39008932],
[b1 = -1858.210974, b2 = -1443.942073, b3 = -117.7029385, b4 = -541.5565807, b5 = 635.7869277, b6 = -1292.459322, r1 = -.6056473654, r2 = .7430910328, r3 = -.2846172619, r4 = -.4570833521, r5 = -.6176622647, r6 = -.6399751058, r7 = .6513571049, r8 = .2575054246, r9 = -.7137400635, t1 = -8.170594439, t2 = 73.18220544, t3 = -5.574473809],
[b1 = -2879.955409, b2 = -7247.457464, b3 = 7603.360417, b4 = -10386.60081, b5 = 15680.46439, b6 = -7326.146084, r1 = .8898800024, r2 = -.3777475308, r3 = .2557740885, r4 = -.2159488982, r5 = .1450669474, r6 = .9655680474, r7 = -.4018453119, r8 = -.9144738289, r9 = 0.4751801242e-1, t1 = 25.17284844, t2 = -56.81452504, t3 = 4.483386705],
[b1 = -2594.500775, b2 = -8451.746216, b3 = 8378.142403, b4 = -8445.314669, b5 = 16539.21636, b6 = -7726.257147, r1 = -.8887915121, r2 = .4283658935, r3 = .1629487933, r4 = .2014992422, r5 = 0.4589445400e-1, r6 = .9784128753, r7 = -.4116402597, r8 = -.9024391172, r9 = .1271060041, t1 = -72.41708628, t2 = -1.180372243, t3 = 11.62696253],
[b1 = -3386.721976, b2 = -9232.755155, b3 = 8735.844228, b4 = -8449.692294, b5 = 14675.00399, b6 = -7470.241638, r1 = .7020126763, r2 = -.7115667558, r3 = -0.2917112402e-1, r4 = -.6916841933, r5 = -.6714995329, r6 = -.2658220344, r7 = -.1695617265, r8 = -.2067876432, r9 = .9635806617, t1 = 22.56779868, t2 = -57.27997094, t3 = 12.66120812],
[b1 = -2344.035915, b2 = 3947.708934, b3 = -879.5603548, b4 = -4851.200663, b5 = 7270.443175, b6 = -2742.299953, r1 = .4417879292, r2 = .7119951524, r3 = .5457896376, r4 = -.5754568251, r5 = .6916351055, r6 = -.4364519713, r7 = .6882389614, r8 = .1212591594, r9 = -.7152785110, t1 = 49.50818048, t2 = 50.77308450, t3 = 32.05737927],
[b1 = -4793.592445, b2 = -9508.057512, b3 = 9867.840732, b4 = -7363.405470, b5 = 13671.66420, b6 = -8641.244153, r1 = -.8607833310, r2 = .4979577238, r3 = .1053098401, r4 = -.5071531704, r5 = -.8216734210, r6 = -.2600931582, r7 = -0.4298510042e-1, r8 = -.2772920743, r9 = .9598236227, t1 = -55.37291300, t2 = 22.92886207, t3 = 35.86152727],
[b1 = -1143.596369, b2 = 1527.374908, b3 = 1286.733075, b4 = -1246.223196, b5 = 880.0474364, b6 = -176.7812153, r1 = .5096005566, r2 = -.5301666308, r3 = .6776655638, r4 = -0.1872847237e-1, r5 = .7805852008, r6 = .6247687481, r7 = .8602072524, r8 = .3310741426, r9 = -.3878574417, t1 = 62.72704338, t2 = -19.19220727, t3 = 40.08281887],
[b1 = -6277.680746, b2 = -547.8928701, b3 = 6669.122409, b4 = -11168.08424, b5 = 15793.41027, b6 = -8033.605502, r1 = .4599469977, r2 = .3665077232, r3 = .8087773786, r4 = .5464600340, r5 = -.8347594860, r6 = 0.6751319714e-1, r7 = -.6998786970, r8 = -.4109120215, r9 = .5842269422, t1 = -10.38583601, t2 = 10.41107518, t3 = 61.92902662],
[b1 = -9151.429703, b2 = -6008.117168, b3 = 11049.83952, b4 = -7190.606039, b5 = 13545.27447, b6 = -7223.768017, r1 = 0.7425420274e-1, r2 = .5809660735, r3 = .8105336112, r4 = -.9944330906, r5 = .1040687725, r6 = 0.1650814969e-1, r7 = -0.7476056307e-1, r8 = -.8072472434, r9 = .5854594317, t1 = -4.663325049, t2 = 4.554915592, t3 = 62.58462359],
[b1 = -1226.728760, b2 = 1147.011945, b3 = -400.7753802, b4 = -4507.321778, b5 = 8005.881456, b6 = -3241.483736, r1 = -0.9032875350e-2, r2 = .7488743127, r3 = .6626504893, r4 = -.2759411564, r5 = .6350798638, r6 = -.7214776814, r7 = .9611320853, r8 = .1893695603, r9 = -.2009086466, t1 = 40.46849908, t2 = 60.56033489, t3 = 65.08406719]]david_cThu, 07 Dec 2017 19:00:21 +0100https://ask.sagemath.org/question/39998/Uniqueness of reduced Groebner basis - proofhttps://ask.sagemath.org/question/39792/uniqueness-of-reduced-groebner-basis-proof/ Hi, can you please help me understand something.
I defined minimal GB like this:
Let G = {g1, . . . , gs} be a GB of an ideal I ⊂ k[x1, . . . , xn].
Then G is a **minimal GB** if and only if for each i = 1, . . . , s, the polynomial LC(gi) = 1 and its leading monomial LM(gi) does not divide LM(gj) for any j different than i.
and I showed that if:
G = {g1, . . . , gs} and H = {h1, . . . , ht} are two minimal GB for I then s = t and, after renumbering as necessary, LT(gi) = LT(hi) for i = 1, . . . , s.
Now I have a definition for reduced GB:
Let G = {g1, . . . , gs} be a GB of an ideal I ⊂ k[x1, . . . , xn].
Then G is a **reduced GB** if and only if for each i = 1, . . . , s LC(gi) = 1 and its leading monomial LM(gi) does not divide
any term of any gj for any j different then i.
Now i want to show **uniqueness** of reduced GB and the proof goes like this:
Suppose that {f1, . . . , fs} and {g1, . . . , gs} are both reduced and ordered so that LT(fi) = LT(gi) for each i.
Consider fi − gi ∈ I. If it is not zero, then its leading term must be a term that appeared in fi or in gi . In either case, this
contradicts the bases being reduced, so in fact fi = gi as claimed.
I don't understand why is there a contradiction with the bases being reduced.PetraSat, 25 Nov 2017 21:54:03 +0100https://ask.sagemath.org/question/39792/What is the meaning of the ouptput:Polynomial Sequence with 634 Polynomials in 35 Variableshttps://ask.sagemath.org/question/35887/what-is-the-meaning-of-the-ouptputpolynomial-sequence-with-634-polynomials-in-35-variables/ I am doing calculations of finding Groebner basis of a toric ideal associated with one matrix. At the end I am getting output as **Polynomial Sequence with 634 Polynomials in 35 Variables** . I want a complete output which involves all these polynomials. Is there any command to do this?NileshSat, 03 Dec 2016 11:50:01 +0100https://ask.sagemath.org/question/35887/Compute Groebner Basis of an ideal that includes parametershttps://ask.sagemath.org/question/33051/compute-groebner-basis-of-an-ideal-that-includes-parameters/ I'm trying to compute the Groebner Basis of the ideal $$I=\langle f_1,f_2,f_3,f_4,f_5 \rangle$$ in $\mathbb{R}[x_1,y_1,x_2,y_2,x_3,y_3]$, where
$$ f_1=13(x_1+x_1x_2-y_1y_2+(x_1x_2-y_1 y_2)x_3-(y_1 x_2+y_2x_1)y_3)-x_0 $$
$$ f_2=13(y_1+y_1x_2+y_2x_1+(y_1 x_2+y_2x_1)x_3+(x_1x_2-y_1 y_2)y_3)-y_0$$
$$f_3=x_1^2+y_1^2-1$$
$$f_4=x_2^2+y_2^2-1$$
$$f_5=x_3^2+y_3^2-1.$$
$x_1,y_1,x_2,y_2,x_3,y_3$ are real variables and $x_0,y_0$ are some constants. I'm using lex order with $x_1>y_1>x_2>y_2>x_3>y_3$. What I've tried was
sage: R.<x1,y1,x2,y2,x3,y3> = PolynomialRing(QQ, order='lex')
sage: x0,y0 = var('x0,y0')
sage: f1 = 13*(x1+x1*x2-y1*y2+(x1*x2-y1*y2)*x3-(y1*x2+y2*x1)*y3)-x0
sage: f2 = 13*(y1+y1*x2+y2*x1+(y1*x2+y2*x1)*x3+(x1*x2-y1*y2)*y3)-y0
sage: f3 = x1^2+y1^2-1
sage: f4 = x2^2+y2^2-1
sage: f5 = x3^2+y3^2-1
sage: ideal(f1,f2,f3,f4,f5).groebner_basis()
but the output was
---------------------------------------------------------------------------
AttributeError Traceback (most recent call last)
<ipython-input-8-e03b88a807f0> in <module>()
----> 1 ideal(f1,f2,f3,f4,f5).groebner_basis()
sage/structure/element.pyx in sage.structure.element.Element.__getattr__ (/usr/lib/sagemath//src/build/cythonized/sage/structure/element.c:4675)()
sage/structure/misc.pyx in sage.structure.misc.getattr_from_other_class (/usr/lib/sagemath//src/build/cythonized/sage/structure/misc.c:1771)()
AttributeError: 'Ideal_generic' object has no attribute 'groebner_basis'
What can I do?ilgkSun, 10 Apr 2016 19:53:35 +0200https://ask.sagemath.org/question/33051/converting from direct representation to indirect representation for S-boxeshttps://ask.sagemath.org/question/26039/converting-from-direct-representation-to-indirect-representation-for-s-boxes/Hi guys, let's we want to get the polynomial expression for a S-Box.
sage: S = mq.SBox(7,6,0,4,2,5,1,3)
sage: P = S.ring()
We can get the **indirect** representation...
sage: S.polynomials()
[x0*x2 + x1 + y1 + 1,
x0*x1 + x1 + x2 + y0 + y1 + y2 + 1,
x0*y1 + x0 + x2 + y0 + y2,
x0*y0 + x0*y2 + x1 + x2 + y0 + y1 + y2 + 1,
x1*x2 + x0 + x1 + x2 + y2 + 1,
x0*y0 + x1*y0 + x0 + x2 + y1 + y2,
x0*y0 + x1*y1 + x1 + y1 + 1,
x1*y2 + x1 + x2 + y0 + y1 + y2 + 1,
x0*y0 + x2*y0 + x1 + x2 + y1 + 1,
x2*y1 + x0 + y1 + y2,
x2*y2 + x1 + y1 + 1,
y0*y1 + x0 + x2 + y0 + y1 + y2,
y0*y2 + x1 + x2 + y0 + y1 + 1,
y1*y2 + x2 + y0]
or the **direct** representation
sage: P.<y0,y1,y2,x0,x1,x2> = PolynomialRing(GF(2),6,order='lex')
sage: S.polynomials([x0,x1,x2],[y0,y1,y2], groebner=True)
[y0 + x0*x1 + x0*x2 + x0 + x1*x2 + x1 + 1,
y1 + x0*x2 + x1 + 1,
y2 + x0 + x1*x2 + x1 + x2 + 1]
My question is, given the **direct** representation of the S-Box, can we retrieve the **indirect** representation for the S-Box?freako89Thu, 05 Mar 2015 05:28:36 +0100https://ask.sagemath.org/question/26039/PBGBStrategyhttps://ask.sagemath.org/question/24429/pbgbstrategy/Hi, I am trying to understand how the groebner_basis() works in PolyBoRi. So I tried to understand the code pbori.pyx. I got stuck at this line:
> self._strat = new PBGBStrategy((<BooleanPolynomialRing>param)._pbring)
since I cannot find the detail of PBGBStrategy() (and PBRing_Constructor() as well).
The only place I can find the word "PBGBStrategy" is in decl.pxd. But I think in decl.pxd, the function/class PBGBStrategy() is only declared.
**Does anyone know where can I see the detail (implementation) of the function/class PBGBStrategy()?**
Thank you.theofanuelaWed, 08 Oct 2014 09:14:42 +0200https://ask.sagemath.org/question/24429/Problem computing Grobner basishttps://ask.sagemath.org/question/24317/problem-computing-grobner-basis/ I'm have the following code:
R0.<c4,e2,e3,e4> = QQ[]
F0 = Frac(R0)
R1.<a,b,m1,m2,m3,m4,r1,r2,r3,r4,s1,s2,s3,s4> = PolynomialRing(F0,14,order='degrevlex')
R2.<r,s,v,w> = R1[]
m = a + b*w
Mst = m1*m + m2*r + m3*s + m4
Rst = r1*m + r2*r + r3*s + r4
Sst = s1*m + s2*r + s3*s + s4
P1l = s + c4*v
P1r = m
P2l = m + e2*r + e3*s + e4*v
P2r = r
Q1l = Sst + c4*v
Q1r = Mst
Q2l = Mst + e2*Rst + e3*Sst + e4*v
Q2r = Rst
P = P1l*P1r - P2l*P2r
Q = Q1l*Q1r - Q2l*Q2r
H = P-Q
I = ideal(H.coefficients())
J = I.groebner_basis()
I get back an error from Singular:
SingularError: Singular error:
? unknown option `set`
? unknown option `sage7`
? error occurred in or before STDIN line 11: `option(set,sage7);`
Any idea what is going on? It won't crash with the "lex" ordering, but I'm running the computation in parallel on different cores with different orderings hoping one of them will eventually find something.EdvardFSun, 28 Sep 2014 01:35:09 +0200https://ask.sagemath.org/question/24317/Relations in a polynomial ringhttps://ask.sagemath.org/question/23306/relations-in-a-polynomial-ring/Suppose Sage hands me a multivariable polynomial ring specified by some number of generators, and some relations that I don't know. How can I get a list of relations among the generators? In particular, here is the code I'm using:
rays = [(0,0,1),(1,0,-2),(0,1,-2),(-1,0,-2),(0,-1,-2)]
cones = [(1,2,3,4)]
Delta = Fan(cones,rays)
T = ToricVariety(Delta)
R = T.affine_patch(0).coordinate_ring()
I've tried defining a morphism from R to itself which just sends the generators to themselves, then computing a groebner basis for the ideal of the kernel.
generators = R.gens()
phi = R.hom(generators)
Sage doesn't seem to let me do this, since kernel isn't implemented for morphisms defined this way. At this point I'm not sure what else to try. I feel like there must be a simpler way to extract relations among generators in a ring, but after spending a couple of days scouring the documentation I can't seem to notice anything relevant. Help is much appreciated!
jmracekWed, 09 Jul 2014 15:52:29 +0200https://ask.sagemath.org/question/23306/A problem on Groebner Fans with more than 10 variableshttps://ask.sagemath.org/question/10887/a-problem-on-groebner-fans-with-more-than-10-variables/ sage: X=[var('x%d' % i) for i in range(20)]
> Up to 10 variables, everything is
> alright:
sage: R=PolynomialRing(QQ,"x",10)
sage: R.ideal(x0).groebner_fan()
Groebner fan of the ideal:
Ideal (x0) of Multivariate Polynomial Ring in x0, x1, x2, x3, x4, x5, x6, x7, x8, x9 over Rational Field
> But with at least one more variable,
> there is a problem:
sage: R=PolynomialRing(QQ,"x",11)
sage: R.ideal(x0).groebner_fan()
---------------------------------------------------------------------------
RuntimeError Traceback (most recent call last)
<ipython-input-49-29624ce56396> in <module>()
----> 1 R.ideal(x0).groebner_fan()
/home/sebastien/sage/local/lib/python2.7/site-packages/sage/rings/polynomial/multi_polynomial_ideal.pyc in groebner_fan(self, is_groebner_basis, symmetry, verbose)
3486 import sage.rings.polynomial.groebner_fan as groebner_fan
3487 return groebner_fan.GroebnerFan(self, is_groebner_basis=is_groebner_basis,
-> 3488 symmetry=symmetry, verbose=verbose)
3489
3490 @cached_method
/home/sebastien/sage/local/lib/python2.7/site-packages/sage/rings/polynomial/groebner_fan.pyc in __init__(self, I, is_groebner_basis, symmetry, verbose)
810 raise TypeError, "I must be a multivariate polynomial ideal"
811 if prefix_check([str(R_gen) for R_gen in I.ring().gens()]) != True:
--> 812 raise RuntimeError, "Ring variables cannot contain each other as prefixes"
813 S = I.ring()
814 R = S.base_ring()
RuntimeError: Ring variables cannot contain each other as prefixes
> What's the problem ? How have more than 10 variables ?
Sébastien PalcouxSat, 04 Jan 2014 09:24:24 +0100https://ask.sagemath.org/question/10887/scary muli_polynomial_ring warninghttps://ask.sagemath.org/question/10426/scary-muli_polynomial_ring-warning/Thw following warning message looks pretty scary, since it is accompanied by a stack trace. And I have absolutely no idea (yet) as to what it is trying to tell me. Is the result it prints in the end reliable? If so, why the fuss? And if not, what is causing this problem? Is this an indication of a bug?
sage: R1.<cosAlpha, sinAlpha> = AA[]
sage: QR1 = R1.quotient(R1.ideal(cosAlpha^2 + sinAlpha^2 - 1))
sage: QR1(-8*sinAlpha - 4*sinAlpha*cosAlpha + 5*2*(2*sinAlpha*cosAlpha)*(cosAlpha*cosAlpha - sinAlpha*sinAlpha))
verbose 0 (3490: multi_polynomial_ideal.py, groebner_basis) Warning: falling back to very slow toy implementation.
singular_ring_delete(ring*) called with NULL pointer.
File "<stdin>", line 1, in <module>
File "_sage_input_4.py", line 10, in <module>
exec compile(u'open("___code___.py","w").write("# -*- coding: utf-8 -*-\\n" + _support_.preparse_worksheet_cell(base64.b64decode("UVIxKC04KnNpbkFscGhhIC0gNCpzaW5BbHBoYSpjb3NBbHBoYSArIDUqMiooMipzaW5BbHBoYSpjb3NBbHBoYSkqKGNvc0FscGhhKmNvc0FscGhhIC0gc2luQWxwaGEqc2luQWxwaGEpKQ=="),globals())+"\\n"); execfile(os.path.abspath("___code___.py"))' + '\n', '', 'single')
File "", line 1, in <module>
File "/tmp/tmpKfaoEi/___code___.py", line 3, in <module>
exec compile(u'QR1(-_sage_const_8 *sinAlpha - _sage_const_4 *sinAlpha*cosAlpha + _sage_const_5 *_sage_const_2 *(_sage_const_2 *sinAlpha*cosAlpha)*(cosAlpha*cosAlpha - sinAlpha*sinAlpha))' + '\n', '', 'single')
File "", line 1, in <module>
File "sage/rings/quotient_ring.py", line 993, in _element_constructor_
return self.element_class(self, x)
File "sage/rings/quotient_ring_element.py", line 99, in __init__
self._reduce_()
File "sage/rings/quotient_ring_element.py", line 118, in _reduce_
self.__rep = I.reduce(self.__rep)
File "sage/rings/polynomial/multi_polynomial_ideal.py", line 4019, in reduce
strat = self._groebner_strategy()
File "sage/rings/polynomial/multi_polynomial_ideal.py", line 910, in _groebner_strategy
return GroebnerStrategy(MPolynomialIdeal(self.ring(), self.groebner_basis()))
Exception KeyError: (The ring pointer 0x0,) in 'sage.libs.singular.ring.singular_ring_delete' ignored
-40*cosAlphabar*sinAlphabar^3 + 16*cosAlphabar*sinAlphabar - 8*sinAlphabarMvGWed, 07 Aug 2013 10:06:35 +0200https://ask.sagemath.org/question/10426/Solving system of polynomial equation over finite fieldhttps://ask.sagemath.org/question/10270/solving-system-of-polynomial-equation-over-finite-field/Hello,
I am working in multivariate polynomial rings over small finite fields (with less then 15, or currently less than 10 elements). I have an algorithm, that outputs a system of equations. I need to find out if the system has a solution and if so, to find one. I am using calculation of groebner basis for this. But since my system typically has 20 or more variables and quite complicated polynomials, it seems that SINGULAR has problem to find the basis in reasonable time. Is there a way to speed up the calculation? For example, since I work in finite field, I can try all possible values for some variable. This simplifies the system and in some cases it seems to really help SINGULAR. But I can do that for only a very few variables.
Currently I work in PolynomialRing and before the grobner basis algorithm, I reduce my polynomials by FieldIdeal (x_0^n - x_0, ..., x_m^n - x_m) of the polynomial ring and add this equations to the system, to force the solution in the finite field.
I tried to work in the quotient ring from the start, but it looks like it slowed down my whole algorithm and also slowed down the computation of the groebner basis (which is a little suprising for me).
I found that for GF(2) PolyBoRi is optimized for the kind of work I need, but I am not restricted to GF(2). Is there something similar for other finite fields?
I would appreciate any tips how to speed up the whole process. Thank you.blishkoSun, 23 Jun 2013 11:16:01 +0200https://ask.sagemath.org/question/10270/Groebner basishttps://ask.sagemath.org/question/10265/groebner-basis/hello
I'm trying to compute groebner basis for I=( x^2+y+z-1,x+y^2+z-1,x+y+z^2-1) in sage, but why the groebner basis of this ideal is same as ideal?
thank youRoxanaThu, 20 Jun 2013 15:03:04 +0200https://ask.sagemath.org/question/10265/reduced groebner basishttps://ask.sagemath.org/question/10264/reduced-groebner-basis/hello,
how can I compute reduced groebner basis with out using buchberger algorithm in sage?RoxanaThu, 20 Jun 2013 15:00:13 +0200https://ask.sagemath.org/question/10264/Checking the progress of a calculationhttps://ask.sagemath.org/question/9839/checking-the-progress-of-a-calculation/Hi - I pretty much know the answer to this question will be "no", but there are so many smarter-than-me people out there that maybe just maybe one of you will have an idea. (This is not dissimilar from the following thread: http://ask.sagemath.org/question/62/can-i-pause-a-computation-rather-than-aborting-it; however that was somewhat inconclusive ...)
I am running a large Groebner basis calc (ideal gen'd by 35 quadratic and quartic polys in a polynomial ring in 50 variables: over a small finite field, but still ...) and it has now been running for 3 days with no output. I was wondering whether there was ANY way to "peer inside the machine" and learn some sort of approximate level of progress, essentially to know whether I should leave the thing running, or give up!!
Any ideas would be great (although please phrase them in IT-idiot terminology for me) - thanks a lot.GaryMakSat, 23 Feb 2013 17:25:28 +0100https://ask.sagemath.org/question/9839/System of polynomial inequalitieshttps://ask.sagemath.org/question/9596/system-of-polynomial-inequalities/I heard that something called a Groebner Basis can be used to find the solutions of a system of polynomial equations like $p_1(x_1,\ldots,x_m)=0,\ldots,p_n(x_1,\ldots,x_m)=0$
Is there something analgous that can find solutions when inequalities are also involved such as
$$p_1(x_1,\ldots,x_m)=0,\ldots,p_n(x_1,\ldots,x_m)=0$$
$$q_1(x_1,\ldots,x_m)>0,\ldots,q_r(x_1,\ldots,x_m)>0$$
and is there a way to do this in Sage?kevinfatSat, 01 Dec 2012 21:56:21 +0100https://ask.sagemath.org/question/9596/Groebner Basis for Submodules of a Free Modulehttps://ask.sagemath.org/question/8841/groebner-basis-for-submodules-of-a-free-module/I am interested in computing the Groebner basis for submodules of a free module. Is there a way to make this work in SAGE?eldenelmantoSun, 01 Apr 2012 16:56:02 +0200https://ask.sagemath.org/question/8841/SAGBI-Grobner basis of an invariant polynomial systemhttps://ask.sagemath.org/question/8774/sagbi-grobner-basis-of-an-invariant-polynomial-system/Hi all!
I've been looking into the SAGBI-Grobner basis and I gave it a test drive. My very simple multivariate system is invariant and I want to find its SAGBI basis via the Singular library. I'm pretty sure the code below produces *wrong* result for some reason (I'm by no means saying there is a bug in the Singular lib).
The last polynomial is in fact *invariant* to the same G as the original system, the rest of the polynomials are identical to the original ones. A paper on the topic by Nicolas M. Thiery: [Computing Minimal Generating Sets of Invariant Rings of Permutation Groups with SAGBI-Grobner Basis](http://www.dmtcs.org/pdfpapers/dmAA0123.pdf) states that the remainder of dividing any polynomial with any other in the SAGBI basis should be 0, but I'm sure this is not the case here, or am I missing something? Sorry in advance for vagueness - I don't understand the topic 100%. It should be simple however to compute SAGBI basis of this system by hand or see just by looking at the result, that something might be wrong here. I suspect there is something wrong with the original set of polynomials... A link to the [worksheet](http://www.sagenb.org/home/pub/4457/), if it helps!
Thank you in advance,
Sash
R1.<S0,S1,S2,S3> = QQ[]
P1.<X0,X1, Y0,Y1> = Frac(R1)[]
I1 = P * [
X0 + Y0 - S0,
X0 * X1 + Y0 * Y1 - S1,
X0* ( X1^2 )+ Y0 *( Y1^2 ) - 2* S2]
PI = singular(I1)
singular.LIB("sagbi.lib")
PI.sagbi()
------------------------------------------------
X0+Y0+(-S0),
X0*X1+Y0*Y1+(-S1),
X0*X1^2+Y0*Y1^2+(-2*S2),
X0*X1^2*Y0-2*X0*X1*Y0*Y1+X0*Y0*Y1^2+(-S0)*X0*X1^2+(-S0)*Y0*Y1^2+(2*S1)*X0*X1+(2*S1)*Y0*Y1+(-2*S2)*X0+(-2*S2)*Y0+(2*S0*S2-S1^2)musevicTue, 06 Mar 2012 12:34:42 +0100https://ask.sagemath.org/question/8774/Show the polynomials in the Groebner Basis as they are foundhttps://ask.sagemath.org/question/8759/show-the-polynomials-in-the-groebner-basis-as-they-are-found/This is more a question about singular, since that is what Sage uses to computer the Groebner Basis. In Singular, you can use option(prot) and then, upon using the groebner function of your choice, you will see verbose output. From the [Singular manual](http://www.singular.uni-kl.de/Manual/latest/sing_330.htm#SEC370), we are told that when "s" is printed in the verbose output, a new element of the standard basis has been found. It is sometimes enough, and in particular very useful for my needs, to know that a certain polynomial is in the groebner basis.
I am working with an overdetermined system of polynomials for which the full groebner basis is too difficult to compute, however it would be valuable for me to be able to print out the groebner basis elements as they are found so that I may know if a particular polynomial is in the groebner basis. Is there any way to do this?
----------
My question is above, but more details specifically related to my problem are below, which may be useful in providing an alternate answer.
The problem is as follows: I have a system of (not necessarily homogeneous) multivariate polynomials $f_1(x_1,\dots,x_n)=0,\dots f_m(x_1,\dots,x_n)=0$. I would like to prove that a few of the $x_i$ must be equal to zero. I was able to uncomment lines 240, 241, and 242 in [this toy implementation library of Faugere's f5 algorithm for Singular](http://www.math.usm.edu/perry/Research/f5_library.lib) and remove the "lead" function around the to-be-printed output on line 241. After just a couple of seconds while running this command, $x_7^5$ was printed out as a member of the basis.
This would seem to imply that $x_7$ must equal zero. The toy library is useful in this regard, since it was able to be modified to print out the members of the basis as they were discovered, however it is still a toy implementation and is not as efficient as slimgb, for instance. My question is, how can I get this same behavior from slimgb?process91Wed, 29 Feb 2012 16:08:42 +0100https://ask.sagemath.org/question/8759/weight ordershttps://ask.sagemath.org/question/8694/weight-orders/I found that installed Sage on my VM Ubuntu can't create weighted TermOrders.
Using 'Force = True' results in a ring with just lex order.
Reinstalling doesn't help.
Copying from http://sagemath.org/doc/reference/sage/rings/polynomial/term_order.html?highlight=termorder#sage.rings.polynomial.term_order.TermOrder
results in Error massage:
"verbose 0 (388: term_order.py, __init__) Term ordering 'wdegrevlex' unknown"
how can i fix that problem?MbochkFri, 03 Feb 2012 08:34:31 +0100https://ask.sagemath.org/question/8694/Analogue of PointsOverSplittingField in SAGEhttps://ask.sagemath.org/question/8690/analogue-of-pointsoversplittingfield-in-sage/Does anyone know if SAGE has an analogue of MAGMA's function PointsOverSplittingField, or something that does Groebner basis computations/polynomial system solutions over an algebraically closed field.
I am trying to verify the results that MAGMA gives me, so please don't point me to SAGE's interface to MAGMA.arsenelkinThu, 02 Feb 2012 13:10:38 +0100https://ask.sagemath.org/question/8690/Faugère's F4 Algorithmhttps://ask.sagemath.org/question/8638/faugeres-f4-algorithm/There are many places online which mention that Faugère's F4 (and even F5) algorithms are included (or were going to be included) in Sage, but the only result in the documentation I can find is here:
http://www.sagemath.org/doc/reference/sage/rings/polynomial/pbori.html?highlight=faugere#sage.rings.polynomial.pbori.GroebnerStrategy.faugere_step_dense
Does anyone know if it is currently included in Sage?process91Tue, 17 Jan 2012 22:40:56 +0100https://ask.sagemath.org/question/8638/memory leak when doing lots of ideal testshttps://ask.sagemath.org/question/8573/memory-leak-when-doing-lots-of-ideal-tests/I'm trying to find elliptic curves lying on a quartic surface; there are probably clever ways to do this, but at the moment I am finding lots of quadrics through an integer point on the surface, then iterating over pairs of them and checking
`x^4+y^4+z^4-67*t^4 in ideal(f1,f2)`
This leaks about 2MB memory per second, presumably because the Groebner bases for the ideals are being cached; is there a way to tell sage not to cache them?fivemackTue, 17 Jan 2012 06:59:06 +0100https://ask.sagemath.org/question/8573/Basis of invariant polynomial systemhttps://ask.sagemath.org/question/8509/basis-of-invariant-polynomial-system/I've been trying to compute a Grobner basis for a specific invariant polynomial system. It has 6 variables, 6 constants and 6 equations and is invariant to a group of cardinality 2. Various algorithms have been ran on it, including FGb/Gb through Maple and Singular through SAGE system. In both cases, the invariance was ignored and the computation of the Grobner basis failed to finish after hours (sometime days) of computation, while occupying all the memory available. Please note, I do not know what exactly the underlying algorithm was (Buchberger/F4/F5...).
It is an engineering application and in practice, I would only need the first few polynomials of the Grobner basis, that is the ones with as low degree as possible. I'm an engineer not a mathematician, so my knowledge of the topic is very limited. I did however understood, that in case of invariant systems, a SAGBI basis (or invariant Grobner basis) can be computed much more efficiently. More important, the invariant Grobner basis can be computed "up to a given degree", which is exactly what I probably need.
I got a hint that such algorithm might exist in SAGE. I've been searching through the SAGE documentation, but it seems I don't know what to search for and the system is huge.
If anyone can point me to right direction it would be great!
The problem:
X0 + Y0 - S0 = 0
X0 X1 + Y0 Y1 - S1 = 0
X0 ( X1^2 + 2 X2 )+ Y0 ( Y1^2 + 2 Y2 )- 2 S2 = 0
X0 ( X1^3 + 6 X2 X1 )+ Y0 ( Y1^3 + 6 Y2 Y1 ) - 6 S3 = 0
X0 ( X1^4 + 12 X2 X1^2 + 12 X2^2 )+ Y0 ( Y1^4 + 12 Y2 Y1^2 + 12 Y2^2 )- 24 S4 = 0
X0 ( X1^5 + 20 X2 X1^3 + 60 X2^2 X1 ) + Y0 ( Y1^5 + 20 Y2 Y1^3 + 60 Y2^2 Y1 ) - 120 S5 = 0
Where X0,X1,X2,Y0,Y1,Y2 are variables S0...S5 are constants, all are complex numbers.musevicThu, 24 Nov 2011 13:20:32 +0100https://ask.sagemath.org/question/8509/