Back to Forum | View unanswered posts | View active topics
Topic review - Computing efficiently the dot product of homogeneous polys |
Author |
Message |
|
|
Post subject: |
Re: Computing efficiently the dot product of homogeneous polys |
 |
|
Hi, for removing multiples of squares you can use NF, for example as follows: Code: > ideal I = x(1)^2, x(2)^2, x(3)^2, x(4)^2, x(5)^2, x(6)^2; I = groebner(I); option(redTail); NF(Q, I); -2*x(1)*x(2)*x(4)-x(1)*x(2)*x(5)+3*x(1)*x(4)*x(5)-x(2)*x(4)*x(5)-x(1)*x(2)*x(6)+x(1)*x(4)*x(6)-x(2)*x(4)*x(6)+x(1)*x(5)*x(6)-x(2)*x(5)*x(6)+2*x(4)*x(5)*x(6)
O.
Hi,
for removing multiples of squares you can use NF, for example as follows: [code] > ideal I = x(1)^2, x(2)^2, x(3)^2, x(4)^2, x(5)^2, x(6)^2; I = groebner(I); option(redTail); NF(Q, I); -2*x(1)*x(2)*x(4)-x(1)*x(2)*x(5)+3*x(1)*x(4)*x(5)-x(2)*x(4)*x(5)-x(1)*x(2)*x(6)+x(1)*x(4)*x(6)-x(2)*x(4)*x(6)+x(1)*x(5)*x(6)-x(2)*x(5)*x(6)+2*x(4)*x(5)*x(6) [/code]
O.
|
|
|
 |
Posted: Thu Nov 08, 2012 6:10 pm |
|
|
 |
|
|
Post subject: |
Re: Computing efficiently the dot product of homogeneous polys |
 |
|
Hi Oleksandr, yes this works but I need to improve it further. Indeed P is much smaller (about 200 times) than Q. Moreover, in these particular computations, I may assume that P is the product of all differences x(i)-x(j), 1<=i<j<=n (nvars=n). (In one computation, with n=9, I have size(P)=362 880 and size(Q)=75 510 055.) Thus each monomial in P has the exponents 0,1,2,...,n-1 up to a permutation. I would like to throw away from Q all monomials which have two equal exponents or at least one exponent >n-1 in order to make Q smaller. Is there a simple way to do at least one of these two things ? Thank you in advance for your answer, Dragomir
Hi Oleksandr, yes this works but I need to improve it further. Indeed P is much smaller (about 200 times) than Q. Moreover, in these particular computations, I may assume that P is the product of all differences x(i)-x(j), 1<=i<j<=n (nvars=n). (In one computation, with n=9, I have size(P)=362 880 and size(Q)=75 510 055.) Thus each monomial in P has the exponents 0,1,2,...,n-1 up to a permutation. I would like to throw away from Q all monomials which have two equal exponents or at least one exponent >n-1 in order to make Q smaller. Is there a simple way to do at least one of these two things ? Thank you in advance for your answer, Dragomir
|
|
|
 |
Posted: Thu Nov 08, 2012 1:07 am |
|
|
 |
|
|
Post subject: |
Re: Computing efficiently the dot product of homogeneous polys |
 |
|
Hi, what about using 'coef' as follows: Code: > ring R = 32003, (x(1..6)), dp; poly P=(x(1)-x(2))*(x(3)-x(4))*(x(5)-x(6)); > matrix M=coef(P, x(1)*x(2)*x(3)*x(4)*x(5)*x(6)); M; // needs the product of all ring variables!!! M[1,1]=x(1)*x(3)*x(5) M[1,2]=x(2)*x(3)*x(5) M[1,3]=x(1)*x(4)*x(5) M[1,4]=x(2)*x(4)*x(5) M[1,5]=x(1)*x(3)*x(6) M[1,6]=x(2)*x(3)*x(6) M[1,7]=x(1)*x(4)*x(6) M[1,8]=x(2)*x(4)*x(6) M[2,1]=1 M[2,2]=-1 M[2,3]=-1 M[2,4]=1 M[2,5]=-1 M[2,6]=1 M[2,7]=1 M[2,8]=-1 > ideal PP = M[1,1..ncols(M)]; PP; PP[1]=x(1)*x(3)*x(5) PP[2]=x(2)*x(3)*x(5) PP[3]=x(1)*x(4)*x(5) PP[4]=x(2)*x(4)*x(5) PP[5]=x(1)*x(3)*x(6) PP[6]=x(2)*x(3)*x(6) PP[7]=x(1)*x(4)*x(6) PP[8]=x(2)*x(4)*x(6) > coeffs(ideal(Q), PP); _[1,1]=0 _[2,1]=0 _[3,1]=3 _[4,1]=-1 _[5,1]=0 _[6,1]=0 _[7,1]=1 _[8,1]=-1
Hi,
what about using 'coef' as follows:
[code] > ring R = 32003, (x(1..6)), dp; poly P=(x(1)-x(2))*(x(3)-x(4))*(x(5)-x(6)); > matrix M=coef(P, x(1)*x(2)*x(3)*x(4)*x(5)*x(6)); M; // needs the product of all ring variables!!! M[1,1]=x(1)*x(3)*x(5) M[1,2]=x(2)*x(3)*x(5) M[1,3]=x(1)*x(4)*x(5) M[1,4]=x(2)*x(4)*x(5) M[1,5]=x(1)*x(3)*x(6) M[1,6]=x(2)*x(3)*x(6) M[1,7]=x(1)*x(4)*x(6) M[1,8]=x(2)*x(4)*x(6) M[2,1]=1 M[2,2]=-1 M[2,3]=-1 M[2,4]=1 M[2,5]=-1 M[2,6]=1 M[2,7]=1 M[2,8]=-1 > ideal PP = M[1,1..ncols(M)]; PP; PP[1]=x(1)*x(3)*x(5) PP[2]=x(2)*x(3)*x(5) PP[3]=x(1)*x(4)*x(5) PP[4]=x(2)*x(4)*x(5) PP[5]=x(1)*x(3)*x(6) PP[6]=x(2)*x(3)*x(6) PP[7]=x(1)*x(4)*x(6) PP[8]=x(2)*x(4)*x(6) > coeffs(ideal(Q), PP); _[1,1]=0 _[2,1]=0 _[3,1]=3 _[4,1]=-1 _[5,1]=0 _[6,1]=0 _[7,1]=1 _[8,1]=-1 [/code]
|
|
|
 |
Posted: Wed Nov 07, 2012 3:48 pm |
|
|
 |
|
|
Post subject: |
Re: Computing efficiently the dot product of homogeneous polys |
 |
|
Hi Oleksandr, I better not try to learn the internals of Singular! I like your suggestion and wanted to try it. But I realized immediately that there is a problem of defining the ideal PP. You probably did it by hand, but this is impossible for me since P has may be milions of terms. I could not find any function to convert a poly to the sequence of the monomials that occur in it. I could convert poly to a string and then replace the signs '+' and '-' with commas (although I do not know how to do that, just an idea) and at the same time eliminate the coefficients, to obtain this list as a string. But this seems rather complicated. There should be a better way. Can you help me with that problem? Thanks a lot, Dragomir
Hi Oleksandr, I better not try to learn the internals of Singular! I like your suggestion and wanted to try it. But I realized immediately that there is a problem of defining the ideal PP. You probably did it by hand, but this is impossible for me since P has may be milions of terms. I could not find any function to convert a poly to the sequence of the monomials that occur in it. I could convert poly to a string and then replace the signs '+' and '-' with commas (although I do not know how to do that, just an idea) and at the same time eliminate the coefficients, to obtain this list as a string. But this seems rather complicated. There should be a better way. Can you help me with that problem? Thanks a lot, Dragomir
|
|
|
 |
Posted: Tue Nov 06, 2012 10:26 pm |
|
|
 |
|
|
Post subject: |
Re: Computing efficiently the dot product of homogeneous polys |
 |
|
Well, for writing a dynamic module you will need to learn Singular internals. I would suggest starting by looking at Singular/extra.cc for experimental routines (which can be run e.g. via system("foo", arglist) ) and writing your own by analogy. Besides, did you consider converting the shortest of your polynomials into a monomial ideal (like PP below) and using "coeffs ( ideal_expression, ideal_expression ) " for example as follows? Code: > ring R = 32003, (x(1..6)), dp; poly P=(x(1)-x(2))*(x(3)-x(4))*(x(5)-x(6)); poly Q=(x(1)+x(4)+x(6))*(x(1)+x(4)+x(5))*(-x(2)+x(4)+x(5)); > ideal PP = x(1)*x(3)*x(5),x(2)*x(3)*x(5),x(1)*x(4)*x(5),x(2)*x(4)*x(5),x(1)*x(3)*x(6),x(2)*x(3)*x(6),x(1)*x(4)*x(6),x(2)*x(4)*x(6); > coeffs(ideal(P,Q), PP); _[1,1]=1 _[1,2]=0 _[2,1]=-1 _[2,2]=0 _[3,1]=-1 _[3,2]=3 _[4,1]=1 _[4,2]=-1 _[5,1]=-1 _[5,2]=0 _[6,1]=1 _[6,2]=0 _[7,1]=1 _[7,2]=1 _[8,1]=-1 _[8,2]=-1 > print(_); 1, 0, -1,0, -1,3, 1, -1, -1,0, 1, 0, 1, 1, -1,-1
Well, for writing a dynamic module you will need to learn Singular internals. I would suggest starting by looking at Singular/extra.cc for experimental routines (which can be run e.g. via system("foo", arglist) ) and writing your own by analogy.
Besides, did you consider converting the shortest of your polynomials into a monomial ideal (like PP below) and using "coeffs ( ideal_expression, ideal_expression ) " for example as follows?
[code] > ring R = 32003, (x(1..6)), dp; poly P=(x(1)-x(2))*(x(3)-x(4))*(x(5)-x(6)); poly Q=(x(1)+x(4)+x(6))*(x(1)+x(4)+x(5))*(-x(2)+x(4)+x(5)); > ideal PP = x(1)*x(3)*x(5),x(2)*x(3)*x(5),x(1)*x(4)*x(5),x(2)*x(4)*x(5),x(1)*x(3)*x(6),x(2)*x(3)*x(6),x(1)*x(4)*x(6),x(2)*x(4)*x(6); > coeffs(ideal(P,Q), PP); _[1,1]=1 _[1,2]=0 _[2,1]=-1 _[2,2]=0 _[3,1]=-1 _[3,2]=3 _[4,1]=1 _[4,2]=-1 _[5,1]=-1 _[5,2]=0 _[6,1]=1 _[6,2]=0 _[7,1]=1 _[7,2]=1 _[8,1]=-1 _[8,2]=-1 > print(_); 1, 0, -1,0, -1,3, 1, -1, -1,0, 1, 0, 1, 1, -1,-1 [/code]
|
|
|
 |
Posted: Mon Nov 05, 2012 7:18 pm |
|
|
 |
|
|
Post subject: |
Re: Computing efficiently the dot product of homogeneous polys |
 |
|
Well, I am familiar with "coef" and "coeffs" commands. They have to be used several times to get down to the coefficients that I need and I could not make it efficient. I do not have any experience in writing the module that you mentioned. Where can I learn how to do that? Thanks, Dragomir
Well, I am familiar with "coef" and "coeffs" commands. They have to be used several times to get down to the coefficients that I need and I could not make it efficient. I do not have any experience in writing the module that you mentioned. Where can I learn how to do that? Thanks, Dragomir
|
|
|
 |
Posted: Sun Nov 04, 2012 5:47 pm |
|
|
 |
|
|
Post subject: |
Re: Computing efficiently the dot product of homogeneous polys |
 |
|
I see. Sorry, i got confused by "The bilinear dot product is defined by postulating that the monomials form an orthonormal basis" since exterior algebra can be used for dealing with orthogonal monomial bases but probably will not do for your computation.
Please take a look at 'coeffs' and 'coeff' commands.
If those are too inefficient - one could consider writing a tiny dynamic module for that kind of kernel operation (list intersection with a twist).
Cheers, Oleksandr
I see. Sorry, i got confused by "The bilinear dot product is defined by postulating that the monomials form an orthonormal basis" since exterior algebra can be used for dealing with orthogonal monomial bases but probably will not do for your computation.
Please take a look at 'coeffs' and 'coeff' commands.
If those are too inefficient - one could consider writing a tiny dynamic module for that kind of kernel operation (list intersection with a twist).
Cheers, Oleksandr
|
|
|
 |
Posted: Sun Nov 04, 2012 2:17 pm |
|
|
 |
|
|
Post subject: |
Re: Computing efficiently the dot product of homogeneous polys |
 |
|
Dear Oleksandr, I really do not understand what this non-commutative ring has to do with my problem. May be I did not explain well what I mean by "inner product" (or "dot product"). Given a monomial M that occurs in P, say with coefficient "a", we have to test whether M also occurs in Q. If it does, and has coefficient "b", then I take the product "ab" of these coefficients. I run through all possible M's that occur in P and take the sum of all products "ab" that arise. This sum is my "inner product" which I want to compute. Dragomir
Dear Oleksandr, I really do not understand what this non-commutative ring has to do with my problem. May be I did not explain well what I mean by "inner product" (or "dot product"). Given a monomial M that occurs in P, say with coefficient "a", we have to test whether M also occurs in Q. If it does, and has coefficient "b", then I take the product "ab" of these coefficients. I run through all possible M's that occur in P and take the sum of all products "ab" that arise. This sum is my "inner product" which I want to compute. Dragomir
|
|
|
 |
Posted: Sun Nov 04, 2012 2:32 am |
|
|
 |
|
|
Post subject: |
Re: Computing efficiently the dot product of homogeneous polys |
 |
|
here you go: Code: > LIB "nctools.lib"; ring R = 32003, (x(1..6)), dp; def E = superCommutative(1,6); setring E; E; // characteristic : 32003 // number of vars : 6 // block 1 : ordering dp // : names x(1) x(2) x(3) x(4) x(5) x(6) // block 2 : ordering C // noncommutative relations: // x(2)x(1)=-x(1)*x(2) // x(3)x(1)=-x(1)*x(3) // x(4)x(1)=-x(1)*x(4) // x(5)x(1)=-x(1)*x(5) // x(6)x(1)=-x(1)*x(6) // x(3)x(2)=-x(2)*x(3) // x(4)x(2)=-x(2)*x(4) // x(5)x(2)=-x(2)*x(5) // x(6)x(2)=-x(2)*x(6) // x(4)x(3)=-x(3)*x(4) // x(5)x(3)=-x(3)*x(5) // x(6)x(3)=-x(3)*x(6) // x(5)x(4)=-x(4)*x(5) // x(6)x(4)=-x(4)*x(6) // x(6)x(5)=-x(5)*x(6) // quotient ring from ideal _[1]=x(6)^2 _[2]=x(5)^2 _[3]=x(4)^2 _[4]=x(3)^2 _[5]=x(2)^2 _[6]=x(1)^2 > poly P=(x(1)-x(2))*(x(3)-x(4))*(x(5)-x(6)); P; x(1)*x(3)*x(5)-x(2)*x(3)*x(5)-x(1)*x(4)*x(5)+x(2)*x(4)*x(5)-x(1)*x(3)*x(6)+x(2)*x(3)*x(6)+x(1)*x(4)*x(6)-x(2)*x(4)*x(6) > poly Q=(x(1)+x(4)+x(6))*(x(1)+x(4)+x(5))*(-x(2)+x(4)+x(5)); Q; x(1)*x(2)*x(5)-x(1)*x(4)*x(5)-x(2)*x(4)*x(5)-x(1)*x(2)*x(6)+x(1)*x(4)*x(6)+x(2)*x(4)*x(6)+x(1)*x(5)*x(6)+x(2)*x(5)*x(6) > P*Q; 0
note that x(i)*x(j) + x(j)*x(i) == 0
here you go: [code] > LIB "nctools.lib"; ring R = 32003, (x(1..6)), dp; def E = superCommutative(1,6); setring E; E; // characteristic : 32003 // number of vars : 6 // block 1 : ordering dp // : names x(1) x(2) x(3) x(4) x(5) x(6) // block 2 : ordering C // noncommutative relations: // x(2)x(1)=-x(1)*x(2) // x(3)x(1)=-x(1)*x(3) // x(4)x(1)=-x(1)*x(4) // x(5)x(1)=-x(1)*x(5) // x(6)x(1)=-x(1)*x(6) // x(3)x(2)=-x(2)*x(3) // x(4)x(2)=-x(2)*x(4) // x(5)x(2)=-x(2)*x(5) // x(6)x(2)=-x(2)*x(6) // x(4)x(3)=-x(3)*x(4) // x(5)x(3)=-x(3)*x(5) // x(6)x(3)=-x(3)*x(6) // x(5)x(4)=-x(4)*x(5) // x(6)x(4)=-x(4)*x(6) // x(6)x(5)=-x(5)*x(6) // quotient ring from ideal _[1]=x(6)^2 _[2]=x(5)^2 _[3]=x(4)^2 _[4]=x(3)^2 _[5]=x(2)^2 _[6]=x(1)^2 > poly P=(x(1)-x(2))*(x(3)-x(4))*(x(5)-x(6)); P; x(1)*x(3)*x(5)-x(2)*x(3)*x(5)-x(1)*x(4)*x(5)+x(2)*x(4)*x(5)-x(1)*x(3)*x(6)+x(2)*x(3)*x(6)+x(1)*x(4)*x(6)-x(2)*x(4)*x(6) > poly Q=(x(1)+x(4)+x(6))*(x(1)+x(4)+x(5))*(-x(2)+x(4)+x(5)); Q; x(1)*x(2)*x(5)-x(1)*x(4)*x(5)-x(2)*x(4)*x(5)-x(1)*x(2)*x(6)+x(1)*x(4)*x(6)+x(2)*x(4)*x(6)+x(1)*x(5)*x(6)+x(2)*x(5)*x(6) > P*Q; 0 [/code]
note that x(i)*x(j) + x(j)*x(i) == 0
|
|
|
 |
Posted: Sat Nov 03, 2012 5:17 pm |
|
|
 |
|
|
Post subject: |
Re: Computing efficiently the dot product of homogeneous polys |
 |
|
malex wrote: Hi! Could you please give a small example? Besides, i would suggest using tensor product of your polynomial algebra with a non-commutative quotient algebra generated by your basis vectors (e.g. graded commutative http://www.singular.uni-kl.de/Manual/3- ... htm#SEC566 or similar) Cheers, Oleksandr Hi, yes of course: Ring 32003, (x(1..6)), dp; poly P=(x(1)-x(2))*(x(3)-x(4))*(x(5)-x(6)); poly Q=(x(1)+x(4)+x(6))*(x(1)+x(4)+x(5))*(-x(2)+x(4)+x(5)); I think Singular expands the polynomials, so we get P=x(1)*x(3)*x(5)-(x(1)*x(3)*x(6)-x(1)*x(4)*x(5)-... Q=-x(1)^2*x(2)+x(1)^2*x(4)+x(1)^1*x(5)-2*x(1)*x(2)*x(4)+2*x(1)*x(4)^2+3*x(1)*x(4)*x(5)-... There are no squares of variables in P so all the termis in Q containing a square of a variable can be ignored (they are orthogonal to each term of P). The monomial x(1)*x(4)*x(5) occurs in both P and Q, with coefficients -1 and 3 respectively. Their contribution to the inner product (P|Q) is (-1)*3 = -3. The answer in this case is that (P|Q)=-2. I did not have time yet to follow your suggestion above (I shall try that later). However, if you can give me a short example of how to proceed, that would be the best. Thanks, Dragomir
[quote="malex"]Hi!
Could you please give a small example?
Besides, i would suggest using tensor product of your polynomial algebra with a non-commutative quotient algebra generated by your basis vectors (e.g. graded commutative http://www.singular.uni-kl.de/Manual/3-1-5/sing_514.htm#SEC566 or similar)
Cheers, Oleksandr[/quote] Hi, yes of course:
Ring 32003, (x(1..6)), dp; poly P=(x(1)-x(2))*(x(3)-x(4))*(x(5)-x(6)); poly Q=(x(1)+x(4)+x(6))*(x(1)+x(4)+x(5))*(-x(2)+x(4)+x(5));
I think Singular expands the polynomials, so we get
P=x(1)*x(3)*x(5)-(x(1)*x(3)*x(6)-x(1)*x(4)*x(5)-... Q=-x(1)^2*x(2)+x(1)^2*x(4)+x(1)^1*x(5)-2*x(1)*x(2)*x(4)+2*x(1)*x(4)^2+3*x(1)*x(4)*x(5)-...
There are no squares of variables in P so all the termis in Q containing a square of a variable can be ignored (they are orthogonal to each term of P). The monomial x(1)*x(4)*x(5) occurs in both P and Q, with coefficients -1 and 3 respectively. Their contribution to the inner product (P|Q) is (-1)*3 = -3. The answer in this case is that (P|Q)=-2.
I did not have time yet to follow your suggestion above (I shall try that later). However, if you can give me a short example of how to proceed, that would be the best. Thanks, Dragomir
|
|
|
 |
Posted: Sat Nov 03, 2012 4:46 pm |
|
|
 |
|
|
Post subject: |
Re: Computing efficiently the dot product of homogeneous polys |
 |
|
Hi! Could you please give a small example? Besides, i would suggest using tensor product of your polynomial algebra with a non-commutative quotient algebra generated by your basis vectors (e.g. graded commutative http://www.singular.uni-kl.de/Manual/3- ... htm#SEC566 or similar) Cheers, Oleksandr
Hi!
Could you please give a small example?
Besides, i would suggest using tensor product of your polynomial algebra with a non-commutative quotient algebra generated by your basis vectors (e.g. graded commutative http://www.singular.uni-kl.de/Manual/3-1-5/sing_514.htm#SEC566 or similar)
Cheers, Oleksandr
|
|
|
 |
Posted: Fri Nov 02, 2012 12:11 am |
|
|
 |
|
|
Post subject: |
Computing efficiently the dot product of homogeneous polys |
 |
|
Let P and Q be homogeneous polys of the same degree d in several variables. The bilinear dot product is defined by postulating that the momomials form an orthonormal basis. The degree d is large and P and Q have each a lot of terms. I would like to compute the dot product of P and Q efficiently trying to minimize the need for additional memory. Any suggestions how to do this will be greatly appreciated. Thanks.
Let P and Q be homogeneous polys of the same degree d in several variables. The bilinear dot product is defined by postulating that the momomials form an orthonormal basis. The degree d is large and P and Q have each a lot of terms. I would like to compute the dot product of P and Q efficiently trying to minimize the need for additional memory. Any suggestions how to do this will be greatly appreciated. Thanks.
|
|
|
 |
Posted: Wed Oct 31, 2012 6:02 pm |
|
|
 |
|
|
It is currently Fri May 13, 2022 10:58 am
|
|