factoring lists in Singular
c.r...@espero.org.uk
I have turned to Singular to calculate the intersections of
polynomials that Maple 11 has had problems with. (My solution sets
are infinite, and Maple's polynomial arithmetic apparently is
particular poor in such cases.) After defining the ring, polynomials
and ideal, I use facstd. I would like to factorise my results further
than at present.
For example, the appended code produces the following output:
[1]:
_[1]=v
_[2]=b3-b2v+3bv2-2bv-v3
[2]:
_[1]=9v-4
_[2]=b-2v
[3]:
_[1]=v-1
_[2]=b-v
Thus, [1,2] simplifies to "=b" and [3,2] to "=b-1". How can I ask
Singular to perform these simplifications?
Thank you,
Colin Rowat, Department of Economics, University of Birmingham
APPENDED CODE
LIB "primdec.lib";
ring r=0,(b,s,v),lp;
poly v11h= b^3 + v^3 - 2*b*v;
poly v21h= v^3 - 3*b*v^2 + b^2*v + 2*b*v -b^3;
ideal i1121h = v11h,v21h;
list fi1121h = facstd(i1121h);
fi1121h;
clicl...@freenet.de
Can't help you with the Singular syntax, indeed I'm not exactly sure
what you want done. This is my guess, on Derive 1.61:
[v11h := b^3+v^3-2*b*v, v21h := v^3-3*b*v^2+b^2*v+2*b*v-b^3]
SOLVE([v11h = v21h], [b, v])
[b = 0, 2*b^2-b*v+v*(3*v-4) = 0]
" let's reduce the 2nd equation further: "
SOLVE([2*b^2-b*v+v*(3*v-4)=0], [b])
[b = -(SQRT(-v)+SQRT(23*v-32))*SQRT(-v)/4, b = (SQRT(23*v-32)-SQRT(-
v))*SQRT(-v)/4]
" ... and with some manual massaging ... "
[b = (v-SQRT(v*(32-23*v)))/4, b = (SQRT(v*(32-23*v))+v)/4]
Now you have three solutions. Any system that knows about Groebner
bases should be able to do that. What's the problem with Maple?
Martin.
c.r...@espero.org.uk
> Now you have three solutions. Any system that knows about Groebner
> bases should be able to do that. What's the problem with Maple?
Thank you Martin. With the example posted, Maple can get me the
result that I want. My problem arises for more complicated examples,
when I run into memory allocation difficulties. I do not have first
hand knowledge of this, but am told that Maple's polynomial arithmetic
is poor, and particularly so for systems with infinite solutions - as
here.
Thus, I turned to Singular as a possibly more efficient package for
harder problems.
In the simple example that I first posted, including
option(redSB)
before the facstd() call performs the simplifications that I wanted.
I am now trying this on more complicated examples.
Best,
Colin Rowat
clicl...@freenet.de
c.ro...@espero.org.uk wrote:
The space and time requirements of Groebner basis calculations grow
exponentially with the problem degree. With non-optimized
implementations on small/slow machines, problems may begin to show up
for degrees as low as five, while degrees around ten are already
record-hunter territory. Compare
<http://groups.google.com/group/sci.math.symbolic/browse_thread/
thread/11d3054c63e76aff/2712dda9fbcc5966?hl=en>
by "mabshoff" in a recent thread, and
<http://magma.maths.usyd.edu.au/users/allan/gb/>.
Martin.
Robert H. Lewis
> > Now you have three solutions. Any system that knows
> about Groebner
> > bases should be able to do that. What's the problem
> with Maple?
>
> Thank you Martin. With the example posted, Maple can
> get me the
> result that I want. My problem arises for more
> complicated examples,
> when I run into memory allocation difficulties. I do
> not have first
> hand knowledge of this, but am told that Maple's
> polynomial arithmetic
> is poor, and particularly so for systems with
> infinite solutions - as
I am also not exactly sure what you want done. Can you post a "more complicated example"? It may be that resultant techniques give the best answer. (They usually are best for solving systems of polynomial equations.)
Robert H. Lewis
Fordham University
http://home.bway.net/lewis/
c.r...@espero.org.uk
> I am also not exactly sure what you want done. Can you post a "more
> complicated example"? It may be that resultant techniques give the
> best answer. (They usually are best for solving systems of polynomial
> equations.)
Thank you Robert. Appended is the "more complicated example" that I
have just tried running. While it solves in just under two hours with
Maple 11 (running on an IBM x3655 with 8GB RAM), it Killed out of
Singular on my linux laptop (Pentium M at 1.5GHz and 512MB RAM).
Thus, the example involves polynomials of the order mentioned as
"record-hunter" by Martin.
Is it reasonable to expect solutions to such systems? If so, to what
extent will I need to tailor my solution finding strategy to the ideal
at hand?
Best,
Colin
LIB "primdec.lib";
ring r=0,(b,s,v),lp;
poly v22l = (2*s-1)^2 * ((5*s^2-2*s-1)*b^2 - (8*s^2-5*s-1)*b - 1)*v^5
+ (2*s-1) * ((4*s-1)*(s-1)^2 * b^3 - 2*(7*s^3-6*s^2+1)*b^2 + (32*s^3 -
36*s^2 + 9*s + 2)*b + 2*(s-1))*v^4 + ((1-2*s)*(s-1)*(11*s^2-10*s
+2)*b^3 + (9*s^4 - 12*s^3 - s^2 + 4*s - 1)*b^2 + (5*s - 48*s^4 -
41*s^2 + 81*s^3 + 1)*b - (1-s)^2)*v^3 + ((1 + 21*s^4 - 10*s + 34*s^2 -
45*s^3)*b^3 + 2*s*(s-1)*(s^2-s+1)*b^2 + s*(s-1)*(16*s^2-13*s+1)*b)*v^2
+ (2*s*(1-s)*(2*s-1)^2 * b^3 - s^2 * (1-s)^2 * b^2 - 2*s^2 * (1-s)^2 *
b)*v + b^3 * s^2 * (1-s)^2;
poly v21l = 3*(s-1)*(2*s-1)^3 * b * v^6 - (2*s-1)^2 * ((s^2 - 4*s +
1)*b^2 + (23*s^2 - 29*s + 8)*b + 1)*v^5 + (2*s-1)*((s-1)*(7*s^2 - 5*s
+ 1)*b^3 + 2*(5*s^3 - 12*s^2 + 6*s - 1)*b^2 + (59*s^3 - 96*s^2 + 51*s
- 7)*b + 2*(s-1))*v^4 + ((1-s)*(31*s^3 - 34*s^2 + 14*s - 2)*b^3 +
(-37*s^2 + 48*s^3 + 10*s - 21*s^4 - 1)*b^2 + (29*s + 141*s^3 - 2 -
69*s^4 - 101*s^2)*b - (1-s)^2)*v^3 + ((6*s^2 - 6*s +1)*(2*s-1)^2 * b^2
+ 2*s*(s-1)*(2*s-1)^2 * b + s*(s-1)*(19*s^2 - 19*s + 4))*b*v^2 + (1-
s)*(2*s*(2*s-1)^2 * b^2 - s^2 * (1-s)*b - 2*s^2 * (1-s))*b*v + s^2 *
b^3 * (1-s)^2;
option(redSB);
timer = 0;
ideal i2122l = v21l,v22l;
list fi2122l = facstd(i2122l);
fi2122l;
timer;
Robert H. Lewis
I eliminated s from these two equations, yielding one equation in b and v. If this is not what you want, let me know.
It takes 0.17 seconds and around 350K of RAM. The resultant has these four factors:
3*v^6*b - 9*v^5*b + 9*v^4*b - 3*v^3*b
2*v - 1
v^2*b^5 - v^3*b^4 - 4*v^2*b^4 + 2*v*b^4 + 3*v^4*b^3 + 2*v^3*b^3 + 2*v^2*b^3 - 4*v*b^3 + b^3 - v^5*b^2 - 12*v^4*b^2 + 10*v^3*b^2 - v*b^2 + 4*v^5*b + 10*v^4*b - 20*v^3*b + 11*v^2*b - 2*v*b - 4*v^5 + 4*v^4 - v^3
b^3 + 2*v^3*b^2 - 4*v^2*b^2 - v*b^2 - 2*v^3*b + 7*v^2*b - 2*v*b - v^3
I did not check that each of these is irreducible.
clicl...@freenet.de
The first and third factor reduce to 3·b·v^3·(v - 1)^3 and (b^3 -
b^2·v + 3·b·v^2 - 2·b·v - v^3)·(b·v - 2·v + 1)^2, respectively. The
timing is really impressive.
Martin.
c.r...@espero.org.uk
> Robert H. Lewis wrote:
> > I eliminated s from these two equations, yielding one equation in b and v. If this is not what you want, let me know.
>
> > It takes 0.17 seconds and around 350K of RAM. The resultant has these four factors:
>
> > 3*v^6*b - 9*v^5*b + 9*v^4*b - 3*v^3*b
>
> > 2*v - 1
>
> > v^2*b^5 - v^3*b^4 - 4*v^2*b^4 + 2*v*b^4 + 3*v^4*b^3 + 2*v^3*b^3 + 2*v^2*b^3 - 4*v*b^3 + b^3 - v^5*b^2 - 12*v^4*b^2 + 10*v^3*b^2 - v*b^2 + 4*v^5*b + 10*v^4*b - 20*v^3*b + 11*v^2*b - 2*v*b - 4*v^5 + 4*v^4 - v^3
>
> > b^3 + 2*v^3*b^2 - 4*v^2*b^2 - v*b^2 - 2*v^3*b + 7*v^2*b - 2*v*b - v^3
>
> > I did not check that each of these is irreducible.
>
> The first and third factor reduce to 3·b·v^3·(v - 1)^3 and (b^3 -
> b^2·v + 3·b·v^2 - 2·b·v - v^3)·(b·v - 2·v + 1)^2, respectively. The
> timing is really impressive.
Dear Robert and Martin,
Thank you for this. That speed does seem amazing (my Singular code
has hit 16 hours and is still running), and gives me new hope about
the results that are obtainable.
Robert - did you use Fermat or Singular to obtain the above? If the
latter, that's just the resultant() command?
Finally, a basic interpretational question, as my algebra is strained
here: if I am interested in all intersections of the two polynomials,
v21l and v22l, the resultant above gives me all combinations of b and
v in the affine variety <v21l,v22l>? I then need to see what further
restrictions are imposed by s?
Thank you again,
Colin
Martin Rubey
> Thank you for this. That speed does seem amazing (my Singular code has hit
> 16 hours and is still running), and gives me new hope about the results that
> are obtainable.
>
> Robert - did you use Fermat or Singular to obtain the above? If the latter,
> that's just the resultant() command?
Here is the invocation in FriCAS (or Axiom or OpenAxiom if you prefer):
(1) -> v22l := (2*s-1)^2 * ((5*s^2-2*s-1)*b^2 - (8*s^2-5*s-1)*b - 1)*v^5+ (2*s-1) * ((4*s-1)*(s-1)^2 * b^3 - 2*(7*s^3-6*s^2+1)*b^2 + (32*s^3 -36*s^2 + 9*s + 2)*b + 2*(s-1))*v^4 + ((1-2*s)*(s-1)*(11*s^2-10*s+2)*b^3 + (9*s^4 - 12*s^3 - s^2 + 4*s - 1)*b^2 + (5*s - 48*s^4 -41*s^2 + 81*s^3 + 1)*b - (1-s)^2)*v^3 + ((1 + 21*s^4 - 10*s + 34*s^2 -45*s^3)*b^3 + 2*s*(s-1)*(s^2-s+1)*b^2 + s*(s-1)*(16*s^2-13*s+1)*b)*v^2+ (2*s*(1-s)*(2*s-1)^2 * b^3 - s^2 * (1-s)^2 * b^2 - 2*s^2 * (1-s)^2 *b)*v + b^3 * s^2 * (1-s)^2;
Type: Polynomial Integer
Time: 0.02 (IN) + 0.01 (EV) + 0.03 (OT) = 0.06 sec
(2) -> v21l := 3*(s-1)*(2*s-1)^3 * b * v^6 - (2*s-1)^2 * ((s^2 - 4*s +1)*b^2 + (23*s^2 - 29*s + 8)*b + 1)*v^5 + (2*s-1)*((s-1)*(7*s^2 - 5*s+ 1)*b^3 + 2*(5*s^3 - 12*s^2 + 6*s - 1)*b^2 + (59*s^3 - 96*s^2 + 51*s- 7)*b + 2*(s-1))*v^4 + ((1-s)*(31*s^3 - 34*s^2 + 14*s - 2)*b^3 +(-37*s^2 + 48*s^3 + 10*s - 21*s^4 - 1)*b^2 + (29*s + 141*s^3 - 2 -69*s^4 - 101*s^2)*b - (1-s)^2)*v^3 + ((6*s^2 - 6*s +1)*(2*s-1)^2 * b^2+ 2*s*(s-1)*(2*s-1)^2 * b + s*(s-1)*(19*s^2 - 19*s + 4))*b*v^2 + (1-s)*(2*s*(2*s-1)^2 * b^2 - s^2 * (1-s)*b - 2*s^2 * (1-s))*b*v + s^2 *b^3 * (1-s)^2;
Type: Polynomial Integer
Time: 0.02 (IN) + 0.01 (EV) + 0.04 (OT) = 0.06 sec
(3) -> factors factor(resultant(v22l, v21l, s))
(3)
[[factor= 81,exponent= 1], [factor= b,exponent= 8],
[factor= v - 1,exponent= 8], [factor= v,exponent= 13],
[factor= 2v - 1,exponent= 1], [factor= (b - 2)v + 1,exponent= 7],
3 2 2 3
[factor= v - 3b v + (b + 2b)v - b ,exponent= 2],
2 3 2 2 2 3
[factor= (2b - 2b - 1)v + (- 4b + 7b)v + (- b - 2b)v + b ,exponent= 1]]
Type: List Record(factor: Polynomial Integer,exponent: Integer)
Time: 0.11 (EV) + 0.004 (OT) = 0.12 sec
So I guess that speed should not be an issue :-)
> Finally, a basic interpretational question, as my algebra is strained here:
> if I am interested in all intersections of the two polynomials, v21l and
> v22l, the resultant above gives me all combinations of b and v in the affine
> variety <v21l,v22l>?
> I then need to see what further restrictions are imposed by s?
I do not know about affine varieties, but the resultant vanishes if and only if
v22l and v21l have a common root as polynomials in s. Hm, I'm afraid I do not
understand your question, sorry. Maybe you could expand?
Martin
clicl...@freenet.de
c.ro...@espero.org.uk wrote:
>
> Finally, a basic interpretational question, as my algebra is strained
> here: if I am interested in all intersections of the two polynomials,
> v21l and v22l, the resultant above gives me all combinations of b and
> v in the affine variety <v21l,v22l>? I then need to see what further
> restrictions are imposed by s?
>
If what you want are the solutions to the single equation v22l = v21l
and not those to the pair of simultaneous equations [v22l = 0, v21l =
0], then your problem happens to be easy. Turning once more to Derive
6.10:
v22l:=(2*s-1)^2*((5*s^2-2*s-1)*b^2-
(8*s^2-5*s-1)*b-1)*v^5+(2*s-1)*((4*s-1)*(s~
-1)^2*b^3-2*(7*s^3-6*s^2+1)*b^2+(32*s^3-36*s^2+9*s+2)*b+2*(s-1))*v^4+
((1-2*s)~
*(s-1)*(11*s^2-10*s+2)*b^3+(9*s^4-12*s^3-
s^2+4*s-1)*b^2+(5*s-48*s^4-41*s^2+81~
*s^3+1)*b-(1-s)^2)*v^3+((1+21*s^4-10*s
+34*s^2-45*s^3)*b^3+2*s*(s-1)*(s^2-s+1)~
*b^2+s*(s-1)*(16*s^2-13*s+1)*b)*v^2+(2*s*(1-s)*(2*s-1)^2*b^3-s^2*(1-
s)^2*b^2-~
2*s^2*(1-s)^2*b)*v+b^3*s^2*(1-s)^2
v21l:=3*(s-1)*(2*s-1)^3*b*v^6-(2*s-1)^2*((s^2-4*s+1)*b^2+(23*s^2-29*s
+8)*b+1)~
*v^5+(2*s-1)*((s-1)*(7*s^2-5*s
+1)*b^3+2*(5*s^3-12*s^2+6*s-1)*b^2+(59*s^3-96*s~
^2+51*s-7)*b+2*(s-1))*v^4+((1-s)*(31*s^3-34*s^2+14*s-2)*b^3+
(-37*s^2+48*s^3+1~
0*s-21*s^4-1)*b^2+(29*s+141*s^3-2-69*s^4-101*s^2)*b-(1-s)^2)*v^3+
((6*s^2-6*s+~
1)*(2*s-1)^2*b^2+2*s*(s-1)*(2*s-1)^2*b+s*(s-1)*(19*s^2-19*s
+4))*b*v^2+(1-s)*(~
2*s*(2*s-1)^2*b^2-s^2*(1-s)*b-2*s^2*(1-s))*b*v+s^2*b^3*(1-s)^2
" v22l = v21l is equivalent to v22l - v21l = 0, so let's try: "
FACTOR(v22l-v21l,Rational)
3*b*v^2*(1-v)*(s-1)*(b*s+s*(1-2*v)+v-1)^2*(s*(2*v-1)-v)
" from which the solutions can be read off "
" you may also let the system do this; there are three ways: "
SOLVE([v22l=v21l],b)
[v=0, b=0, b=(s*(2*v-1)-v+1)/s]
SOLVE([v22l=v21l],s)
[s=1, s=v/(2*v-1), s=(1-v)/(b-2*v+1)]
SOLVE([v22l=v21l],v)
[b=0, v=0, v=1, v=s/(2*s-1), v=(b*s+s-1)/(2*s-1)]
-
Martin (the other one).
c.r...@espero.org.uk
> Here is the invocation in FriCAS (or Axiom or OpenAxiom if you prefer): ...
> (3) -> factors factor(resultant(v22l, v21l, s))
>
> (3)
> [[factor= 81,exponent= 1], [factor= b,exponent= 8],
> [factor= v - 1,exponent= 8], [factor= v,exponent= 13],
> [factor= 2v - 1,exponent= 1], [factor= (b - 2)v + 1,exponent= 7],
> 3 2 2 3
> [factor= v - 3b v + (b + 2b)v - b ,exponent= 2],
> 2 3 2 2 2 3
> [factor= (2b - 2b - 1)v + (- 4b + 7b)v + (- b - 2b)v + b ,exponent= 1]]
> Type: List Record(factor: Polynomial Integer,exponent: Integer)
> Time: 0.11 (EV) + 0.004 (OT) = 0.12 sec
Thank you Martin. The corresponding command in Singular seems to be
factorize(resultant(v21l,v22l,s));
which replicates your FriCAS/Axiom/OpenAxiom results. The [2] return
(multiplicities?) in Singular corresponds to the FriCAS/etc. exponent.
> I do not know about affine varieties, but the resultant vanishes if and only if
> v22l and v21l have a common root as polynomials in s. Hm, I'm afraid I do not
> understand your question, sorry. Maybe you could expand?
If I understand correctly: if the resultant can be made to vanish,
then we conclude that the intersection of v22l and v21l is non-empty
- an existence result. What I then want to do is to characterise that
intersection.
For my simple example (q.v. my initial post), the
factorize(resultant()) command in Singular yields:
-2 [multiplicity 1]
b [multiplicity 7]
b-1 [multiplicity 1]
9b-8 [multiplicity 1]
All except the first of these therefore correspond to a partial
solution - thus the first step in an elimination and extension
strategy? If so, is there a generally optimal way of automating the
whole procedure (ideally in Singular) or must one tailor this to each
pair of polynomials? Any references of which I should be aware would
be appreciated (I've been using Cox, Little and O'Shea).
Thank you again,
Colin Rowat
Martin Rubey
> For my simple example (q.v. my initial post), the
> factorize(resultant()) command in Singular yields:
>
> -2 [multiplicity 1]
> b [multiplicity 7]
> b-1 [multiplicity 1]
> 9b-8 [multiplicity 1]
>
> All except the first of these therefore correspond to a partial
> solution - thus the first step in an elimination and extension
> strategy?
Yes. You can now run through these solutions and solve for b. Then substitute
in the original equations and solve for v. You will in fact need to compute
the gcd of the two polynomials after the substitution: there might be a value
of v that makes one vanish, but not the other. The example above illustrates
that:
(60) -> factors factor resultant(v11h, v21h, b)
(60)
[[factor= 2,exponent= 1], [factor= v - 1,exponent= 1],
[factor= v,exponent= 7], [factor= 9v - 4,exponent= 1]]
Type: List Record(factor: Polynomial Integer,exponent: Integer)
(61) -> factor eval(v11h, v=1)
2
(61) (b - 1)(b + b - 1)
Type: Factored Polynomial Integer
(62) -> factor eval(v21h, v=1)
2
(62) - (b - 1)(b + 1)
Type: Factored Polynomial Integer
(63) -> gcd(eval(v21h, v=1), eval(v11h, v=1))
(63) b - 1
Type: Polynomial Integer
Thus, v=1, b=1 is a common solution, but v=1, b==(sqrt(5)-1)/2 is not.
> If so, is there a generally optimal way of automating the whole procedure
> (ideally in Singular) or must one tailor this to each pair of polynomials?
I doubt it. Note that in many cases you will not even be able to explicitly
compute the zeros of the resultant...
Martin
Robert H. Lewis
> > Robert H. Lewis wrote:
>
> > > I eliminated s from these two equations, yielding
> one equation in b and v. If this is not what you
> want, let me know.
> >
> > > It takes 0.17 seconds and around 350K of RAM.
> The resultant has these four factors:
> >.... snip ....
> >
> > The first and third factor reduce to 3·b·v^3·(v -
> 1)^3 and (b^3 -
> > b^2·v + 3·b·v^2 - 2·b·v - v^3)·(b·v - 2·v + 1)^2,
> respectively. The
> > timing is really impressive.
>
> Dear Robert and Martin,
>
> Thank you for this. That speed does seem amazing (my
> Singular code
> has hit 16 hours and is still running), and gives me
> new hope about
> the results that are obtainable.
>
> Robert - did you use Fermat or Singular to obtain the
> above? If the
> latter, that's just the resultant() command?....
I used Fermat. There is no "resultant" command. I have a set of functions written in Fermat's language to implement the Dixon resultant. The crux is the computation of the determinant of a matrix with multivariate polynomial entries.
I assumed that you had given two equations in the three variables b, v, s. Then Dixon can eliminate one of the vars. I eliminated s but it would be as easy to eliminate any other.
With only two equations, this is a very easy problem. (Sylvester or Macaulay would probably work fine too.) The two equations could be much more complicated and the method would still work. Maybe you have an example with four or five equations?
I see Martin (and Martin?) have answered your other questions. I'm always looking for interesting sets of polynomial equations to try Dixon on.
Regards,
Waldek Hebisch
>
> c.ro...@espero.org.uk wrote:
> >
> > Finally, a basic interpretational question, as my algebra is strained
> > here: if I am interested in all intersections of the two polynomials,
> > v21l and v22l, the resultant above gives me all combinations of b and
> > v in the affine variety <v21l,v22l>? I then need to see what further
> > restrictions are imposed by s?
> >
>
> If what you want are the solutions to the single equation v22l = v21l
> and not those to the pair of simultaneous equations [v22l = 0, v21l =
> 0], then your problem happens to be easy. Turning once more to Derive
> 6.10:
> " v22l = v21l is equivalent to v22l - v21l = 0, so let's try: "
>
> FACTOR(v22l-v21l,Rational)
> 3*b*v^2*(1-v)*(s-1)*(b*s+s*(1-2*v)+v-1)^2*(s*(2*v-1)-v)
Actially, this observation allows easy solution to the original
system. Namely, system [v22l = 0, v21l = 0] has the same solutions
as [v21l = 0, v22l - v21l = 0]. Since v22l - v21l factors we
need just to solve all systems of form [v21l = 0, fi = 0] where
fi is factor of v22l - v21l. Using FriCAS it takes almost no
time (0.08s) to compute Groebner bases of ideals genrated by
the pairs [v21l, fi].
(23) -> factors(v21l - v22l)
(23)
[[factor= 3,exponent= 1], [factor= b,exponent= 1],
[factor= s - 1,exponent= 1], [factor= v - 1,exponent= 1],
[factor= v,exponent= 2], [factor= (2s - 1)v + (- b - 1)s + 1,exponent= 2],
[factor= (2s - 1)v - s,exponent= 1]]
Type: List Record(factor: Polynomial Integer,exponent: Integer)
Time: 0 sec
(24) -> lfd := [v.factor for v in factors(v21l - v22l)]
(24) [3,b,s - 1,v - 1,v,(2s - 1)v + (- b - 1)s + 1,(2s - 1)v - s]
Type: List Polynomial Integer
Time: 0 sec
(25) -> [groebner([v21l, lfd.i]) for i in 2..#lfd]
(25)
2 5 2 4 2 3
[[(4s - 4s + 1)v + (- 4s + 6s - 2)v + (s - 2s + 1)v ,b],
2 5 2 4 2 3 3 2
[(2b - 2b - 1)v + (- 4b + 7b)v + (- b - 2b)v + b v ,s - 1],
2 4 2 3 3 2 2
[v - 1,(2b - 2b)s + (- 4b + 4b)s + (b - b + b - 1)s ],
3 4 3 3 3 2
[v,b s - 2b s + b s ],
[
4 3 2 3 4 3 2 2
(b - 4b + 4b )v + (- b + 6b - 8b )v
+
5 4 3 2 7 6 5 4 6
(- 2b + 10b - 18b + 13b )v + (- 864b + 288b + 480b + 96b )s
+
7 6 5 4 3 5
(552b + 1800b - 968b - 1192b - 192b )s
+
7 6 5 4 3 2 4
(- 170b - 962b - 1134b + 1226b + 944b + 96b )s
+
7 6 5 4 3 2 3
(b + 329b + 287b + 315b - 700b - 232b )s
+
6 5 4 3 2 2
(- 6b - 140b + 100b - 108b + 154b )s
+
6 5 4 3 2 5 4 3 2
(- 2b + 13b - 29b + 27b - 9b )s + 2b - 10b + 16b - 9b
,
5 4 3 2 2 4 3 2
(b - 5b + 8b - 4b )v + (2b - 6b + 4b )v
+
7 6 5 4 6
(- 144b + 48b + 80b + 16b )s
+
7 6 5 4 3 5
(32b + 320b - 128b - 192b - 32b )s
+
7 6 5 4 3 2 4
(- 12b - 28b - 244b + 124b + 144b + 16b )s
+
7 6 5 4 3 2 3
(- 4b + 36b - 52b + 108b - 56b - 32b )s
+
7 6 5 4 3 2 2
(- b + 11b - 39b + 61b - 44b + 12b )s
+
6 5 4 3 2 5 4 3
(2b - 10b + 18b - 14b + 4b )s - b + 3b - 2b
,
(2s - 1)v + (- b - 1)s + 1,
6 5 4 3 2 7 6 5 4 6
(b - 6b + 13b - 12b + 4b )v + (- 288b + 96b + 160b + 32b )s
+
7 6 5 4 3 5
(208b + 592b - 336b - 400b - 64b )s
+
7 6 5 4 3 2 4
(- 56b - 376b - 360b + 440b + 320b + 32b )s
+
7 6 5 4 3 2 3
(4b + 100b + 140b + 92b - 256b - 80b )s
+
7 6 5 4 3 2 2
(2b - 14b - 26b + 14b - 32b + 56b )s
+
7 6 5 4 3 2 6 5 4 3 2
(b - 7b + 19b - 25b + 16b - 4b )s - b + 6b - 13b + 12b - 4b
,
7 6 5 4 7 7 6 5 4 3 6
(9b - 3b - 5b - b )s + (- 11b - 17b + 13b + 13b + 2b )s
+
7 6 5 4 3 2 5
(5b + 21b + 6b - 20b - 11b - b )s
+
7 6 5 4 3 2 4
(- b - 9b - 10b + 4b + 13b + 3b )s
+
6 5 4 3 2 3 5 4 3 2 2
(2b + 3b + b - 3b - 3b )s + (- b + b - b + b )s
]
,
[(2s - 1)v - s,
3 2 3 5 3 2 4 3 2 3
(b - 6b + 12b - 8)v + 16b s + (8b - 48b )s + (4b - 24b + 48b)s
+
3 2 2 3 2
(2b - 12b + 24b - 16)s + (b - 6b + 12b - 8)s
,
3 6 2 5 4 3
b s - 3b s + 3b s - s ]
]
Type: List List Polynomial Integer
Time: 0.02 (EV) + 0.01 (OT) + 0.05 (GC) = 0.08 sec
I belive that other systems can do the same.
--
Waldek Hebisch
heb...@math.uni.wroc.pl
c.r...@espero.org.uk
with my slow reply.
Martin ("the other one"), in response to your remark (10 May):
> If what you want are the solutions to the single equation v22l = v21l
> and not those to the pair of simultaneous equations [v22l = 0, v21l =
> 0]
I am looking for the simultaneous solutions.
Martin (Rubey; 10 May, 9:49pm) I agree: the intersections will
generally be of too high order to explicitly compute their zeros.
Robert:
- you are right: although my simple example (7 May, 8:40pm) is
specified in terms of (b,s,v), it is degenerate, only involving (b,v).
- all of my problems involve two equations. (Do Groebner bases only
come into their own for larger systems?) If you might consider any of
them "interesting sets of polynomial equations", I would be very happy
to forward them to you.
- I shall look at your "Solving Large Polynomial Systems with the
Dixon Resultant" to learn more about Dixon resultants.
Walter: why is it easier to generate Groebner bases of the ideals
generated by <v21l, fi> than it is to work with <v21l, v11l>? (I am
trying to install FriCAS now, but have had a dpkg problem in the move
to Hearty Heron. As I don't know Axiom, and am only beginning to
learn Singular, I would appreciate any references comparing these
packages at a more detailed level than at
http://en.wikipedia.org/wiki/Comparison_of_computer_algebra_systems.)
Finally, two general questions:
(1) in my simple example (7 May, 8:40pm), the factorize(resultant())
command yields four solutions with a multiplicity of 1,7,1 and 1,
respectively (10 May, 9:31pm). Summing these yields 10, which is one
more than what I would have expected, by Bezout's Theorem, from the
intersection of two third order polynomials.
(2) I am continuing to develop my code in Singular. In my complicated
example (8 May, 11:40pm),
factorize(resultant(v21l,v22l,v));
returns
_[1]=243
_[2]=b-1
_[3]=b
_[4]=b2+2bs2-4bs+1
_[5]=9b2s3-11b2s2+5b2s-b2+6bs3-10bs2+4bs+s3-3s2+3s-1
_[6]=2s-1
_[7]=bs-1
_[8]=s-1
_[9]=s
The most interesting of these are _[4] and _[5]. They can be
rewritten in terms of b(s), allowing - I think - use of the Singular
version of Martin Rubey's (10 May, 9:49pm) GCD suggestion:
gcd(subst(v21l,s, expression for b(s) here ),subst(v22l,s, expression
for b(s) here ));
Even more complicated examples, though, may yield higher order terms,
preventing explicit expressions. Can I still use the subst()
command? If not, are there workarounds?
Thank you all again for your detailed help.
Best,
Colin Rowat
clicl...@freenet.de
c.ro...@espero.org.uk schrieb:
>
> Finally, two general questions:
>
> (1) in my simple example (7 May, 8:40pm), the factorize(resultant())
> command yields four solutions with a multiplicity of 1,7,1 and 1,
> respectively (10 May, 9:31pm). Summing these yields 10, which is one
> more than what I would have expected, by Bezout's Theorem, from the
> intersection of two third order polynomials.
There are only three distinct solutions to your simple example
[v11h=0, v21h=0]:
[v11h := b^3+v^3-2*b*v, v21h := v^3-3*b*v^2+b^2*v+2*b*v-b^3]
GROEBNER_BASIS([v11h,v21h],[b,v])
[9*v^6-13*v^5+4*v^4, 10*b*v^2+63*v^5-73*v^4, 10*b^2*v+189*v^5-~
219*v^4+20*v^3, b^3-2*b*v+v^3]
" the 1st term has only three distinct solutions "
FACTOR(9*v^6-13*v^5+4*v^4,Rational)
v^4*(v-1)*(9*v-4)
" accordingly: "
SOLVE([v11h=0,v21h=0],[b,v])
[b=0 AND v=0, b=1 AND v=1, b=8/9 AND v=4/9]
What is your fourth solution?
Martin (the other one).
c.r...@espero.org.uk
> ... There are only three distinct solutions to your simple example
> [v11h=0, v21h=0]: ...
> [b=0 AND v=0, b=1 AND v=1, b=8/9 AND v=4/9]
>
> What is your fourth solution?
Sorry Martin: that was careless of me. You're absolutely right. I
had included the "-2", without realising the obvious, namely that it
does not have implications for b or v.
How is a 'solution' of this sort to be interpreted? If it implies "-2
= 0" then it is clearly inadmissible.
Best,
Colin
c.r...@espero.org.uk
> How is a 'solution' of this sort to be interpreted? If it implies "-2
> = 0" then it is clearly inadmissible.
Apologies - another careless remark by me: "-2" is just a
multiplicative factor.
Using my more "complicated example" suggests, though, that one can't
simply add the (non-constant) multiplicities and compare the result to
the product of the degrees (a la Bezout). In that case, the
multiplicities (excluding the constant) come to 3 + 15 + 1 + 2 + 6 + 7
+ 9 + 13 = 56, which is not equal to 11 x 11.
Is there any relationship between Bezout's Theorem and the
multiplicities of the resultants at this stage, or must one perform
the whole elimination/extension procedure first?
Thank you again,
Colin
Waldek Hebisch
>
> Walter: why is it easier to generate Groebner bases of the ideals
> generated by <v21l, fi> than it is to work with <v21l, v11l>?
After factoring we have polynomials of low degree, which are easy to
handle.
> (I am
> trying to install FriCAS now, but have had a dpkg problem in the move
> to Hearty Heron. As I don't know Axiom, and am only beginning to
> learn Singular, I would appreciate any references comparing these
> packages at a more detailed level than at
> http://en.wikipedia.org/wiki/Comparison_of_computer_algebra_systems.)
>
I am not aware of a text explicitely comparing FriCAS and Singular.
I can offer you may biased opinion (I work on FriCAS, while all
know about Singular comes from reading about it): FriCAS is a
general purpose system while Singular is oriented towards
algebraic geometry.
FriCAS has pretty wide coverage -- look at introductory chapter
in Axiom book (you can find .pdf for online reading at
http://fricas.sourceforge.net/doc/book.pdf) for a sample of possibilities.
When solving polynomial equations FriCAS offers classical resultants,
Groeber bases and triangular systems. Another possibility is to
use power (or Laurent or Puiseux) series to get approximate solutions.
Singular is pretty good at computing Groeber bases, and more
general operating on multivariate polynomials. It probably has
more functions to compute some specific properties of ideals.
However, a it is hard to give a simple and accurate statement.
For example, I found on the net a few examples of polynomials
that take quite a lot of time to factor using Singular --
I have tried them in FriCAS and pretty quickly obtained the
anwer. This is _not_ to claim that FriCAS is faster, rather,
to disprove claim "Singular has very fast polynomial
multiplication, so it must be faster at factoring polynomials"
> Even more complicated examples, though, may yield higher order terms,
> preventing explicit expressions. Can I still use the subst()
> command? If not, are there workarounds?
>
It really depends on your data: sometimes solutions of polynomial
systems have "nice" parametrization. However, you may have
singularities or you may have parametrization which is regular
from analytic point of view, but does not admit simple
formula. Technics like resultunts, Groebner bases or
triangular system can be used to decompose solution set into
irreducible pieces, find dimension, qualitatively analyse singularites
etc.
--
Waldek Hebisch
heb...@math.uni.wroc.pl
William stein
> Singular is pretty good at computing Groeber bases, and more
> general operating on multivariate polynomials.
Overall Singular is probably the best free open source math software
system for computing Groebner basis over fields. It is slow in
some cases, of course. Cocoalib is also rumored to be pretty
good, but I haven't benchmarked it. Singular has unusually good
support for a wide range of term orders. If you have a *lot* of RAM,
Magma is much much faster than Singular currently at many Groebner
basis computations (Allan Steel spent about five years
implementing and heavily tuning a variant of Faugere's F4 in Magma).
> It probably has
> more functions to compute some specific properties of ideals.
It has *tons* of such functions, motivated by a wide range of
research applications of algebraic geometry.
> However, a it is hard to give a simple and accurate statement.
> For example, I found on the net a few examples of polynomials
> that take quite a lot of time to factor using Singular --
You might be referring to all the threads about this on sage-devel?
> I have tried them in FriCAS and pretty quickly obtained the
> anwer. This is _not_ to claim that FriCAS is faster, rather,
> to disprove claim "Singular has very fast polynomial
> multiplication, so it must be faster at factoring polynomials"
Multivariate polynomial factorization in Singular is very
sketchy. In fact, as far as I can tell, general multivariate
factorization is comparably bad still in all open source math
software. I say "bad", because Magma blows everything
else away speedwise at polynomial factorization. See these
trac tickets for some discussion of major efficiency issues
with Singular as compared to Magma:
"singular factorize is randomly slow"
http://trac.sagemath.org/sage_trac/ticket/1343
"multivariate polynomial factorization over GF(p) (sucks)"
http://trac.sagemath.org/sage_trac/ticket/2152
I've been told some of the Singular group is actively
working on improving their polynomial factorization; I hope
they succeed. There is also at least one Sage developer
(Joel Mohler) working on polynomial factorization for Sage.
I don't know what the latest status of this is.
-- William