Code covered by the BSD License

### Highlights from groebner

4.6
4.6 | 6 ratings Rate this file 11 Downloads (last 30 days) File Size: 9.93 KB File ID: #24478 Version: 1.5

# groebner

### Ben Petschel (view profile)

19 Jun 2009 (Updated )

manipulate and solve systems of multivariate polynomial equations by computing the groebner basis

File Information
Description

Example: simplify the system of equations
{x^2+2xy^2=0, xy+2y^3=1}

>> groebner({'x^2+2*x*y^2','x*y+2*y^3-1'},'lex',{'x','y'})

returns {'y^3-0.5','x'}

Solve equations:

>> polynsolve({'x^2+2*x*y^2','x*y+2*y^3-1'},'',{'x','y'})

returns [0, -0.3969 + 0.6874i; 0, -0.3969 - 0.6874i; 0, 0.7937]

>> polynsolve({'x^2-x','x*y-1'},'',{'x','y'})

returns [1, 1]

>> polynsolve({'x^2-x','x*y'},'',{'x','y'})

returns [0, NaN; 1, 0]

(infinite possibilities represented by NaN)

NOTE: calculation of Groebner bases in floating-point arithmetic can be numerically unstable. See the help text for more details.

MATLAB release MATLAB 7.8 (R2009a)
07 Sep 2015 Dionysios Sotiropoulos

### Dionysios Sotiropoulos (view profile)

This is an excellent work.
I need to solve various systems of third-degree multivariate polynomial equations. Could you please specify the differences of this package with the builtin MatLab function
groebner::gbasis() since they do not provide the same results.

05 Mar 2014 QuanShan

### QuanShan (view profile)

excellent work! thanks.I've found this kind of thing for a longtime.wish I can understand it.

16 Jan 2012 Rongfu Tang

### Rongfu Tang (view profile)

excellent work! thanks.

03 Nov 2010 Ben Petschel

### Ben Petschel (view profile)

Christophe, you're welcome to try. I'm not enthusiastic about continuing to work on it when more appropriate tools are readily available and more pressing matters are at hand.

If you must, try adding "deg=double(deg);" to line 391 of groebner.m. However then the functions str2poly and poly2str currently don't parse fractions directly so you could try something like the following example:

eqns={'x^2+2*x*y^2','x*y+2*y^3-1'};vars={'x','y'};ord='lex';
eqnfr = cellfun(@(x)fr(vpi(x)),str2poly(eqns,vars),'unif',false);
gbfr = groebner(eqnfr,ord,vars);
gbs = poly2str(cellfun(@double,gbfr,'unif',false))
% returns gbs = {'x2^3-0.5','x1'}

For this to work you'll need both the Fractions and VPI toolboxes and to have fixed line 391 of groebner.m. It should work with other integer-coefficient polynomials (i.e. multiply the fractions by a big integer) but no guarantees.

Good luck with it!

Comment only
02 Nov 2010 Christophe Lauwerys

### Christophe Lauwerys (view profile)

Thanks for the quick fix Ben.

Regarding floating point accuracy, could a solution be to work with rational coefficients using your fractions toolbox?

Christophe

Comment only
02 Nov 2010 Ben Petschel

### Ben Petschel (view profile)

Christophe, thanks for pointing that out. It's one of several bugs that were introduced with the change in data structures in the last update. I've submitted a new version but there still remains the problem with floating-point accuracy for which I don't know a simple solution.

Comment only
02 Nov 2010 Christophe Lauwerys

### Christophe Lauwerys (view profile)

Could you have a look at another feature/bug:

P = str2poly({'x1*x2*x3'});

P{1}

ans =

1 1 1 1

poly2str(P)
??? Index exceeds matrix dimensions.

Error in ==> poly2str at 68
str = [str,varnames{k}]; % print variable name

Thanks

Christophe

Comment only
10 Oct 2010 Ben Petschel

### Ben Petschel (view profile)

Hi Christophe, thanks for that example, it highlights several issues with the current implementation. Firstly, lex tends to produce longer bases than grlex and the code's reduction algorithms are not particularly efficient. Secondly, groebner base computation is tricky in floating point and while the code does allow a tolerance parameter its checking mechanism is far from perfect. So you'll find that the example does eventually return but with the wrong answer, even with tol set to non-zero. I plan to include more documentation on the limitations in the next update and strongly recommend comparing the results with other programs.

Regarding the use of syms, if you can get it to work that's good, though it's not clear to me how assumptions could be treated robustly even for simple examples like {'a*x'} assuming a<1.

Comment only
08 Oct 2010 Christophe Lauwerys

### Christophe Lauwerys (view profile)

Dear Ben, seems a little trick, overloading the LE operator for the SYM class, makes your code available for syms quite straightforwardly after all, at least a previous version of your code which did not use SORTROWS yet.

An unrelated remark:

how come

groebner({'t^3+x+y','t^2+0.5*x^2-x-z^2','t^2+y-z^2'},'grlex',{'t','x','y','z'})'

returns

't^3+x+y'
'x^2-2*x-2*y'
'-t^2-y+z^2'

in less then a second, while

groebner({'t^3+x+y','t^2+0.5*x^2-x-z^2','t^2+y-z^2'},'lex',{'t','x','y','z'})'

does not return at all ?

Comment only
07 Oct 2010 Ben Petschel

### Ben Petschel (view profile)

Hi Christophe, thanks for pointing that out, looks like the case with non-numeric coefficients is more complicated than I first thought. I don't know of a simple way to handle the symbolic assumptions BUT if you have the symbolic toolbox it's worth looking at the groebner package that comes with MuPAD (see http://www.mathworks.com/help/toolbox/symbolic/mupad.html).

Regards,
Ben

Comment only
07 Oct 2010 Christophe Lauwerys

### Christophe Lauwerys (view profile)

The first problem I encounter trying to use symbolic expressions is on line 305 in groebner.m

if all(abs(P(:))<=tol)

where P is a symbolic array.

??? Undefined function or method 'le'
for input arguments of type 'sym'.

Not sure how to get around this if possible at all.

Symbolic variables can be anything or can be defined under certain assumptions (see http://www.mathworks.com/help/toolbox/symbolic/brs6v40.html#brtck2n)

I guess the LE operator for symbolic variables should check these assumptions in order to come up with an answer.

Comment only
21 Jul 2010 Ben Petschel

### Ben Petschel (view profile)

Thanks John, both are good suggestions. Until I can provide an update, a workaround for complex coefficients is to input the coefficients directly, e.g. your example (1+3*j)*x^2*y+(2+4*j)*x*y has coefficient array [1+3*j,2,1; 2+4*j,1,1]. Let me know if there are any problems.

Comment only
21 Jul 2010 John

### John (view profile)

like (1+3*j)*x^2*y+(2+4*j)*x*y+.....

21 Jul 2010 John

### John (view profile)

It will be a very useful one!
It will be much better if you modify the algorithm for handling 'brackets' in str2poly.m.
That is also my desire for finding roots of polynomials with complex number coefficients.
Would you modify the algorithm for handling those kind of polynomials?

29 Mar 2010 Ben Petschel

### Ben Petschel (view profile)

There's no reason the polynomial coefficients can't be symbolic variables, or any objects for which basic arithmetic is defined. Just create the coefficient arrays directly instead of inputting the polynomials as strings. I don't have the symbolic toolbox so let me know how it goes.

Also I've submitted an updated version that uses a more efficient array representation.

Comment only
29 Mar 2010 Christophe Lauwerys

### Christophe Lauwerys (view profile)

Would it be very difficult to include the possibility of calculating the Groebner basis for a system of parameterized mutivariable polynomials? Singular (http://www.singular.uni-kl.de/) is able to do this, so I assume the algorithms are well know.

22 Jun 2009 1.1

tweaked reduction algorithm; added grlex and revlex options for monomial ordering

22 Jun 2009 1.2

added polynsolve.m for explicitly solving the equations; removed ord='revlex' as it is not a well-ordering.

16 Jul 2009 1.3

fixed bug in handling polynomials with >=3 variables; allowed spaces in polynomial strings

29 Mar 2010 1.4

changed polynomial representation from N-d array to rectangular array for more efficient memory usage when there are many variables

02 Nov 2010 1.5

fixed a few bugs that were introduced with the last update