Re: [sage-devel] Re: InfinitePolynomialRing is -- very -- slow
On Thu, Nov 26, 2009 at 01:42:35PM -0800, Nick Alexander wrote: > Two things, mostly. The huge amount of code that wasn't being > merged -- that appears to now be merged :) For a good part, that was just an instance of a general issue with Sage's slow review process (and I don't have good suggestions to improve it, except to make it technically easier, as has been discussed on the list, in order to encourage more reviewers). > And the whole categories/generic code effort: while I support the > ends, I'm worried that the system will become so slow that it is > unusable in practice. Which is strange, because I'm not usually the > one arguing for efficiency over clarity! Well, give it a shot! I would very much would like to get reports on slowness that can be attributed to the category code :-) Besides what Florent says about creation of parents, there is another issue: category code cannot be fully cyphoned, because Cython does not support multiple inheritance. But a Cython class still can use generic code from categories (see e.g. sage.categories.examples.semigroups_cython) > I know they are mathematically, but at the moment it's very hard to > take QQ['x', 'y'] and view it as a vector space over QQ. > Essentially, it's not easy to say that monomials x^i*y^j are the > basis for some free module over QQ, and have sage convert back and > forth. Or better directly have a basis and basis related operations in QQ['x','y']; as Florent said, making QQ['x','y'] an AlgebrasWithBasis(QQ) is in the plans, and help is welcome :-) Cheers, Nicolas -- Nicolas M. Thiéry "Isil" http://Nicolas.Thiery.name/ -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel-unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
Re: [sage-devel] Re: InfinitePolynomialRing is -- very -- slow
> > Could you elaborate ? What's makes you skeptical ? > > Two things, mostly. The huge amount of code that wasn't being merged > -- that appears to now be merged :) And the whole categories/generic > code effort: while I support the ends, I'm worried that the system > will become so slow that it is unusable in practice. Which is > strange, because I'm not usually the one arguing for efficiency over > clarity! The only thing It could make slow is the creation of some parent, since it only change inheritance. After that whether a methods is inherited from a class or another one shouldn't change anything in the speed. So unless (like me :-) you like creating new parent everything should be alright. Let me explain the smiley. I'm currently testing a conjecture whose input is a monoid so in the next windows on my screen sage it writing a lot of things and in particular creating a new monoid every two second. > >> But if you guys allow me to view a multivariate polynomial ring as a > >> module over its base ring I will be very grateful. > > > > Of course they are ! I have no clue about why you say that ? Could > > you explain > > yourself ? So what ? > > I know they are mathematically, but at the moment it's very hard to > take QQ['x', 'y'] and view it as a vector space over QQ. Essentially, > it's not easy to say that monomials x^i*y^j are the basis for some > free module over QQ, and have sage convert back and forth. But it > sounds like you can do that too! I remember fixing the very same problem in MuPAD a few years ago. I remember fixing it for matrices as well :-). That's typically a problem categories are designed to solve. Cheers, Florent -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel-unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
Re: [sage-devel] Re: InfinitePolynomialRing is -- very -- slow
On 26-Nov-09, at 12:23 PM, Florent Hivert wrote: >>> On Thu, Nov 26, 2009 at 08:30:53AM -0800, YannLC wrote: Just a toy implementation as a very thin layer over dict (at least it should be fast) >>> >>> That's precisely what CombinatorialFreeModule elements are :-) >>> >>> Further optimizations to it are most welcome (For example, I am not >>> sure += is implemented there)! >>> >>> Yes, the name is bad: there is nothing combinatorial to it. Merging >>> this into FreeModule so that one could do FreeModule(QQ, >>> Objects()) is >>> part of the future plan. >> >> I have been an observer of the sage-combinat process since its >> inception and, I must say, I have been mildly skeptical (very >> mildly). > > Could you elaborate ? What's makes you skeptical ? Two things, mostly. The huge amount of code that wasn't being merged -- that appears to now be merged :) And the whole categories/generic code effort: while I support the ends, I'm worried that the system will become so slow that it is unusable in practice. Which is strange, because I'm not usually the one arguing for efficiency over clarity! >> But if you guys allow me to view a multivariate polynomial ring as a >> module over its base ring I will be very grateful. > > Of course they are ! I have no clue about why you say that ? Could > you explain > yourself ? So what ? I know they are mathematically, but at the moment it's very hard to take QQ['x', 'y'] and view it as a vector space over QQ. Essentially, it's not easy to say that monomials x^i*y^j are the basis for some free module over QQ, and have sage convert back and forth. But it sounds like you can do that too! Nick -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel-unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
Re: [sage-devel] Re: InfinitePolynomialRing is -- very -- slow
> > On Thu, Nov 26, 2009 at 08:30:53AM -0800, YannLC wrote: > >> Just a toy implementation as a very thin layer over dict (at least it > >> should be fast) > > > > That's precisely what CombinatorialFreeModule elements are :-) > > > > Further optimizations to it are most welcome (For example, I am not > > sure += is implemented there)! > > > > Yes, the name is bad: there is nothing combinatorial to it. Merging > > this into FreeModule so that one could do FreeModule(QQ, Objects()) is > > part of the future plan. > > I have been an observer of the sage-combinat process since its > inception and, I must say, I have been mildly skeptical (very mildly). Could you elaborate ? What's makes you skeptical ? > But if you guys allow me to view a multivariate polynomial ring as a > module over its base ring I will be very grateful. Of course they are ! I have no clue about why you say that ? Could you explain yourself ? So what ? Cheers, Florent -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel-unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
Re: [sage-devel] Re: InfinitePolynomialRing is -- very -- slow
On 26-Nov-09, at 10:18 AM, Nicolas M. Thiery wrote: > On Thu, Nov 26, 2009 at 08:30:53AM -0800, YannLC wrote: >> Just a toy implementation as a very thin layer over dict (at least it >> should be fast) > > That's precisely what CombinatorialFreeModule elements are :-) > > Further optimizations to it are most welcome (For example, I am not > sure += is implemented there)! > > Yes, the name is bad: there is nothing combinatorial to it. Merging > this into FreeModule so that one could do FreeModule(QQ, Objects()) is > part of the future plan. I have been an observer of the sage-combinat process since its inception and, I must say, I have been mildly skeptical (very mildly). But if you guys allow me to view a multivariate polynomial ring as a module over its base ring I will be very grateful. Nick -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel-unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
[sage-devel] Re: InfinitePolynomialRing is -- very -- slow
On Nov 26, 9:31 am, Simon King wrote: > InfinitePolynomialRing has an underlying *finite* polynomial ring, > that changes whenever you need a variable that is not in the finite > ring. Hi, I have seen this thread has various aspects and I don't know the details, but just reading this it reminds me of dynamic arrays. I think it could be enhanced by allocating a bigger new finite polynomial ring. In the end the usecase of adding new variables should be very common. I suggest to increase it by floor(size*0.6) since this is afaik a good value for that type of operation. I have read that there is a penalty with overestimations, probably there should also be a method to compact it? H -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel-unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
Re: [sage-devel] Re: InfinitePolynomialRing is -- very -- slow
On Thu, Nov 26, 2009 at 05:09:13PM +0100, Florent hivert wrote: > > On Thu, Nov 26, 2009 at 06:54:43AM -0800, Nathann Cohen wrote: > > > Actually, I use these polynomials to emulate what your > > > CombinatorialFreeModule does on a much larger basis : everything that > > > is hashable ;-) > > > > > > I want to be able to index my variables with sets, with edges, with > > > nodes, with almost anything we can come up with in Sage... > > > > sage: F = CombinatorialFreeModule(QQ, Objects()) > > sage: x = F.basis() > > sage: x[1] + x[2.5] + x[Partition([3,2,1])] + x [ QQ ] + x[gap] + > > x[x[3]+x[2]] > > B[2.50] + B[1] + B[B[2] + B[3]] + B[Gap] + B[[3, 2, 1]] + > > B[Rational Field] > > > > Good enough? :-) > > Nice :-) ? > > Now I see the point to not requiring that the basis of a > CombinatorialFreeModule is an EnumeratedSets... Yeah, enumerating Objects() might be an issue :-) Although, technically, there are only a countable number of objects that one can construct in Sage! Cheers, Nicolas -- Nicolas M. Thiéry "Isil" http://Nicolas.Thiery.name/ -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel-unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
Re: [sage-devel] Re: InfinitePolynomialRing is -- very -- slow
On Thu, Nov 26, 2009 at 08:30:53AM -0800, YannLC wrote: > Just a toy implementation as a very thin layer over dict (at least it > should be fast) That's precisely what CombinatorialFreeModule elements are :-) Further optimizations to it are most welcome (For example, I am not sure += is implemented there)! Yes, the name is bad: there is nothing combinatorial to it. Merging this into FreeModule so that one could do FreeModule(QQ, Objects()) is part of the future plan. Cheers, Nicolas -- Nicolas M. Thiéry "Isil" http://Nicolas.Thiery.name/ -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel-unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
[sage-devel] Re: InfinitePolynomialRing is -- very -- slow
Just a toy implementation as a very thin layer over dict (at least it
should be fast)
no doc
-
first see it in action:
sage: x=Test()
sage: p=x.zero_element()
sage: time for i in range(1): p+=x[i]
CPU times: user 0.10 s, sys: 0.00 s, total: 0.10 s
Wall time: 0.10 s
sage: time q=p*3
CPU times: user 0.04 s, sys: 0.00 s, total: 0.04 s
Wall time: 0.05 s
sage: time q-(2*p+p)
CPU times: user 0.10 s, sys: 0.00 s, total: 0.10 s
Wall time: 0.10 s
0
sage: time r=sum([x[i] for i in range(1)],x.zero_element())
CPU times: user 2.69 s, sys: 0.00 s, total: 2.70 s
Wall time: 2.70 s
sage: time p==r
CPU times: user 0.00 s, sys: 0.00 s, total: 0.00 s
Wall time: 0.00 s
True
sage: x[1] + x[2.5] + x[Partition([3,2,1])] + x [ QQ ] + x[gap] + x[x
[3]+x[2]]
1*B[2.50] + 1*B[1] + 1*B[Gap] + 1*B[ 1*B[2] + 1*B[3] ] +
1*B[[3, 2, 1]] + 1*B[Rational Field]
(NB: += is way faster than +)
-
if it can help, here is the code:
class Test(UniqueRepresentation):
def __getitem__(self,x):
return TestElement(x)
def zero_element(self):
return TestElement({})
class TestElement:
def __init__(self, x):
if isinstance(x,dict):
self._dict=dict(x)
else:
self._dict={x:1}
def __add__(self,other):
out = TestElement(self._dict)
return out.__iadd__(other)
def __sub__(self,other):
out = TestElement(self._dict)
return out.__isub__(other)
def __mul__(self,k):
out = TestElement(self._dict)
return out.__imul__(k)
def __rmul__(self,k):
out = TestElement(self._dict)
for x,v in out._dict.iteritems():
out._dict[x]= k*v
return out
def __div__(self,k):
out = TestElement(self._dict)
return out.__idiv__(k)
def __iadd__(self,other):
d = self._dict
for i,c in other._dict.iteritems():
if i in d:
d[i] += c
if not d[i]:
del d[i]
else:
d[i] = c
return self
def __isub__(self,other):
d = self._dict
for i,c in other._dict.iteritems():
if i in d:
d[i] -= c
if not d[i]:
del d[i]
else:
d[i] = c
return self
def __imul__(self,k):
for x,v in self._dict.iteritems():
self._dict[x]=v*k
return self
def __idiv__(self,k):
for x,v in self._dict.iteritems():
self._dict[x]=k/v
return self
def __getitem__(self,i):
return self._dict.get(i,0)
def __setitem__(self,x,v):
self._dict[x]=v
def __repr__(self):
if len(self._dict) == 0:
return "0"
return '+'.join([" %s*B[%s] "%(str(v),str(x)) for x,v in
self._dict.iteritems()])
def __hash__(self):
return hash(frozenset(self._dict))
def __cmp__(self,other):
return self._dict.__cmp__(other._dict)
--
To post to this group, send an email to sage-devel@googlegroups.com
To unsubscribe from this group, send an email to
sage-devel-unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-devel
URL: http://www.sagemath.org
Re: [sage-devel] Re: InfinitePolynomialRing is -- very -- slow
> On Thu, Nov 26, 2009 at 06:54:43AM -0800, Nathann Cohen wrote: > > Actually, I use these polynomials to emulate what your > > CombinatorialFreeModule does on a much larger basis : everything that > > is hashable ;-) > > > > I want to be able to index my variables with sets, with edges, with > > nodes, with almost anything we can come up with in Sage... > > sage: F = CombinatorialFreeModule(QQ, Objects()) > sage: x = F.basis() > sage: x[1] + x[2.5] + x[Partition([3,2,1])] + x [ QQ ] + x[gap] + x[x[3]+x[2]] > B[2.50] + B[1] + B[B[2] + B[3]] + B[Gap] + B[[3, 2, 1]] + > B[Rational Field] > > Good enough? :-) Nice :-) ? Now I see the point to not requiring that the basis of a CombinatorialFreeModule is an EnumeratedSets... Cheers, Florent -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel-unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
Re: [sage-devel] Re: InfinitePolynomialRing is -- very -- slow
On Thu, Nov 26, 2009 at 06:54:43AM -0800, Nathann Cohen wrote: > Actually, I use these polynomials to emulate what your > CombinatorialFreeModule does on a much larger basis : everything that > is hashable ;-) > > I want to be able to index my variables with sets, with edges, with > nodes, with almost anything we can come up with in Sage... sage: F = CombinatorialFreeModule(QQ, Objects()) sage: x = F.basis() sage: x[1] + x[2.5] + x[Partition([3,2,1])] + x [ QQ ] + x[gap] + x[x[3]+x[2]] B[2.50] + B[1] + B[B[2] + B[3]] + B[Gap] + B[[3, 2, 1]] + B[Rational Field] Good enough? :-) Cheers, Nicolas -- Nicolas M. Thiéry "Isil" http://Nicolas.Thiery.name/ -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel-unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
[sage-devel] Re: InfinitePolynomialRing is -- very -- slow
Actually, I use these polynomials to emulate what your CombinatorialFreeModule does on a much larger basis : everything that is hashable ;-) I want to be able to index my variables with sets, with edges, with nodes, with almost anything we can come up with in Sage... Nathann On Nov 26, 3:39 pm, "Nicolas M. Thiery" wrote: > On Thu, Nov 26, 2009 at 05:29:47AM -0800, YannLC wrote: > > If you only want linear terms, you can also use an univariate > > polynomial ring > > > just treat x^i as x_i. > > > it's lightning fast and allow you to easily access coefficients. > > Variant: > > sage: F =CombinatorialFreeModule(QQ, NonNegativeIntegers()) > sage: x = F.basis() > sage: x[3] + 2* x[8] > B[3] + 2*B[8] > sage: f = x[3] + 2* x[8] > sage: f[8] > 2 > > This models more straightforwardly your problem. However, it's > currently (by far) not as fast as polynomials. This slowness will be > fixed as soon as the sparse free module code will have been > generalized to handle FreeModule(QQ, infinity). > > Best, > Nicolas > -- > Nicolas M. Thi ry "Isil" http://Nicolas.Thiery.name/ -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel-unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
Re: [sage-devel] Re: InfinitePolynomialRing is -- very -- slow
On Thu, Nov 26, 2009 at 05:29:47AM -0800, YannLC wrote: > If you only want linear terms, you can also use an univariate > polynomial ring > > just treat x^i as x_i. > > it's lightning fast and allow you to easily access coefficients. Variant: sage: F =CombinatorialFreeModule(QQ, NonNegativeIntegers()) sage: x = F.basis() sage: x[3] + 2* x[8] B[3] + 2*B[8] sage: f = x[3] + 2* x[8] sage: f[8] 2 This models more straightforwardly your problem. However, it's currently (by far) not as fast as polynomials. This slowness will be fixed as soon as the sparse free module code will have been generalized to handle FreeModule(QQ, infinity). Best, Nicolas -- Nicolas M. Thiéry "Isil" http://Nicolas.Thiery.name/ -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel-unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
[sage-devel] Re: InfinitePolynomialRing is -- very -- slow
Then I think you found the very thing I needed... Thank you !!! :-) I do not need 1 millions variables, but clearly I do not want the computations to be too slow under 1.. If I have something like 1000 variables, I very often have 5000 or more functions to define and work on, so I need the symbolic expression to be handled easily by Sage ! Nathann On Nov 26, 3:15 pm, YannLC wrote: > because you use dense representation. > > Try P.=PolynomialRing(QQ,sparse=True) > > By the way, do you need QQ? RR or ZZ would probably be faster. > > On Nov 26, 3:06 pm, Nathann Cohen wrote: > > > I could cache the results... But I still do not understand why just > > evaluating x^99 takes so much time ! > > You really need 1 million variables?! -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel-unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
[sage-devel] Re: InfinitePolynomialRing is -- very -- slow
On Nov 26, 2:17 pm, Simon King wrote: [...] > However, if I understood correctly, you have a *uni*variate polynomial > ring, right? So, probably you can disregard what I just said, since > univariate polynomial rings are different from multivariate (based on > ntl? not sure...) . Yep, as pointed out by Yann... -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel-unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
[sage-devel] Re: InfinitePolynomialRing is -- very -- slow
Hi Nathann! On Nov 26, 2:06 pm, Nathann Cohen wrote: > I could cache the results... But I still do not understand why just > evaluating x^99 takes so much time ! I guess this is a limitation of Singular. In Singular, exponents are restricted to 32767. Usually, multivariate polynomial rings in Sage are based on libSingular, and I guess it has the same limitation. Compare http://www.singular.uni-kl.de/Manual/latest/sing_343.htm#SEC384 So, if you have a larger exponent, Sage has to fall back to a different (and probably much slower) implementation. However, if I understood correctly, you have a *uni*variate polynomial ring, right? So, probably you can disregard what I just said, since univariate polynomial rings are different from multivariate (based on ntl? not sure...) . Perhaps there are similar limitations? Cheers, Simon -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel-unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
[sage-devel] Re: InfinitePolynomialRing is -- very -- slow
because you use dense representation. Try P.=PolynomialRing(QQ,sparse=True) By the way, do you need QQ? RR or ZZ would probably be faster. On Nov 26, 3:06 pm, Nathann Cohen wrote: > I could cache the results... But I still do not understand why just > evaluating x^99 takes so much time ! You really need 1 million variables?! -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel-unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
[sage-devel] Re: InfinitePolynomialRing is -- very -- slow
I could cache the results... But I still do not understand why just evaluating x^99 takes so much time ! On Nov 26, 2:54 pm, YannLC wrote: > can you avoid sums for initialisation? > > sage: P.=PolynomialRing(QQ) > sage: time p=P(dict([(i,1) for i in range()])) > CPU times: user 0.07 s, sys: 0.00 s, total: 0.07 s > Wall time: 0.07 s > > On Nov 26, 2:43 pm, Nathann Cohen wrote: > > > R = PolynomialRing(QQ, 'x') > > x = R.gen() > > sum([x^i for i in range(2,)]) > > > This is still very slow ( even if the values are larger ) :-/ > > > Nathann -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel-unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
[sage-devel] Re: InfinitePolynomialRing is -- very -- slow
can you avoid sums for initialisation? sage: P.=PolynomialRing(QQ) sage: time p=P(dict([(i,1) for i in range()])) CPU times: user 0.07 s, sys: 0.00 s, total: 0.07 s Wall time: 0.07 s On Nov 26, 2:43 pm, Nathann Cohen wrote: > R = PolynomialRing(QQ, 'x') > x = R.gen() > sum([x^i for i in range(2,)]) > > This is still very slow ( even if the values are larger ) :-/ > > Nathann -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel-unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
[sage-devel] Re: InfinitePolynomialRing is -- very -- slow
R = PolynomialRing(QQ, 'x') x = R.gen() sum([x^i for i in range(2,)]) This is still very slow ( even if the values are larger ) :-/ Nathann -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel-unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
[sage-devel] Re: InfinitePolynomialRing is -- very -- slow
Oops, I misread your message... You're right !! ;-) -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel-unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
[sage-devel] Re: InfinitePolynomialRing is -- very -- slow
My problem is that I am dealing with linear functions having an arbitrary large number of variables. Nathann -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel-unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
[sage-devel] Re: InfinitePolynomialRing is -- very -- slow
If you only want linear terms, you can also use an univariate polynomial ring just treat x^i as x_i. it's lightning fast and allow you to easily access coefficients. On Nov 26, 2:10 pm, Nathann Cohen wrote: > Hello !!! > > I am writing the patch to move from InfinitePolynomialRing to just "var > ()", and I am having several annoying problems : > To obtain the coefficients of each variable, I have to write > for v in expression.variables(): > c = expression.coefficient(v) > > And I wonder if this is not a quadratic algorithm while it should be > linear to get "all" the coefficients > > The coefficients are not assumed to be "real values". They are assumed > to be "expression", and I have to evaluate them using n() to get the > value. > > This things transforms all the equations from 2 * x[1] - 3 * x[2] to > 2.00 x[1] - 3.00 * x[2] which makes all the outputs > clearly unreadable... > > How could I get these values without such things happening ? > > Thank you !!! > > Nathann > > On Nov 26, 12:11 pm, Burcin Erocal wrote: > > > On Thu, 26 Nov 2009 02:51:17 -0800 (PST) > > > Nathann Cohen wrote: > > > Hmm After thinking about it for a bit, is using var() really a > > > good solution ? It is fast and everything, but I use my variables in > > > functions that should not spoil the userspace with them ! When I > > > define symbolic variables, they are global and could even be accessed > > > in the userspace... Can this be avoided ? > > > If you're using Cython you can bypass the global symbol registry and > > construct your symbols using pynac directly. > > > This untested function (based on sage.symbolic.ring.SymbolicRing.symbol) > > might work: > > > def my_symbol(name): > > cdef GSymbol symb > > GSymbol_construct_str(&symb, name) > > cdef Expression e > > e = PY_NEW(Expression) > > GEx_construct_symbol(&e._gobj, symb) > > e._parent = SR > > return e > > > You need to include sage/libs/ginac/decl.pxi to get the declarations of > > GSymbol, GSymbol_construct_str, etc. > > > Cheers, > > Burcin -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel-unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
[sage-devel] Re: InfinitePolynomialRing is -- very -- slow
Hello !!! I am writing the patch to move from InfinitePolynomialRing to just "var ()", and I am having several annoying problems : To obtain the coefficients of each variable, I have to write for v in expression.variables(): c = expression.coefficient(v) And I wonder if this is not a quadratic algorithm while it should be linear to get "all" the coefficients The coefficients are not assumed to be "real values". They are assumed to be "expression", and I have to evaluate them using n() to get the value. This things transforms all the equations from 2 * x[1] - 3 * x[2] to 2.00 x[1] - 3.00 * x[2] which makes all the outputs clearly unreadable... How could I get these values without such things happening ? Thank you !!! Nathann On Nov 26, 12:11 pm, Burcin Erocal wrote: > On Thu, 26 Nov 2009 02:51:17 -0800 (PST) > > Nathann Cohen wrote: > > Hmm After thinking about it for a bit, is using var() really a > > good solution ? It is fast and everything, but I use my variables in > > functions that should not spoil the userspace with them ! When I > > define symbolic variables, they are global and could even be accessed > > in the userspace... Can this be avoided ? > > If you're using Cython you can bypass the global symbol registry and > construct your symbols using pynac directly. > > This untested function (based on sage.symbolic.ring.SymbolicRing.symbol) > might work: > > def my_symbol(name): > cdef GSymbol symb > GSymbol_construct_str(&symb, name) > cdef Expression e > e = PY_NEW(Expression) > GEx_construct_symbol(&e._gobj, symb) > e._parent = SR > return e > > You need to include sage/libs/ginac/decl.pxi to get the declarations of > GSymbol, GSymbol_construct_str, etc. > > Cheers, > Burcin -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel-unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
Re: [sage-devel] Re: InfinitePolynomialRing is -- very -- slow
On Thu, 26 Nov 2009 02:51:17 -0800 (PST) Nathann Cohen wrote: > Hmm After thinking about it for a bit, is using var() really a > good solution ? It is fast and everything, but I use my variables in > functions that should not spoil the userspace with them ! When I > define symbolic variables, they are global and could even be accessed > in the userspace... Can this be avoided ? If you're using Cython you can bypass the global symbol registry and construct your symbols using pynac directly. This untested function (based on sage.symbolic.ring.SymbolicRing.symbol) might work: def my_symbol(name): cdef GSymbol symb GSymbol_construct_str(&symb, name) cdef Expression e e = PY_NEW(Expression) GEx_construct_symbol(&e._gobj, symb) e._parent = SR return e You need to include sage/libs/ginac/decl.pxi to get the declarations of GSymbol, GSymbol_construct_str, etc. Cheers, Burcin -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel-unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
[sage-devel] Re: InfinitePolynomialRing is -- very -- slow
Hi Martin! As you have pointed out in the wrong thread, having a smaller ring *has* advantages. But the more I think about it, the more I find it stupid that I let any element of an infinite polynomial "sparse" ring have its own underlying finite polynomial ring. It should be better to have the following model: * The infinite polynomial ring, R, has an underlying polynomial ring R._P, that may change during computations. It has to contain all variables that were created during computations, but not (much) more than that. So, if a generator x of R creates a new variable x[n], then R._P will be updated, and if a permutation acts on an element, R._P will be updated as well. * Any element, t, of R has an underlying polynomial, t._p. At the time when t is created, t._p belongs to R._P. * Later, the underlying ring of R may change. As soon as t is involved in an arithmetic operation, t._p well be updated so that it belongs to the new R._P. Probably that will always be better than the current sparse implementation, and (when doing overallocations) might even replace the dense implementation. Cheers, Simon -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel-unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
[sage-devel] Re: InfinitePolynomialRing is -- very -- slow
Hmm After thinking about it for a bit, is using var() really a good solution ? It is fast and everything, but I use my variables in functions that should not spoil the userspace with them ! When I define symbolic variables, they are global and could even be accessed in the userspace... Can this be avoided ? Nathann -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel-unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
[sage-devel] Re: InfinitePolynomialRing is -- very -- slow
Hi Robert! On Nov 26, 10:20 am, Robert Bradshaw wrote: [...] > With over-allocation one might not even need the dense/sparse > distinction--creating 1000 variables in a "sparse" manner would only > need 10 reallocations. (There could still be the question of how > expensive it is to do arithmetic between very old and very new > variables, without timing and looking at the actual code I'm not sure > if this is a concern.) I just remembered one important detail: In the sparse implementation, any element of an InfinitePolynomialRing has its own underlying polynomial ring. Continuing the example from my post above: sage: x[100].polynomial().parent() Univariate Polynomial Ring in x100 over Real Field with 53 bits of precision sage: x[1].polynomial().parent() Univariate Polynomial Ring in x1 over Real Field with 53 bits of precision sage: x[10].polynomial().parent() Univariate Polynomial Ring in x10 over Real Field with 53 bits of precision sage: (x[1]+x[10]).polynomial().parent() Multivariate Polynomial Ring in x10, x1 over Real Field with 53 bits of precision sage: x[5].polynomial().parent() Univariate Polynomial Ring in x5 over Real Field with 53 bits of precision sage: (x[5]+x[10]).polynomial().parent() Multivariate Polynomial Ring in x10, x5 over Real Field with 53 bits of precision This is why the sparse implementation is so slow. In the dense implementation, the InfinitePolynomialRing has an underlying ring by itself: sage: Y.polynomial_ring() Multivariate Polynomial Ring in b10, b9, b8, b7, b6, b5, b4, b3, b2, b1, b0, a10, a9, a8, a7, a6, a5, a4, a3, a2, a1, a0 over Real Field with 53 bits of precision Perhaps it would be better if the InfinitePolynomialRing had a *common* underlying ring also in the sparse implementation? In the sparse implementation that ring would just be slimmer than in the dense implementation? Provided that I find the time, I'll try to implement it. Thank you for pointing me to it! Cheers, Simon -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel-unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
Re: Re: [sage-devel] Re: InfinitePolynomialRing is -- very -- slow
Note that over allocating has a performance hit attached to it: sage: P = PolynomialRing(QQ,500,'x') sage: f = P.random_element() sage: R = PolynomialRing(QQ,1000,'x') sage: g = R(f) sage: %timeit f*f 10 loops, best of 3: 18.2 µs per loop sage: %timeit g*g 1 loops, best of 3: 32.3 µs per loop Also, it does increases the memory requirements for each and every element. Martin -- name: Martin Albrecht _pgp: http://pgp.mit.edu:11371/pks/lookup?op=get&search=0x8EF0DC99 _otr: 47F43D1A 5D68C36F 468BAEBA 640E8856 D7951CCF _www: http://www.informatik.uni-bremen.de/~malb _jab: martinralbre...@jabber.ccc.de -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel-unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
Re: [sage-devel] Re: InfinitePolynomialRing is -- very -- slow
On Nov 26, 2009, at 2:10 AM, Simon King wrote: > Hi Robert! > > On Nov 26, 9:46 am, Robert Bradshaw > wrote: > [...] I think this makes perfect sense...I'm actually surprised it's not implemented that way already. >> >>> That's impossible. >> >> Over-allocating the number of generators ahead of time whenever you >> need more to achieve O(log(n)) rather than O(n) ring enlargements for >> n used variables (where n is, of course, not know ahead of time) >> seems >> easy enough to me. > > Over-allocation could indeed be a good idea. > > By "impossible" I meant: When you have > sum([x[i] for i in range(1001)] > it is impossible to guess that eventually you will have 1000 variables > already at the time when you create x[0]. Yeah. I think this is just a stress test for how well the ring works with many dynamically created variables, not an actual application. > And when you create x[1000] first, then you have two approaches: > 1) I don't know whether any other variable will be used, thus, I only > create x[1000] and nothing else. That's the sparse implementation. > 2) If x[1000] is used, it is likely that x[999] will be used as well. > So, I create x[0],...,x[1000] at once. That's the dense > implementation. With over-allocation one might not even need the dense/sparse distinction--creating 1000 variables in a "sparse" manner would only need 10 reallocations. (There could still be the question of how expensive it is to do arithmetic between very old and very new variables, without timing and looking at the actual code I'm not sure if this is a concern.) - Robert -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel-unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
[sage-devel] Re: InfinitePolynomialRing is -- very -- slow
Hi Robert! On Nov 26, 9:46 am, Robert Bradshaw wrote: [...] > >> I think this makes perfect sense...I'm actually surprised it's not > >> implemented that way already. > > > That's impossible. > > Over-allocating the number of generators ahead of time whenever you > need more to achieve O(log(n)) rather than O(n) ring enlargements for > n used variables (where n is, of course, not know ahead of time) seems > easy enough to me. Over-allocation could indeed be a good idea. By "impossible" I meant: When you have sum([x[i] for i in range(1001)] it is impossible to guess that eventually you will have 1000 variables already at the time when you create x[0]. And when you create x[1000] first, then you have two approaches: 1) I don't know whether any other variable will be used, thus, I only create x[1000] and nothing else. That's the sparse implementation. 2) If x[1000] is used, it is likely that x[999] will be used as well. So, I create x[0],...,x[1000] at once. That's the dense implementation. [...] > > Or start summation with the highest index, which has the same effect. > > Or use *symbolic* variables right away, since this is what Nathann > > needed anyway. > > I'm clearly not following you--I thought the point was that one didn't > know ahead of time the highest index. Yes. InfinitePolynomialRing can not know the highest index. But if the user happens to know the highest index, (s)he can forward this information to InfinitePolynomialRing, by using the highest index first (in the default implementation). Once more: I think the crucial point is whether in a given application the number of variables can grow by arithmetic operations. For InfinitePolynomialRing, the action of an infinite symmetric group can obviously raise the variable index beyond all bounds. And this is what can happen during symmetric Groebner basis computation. If in Nathann's application there is no such group action (and no shift operator) then he might be better off using symbolic variables right away. Cheers, Simon -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel-unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
[sage-devel] Re: InfinitePolynomialRing is -- very -- slow
I do not know in advance the number of variables needed.
It can be pre-computed, of course (and it would be equivalent to
actually running the whole algorithm), but we are definitely better
without this hindrance... Actually, I tried several things using var
("x_"+str(i)) and it is much better in many aspects... I am planning
to write a patch for this as soon as ticket #7270 will be reviewed
( and I hope it will happen very soon anybody
available ? ;-) ).
For the moment, I told my colleagues to print p._x[5000] before their
computations which is some good enough temporary fix ;-)
I have another bug coming from the same InfinitePolynomial ring when
creating too many variables, but I haven't found the way to reproduce
it for the moment You'll have a ticket for this as soon as
possible !!
Thank you very much for your help !!!
Nathann
--
To post to this group, send an email to sage-devel@googlegroups.com
To unsubscribe from this group, send an email to
sage-devel-unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-devel
URL: http://www.sagemath.org
[sage-devel] Re: InfinitePolynomialRing is -- very -- slow
Hi Nathann! On Nov 26, 9:11 am, Nathann Cohen wrote: > Ok, now I understand... ;-) > > The trouble is that obviously, I have no idea of how many variables I > will need. I do no want to ask the user, as not having to say it is -- > really-- a relief ! I don't know exactly what you plan to do. I think the most important question is: Will the number of variables grow *during* your application, or is it possible to determine *in advance* the highest number of variables? In the latter case, ask the user for that number, and create a polynomial ring or a list of symbolic variables that is big enough. Best regards, Simon -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel-unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
[sage-devel] Re: InfinitePolynomialRing is -- very -- slow
Hi Florent! PS: On Nov 26, 9:24 am, Florent Hivert wrote: > On Thu, Nov 26, 2009 at 01:16:09AM -0800, Simon King wrote: > > > On Nov 26, 2009, at 12:35 AM, Florent Hivert wrote: > > [...] > > > I think this makes perfect sense...I'm actually surprised it's not > > > implemented that way already. > > > That's impossible. I understood "I'm surprised it's not implemented that way" as follows: "Why don't you always chose an underlying polynomial ring that is big enough, as in the example of summation?" And this is, as I had pointed out, impossible. Cheers, Simon -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel-unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
[sage-devel] Re: InfinitePolynomialRing is -- very -- slow
Hi Florent! On Nov 26, 9:24 am, Florent Hivert wrote: [...] > I don't understand why what you say here is an answer to the following > sentence of mine: > > Is there a problem in Symmetric Ideals if you have unused variables ? You will always have an infinity of unused variables, of course: In each actual computation, you will use only finitely many of them. And then the problem is, how to implement it? Since part of the Aschenbrenner-Hillar algorithm involves *classical* (finite) Groebner basis computation, it seemed reasonable to have finite polynomial rings as underlying structure, rather than symbolic variables. The underlying finite polynomial ring should of course contain all variables that are used. In the sparse implementation, the underlying ring will contain *only* the used variables. In the dense implementation, it will contain all variables that have at most the highest used index. Example: sage: X. = InfinitePolynomialRing(RR,implementation='sparse') sage: t=x[5] sage: t.polynomial().parent() Univariate Polynomial Ring in x5 over Real Field with 53 bits of precision sage: Y. = InfinitePolynomialRing(RR) sage: s=a[5] sage: s.polynomial().parent() Multivariate Polynomial Ring in b5, b4, b3, b2, b1, b0, a5, a4, a3, a2, a1, a0 over Real Field with 53 bits of precision But when you start doing arithmetic, the underlying ring will, in general, change. And this is also the case when you let the symmetric group over the natural numbers act on the ring: sage: p=Permutation((5,10)) sage: (t^p).polynomial().parent() Multivariate Polynomial Ring in x10, x5 over Real Field with 53 bits of precision sage: (s^p).polynomial().parent() Multivariate Polynomial Ring in b10, b9, b8, b7, b6, b5, b4, b3, b2, b1, b0, a10, a9, a8, a7, a6, a5, a4, a3, a2, a1, a0 over Real Field with 53 bits of precision You see why the sparse implementation is called "sparse". __Consequences:__ - The sparse implementation has the disadvantage that, on average, you will more often change the underlying finite polynomial ring. That slows it down. - The dense implementation in some applications has the disadvantage that the underlying ring is too big. Does this answer your question? Cheers, Simon -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel-unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
Re: [sage-devel] Re: InfinitePolynomialRing is -- very -- slow
On Nov 26, 2009, at 1:16 AM, Simon King wrote: > Hi Robert! > > On Nov 26, 8:43 am, Robert Bradshaw > wrote: >> On Nov 26, 2009, at 12:35 AM, Florent Hivert wrote: >>> Though this could be improved by using a similar trick than >>> doubling the size of a list when appending element, I'm not sure >>> that's what we want. >> >> I think this makes perfect sense...I'm actually surprised it's not >> implemented that way already. > > That's impossible. Over-allocating the number of generators ahead of time whenever you need more to achieve O(log(n)) rather than O(n) ring enlargements for n used variables (where n is, of course, not know ahead of time) seems easy enough to me. > The whole point of InfinitePolynomialRing is that you do *not* know in > advance how many variables you will eventually need. Its main purpose > is to compute Groebner bases of so-called Symmetric Ideals, and during > such computation it may very well be that the number of variables > increases during computation. > > And then, as I mentioned in my previous post, there is the problem > that in some cases you will use only very few variables, although the > indices may be very large and, again, you don't know in advance *what* > indices you will need. This is why there is a non-default sparse > implementation. > >>> In the mean time. I have the following workaround: Just start by >>> declaring your last variable: > > Or start summation with the highest index, which has the same effect. > Or use *symbolic* variables right away, since this is what Nathann > needed anyway. I'm clearly not following you--I thought the point was that one didn't know ahead of time the highest index. - Robert -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel-unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
[sage-devel] Re: InfinitePolynomialRing is -- very -- slow
Hi David! On Nov 26, 9:07 am, David Kohel wrote: > Rather I would say that "sparse" should be the default: > > P. = InfinitePolynomialRing(QQ, implementation="sparse") No. The main purpose of InfinitePolynomialRing is the computation of symmetric Groebner bases, and simply it turned out in examples that "sparse" is much slower in Groebner basis computations. > Moreover, this syntax (and for gens, etc.) is inconsistent > with PolynomialRing. Why? One possible way of creating a polynomial ring is sage: R.=PolynomialRing(QQ) So, my syntax is perfectly consistent. > The syntax: > > PolynomialRing(ring, integer, sparse=True) > > would be a more coherent, where integer=Set(ZZ) would give > an infinite polynomial ring. Mathematically, let G be the symmetric group of the natural numbers. Then, PolynomialRing(QQ,x) is the free QQ(G) module with generator x. And, by work of Aschenbrenner and Hillar, it is actually noetherian as a QQ(G) module. And this implies at least three reasons why I don't like your suggestion. 1) An InfinitePolynomialRing is not just a polynomial ring with infinitely many variables. This is a point against using the PolynomialRing constructor for its creation. 2) The variables x[0],x[1],x[2],x[3],... are *not* considered the generators of an infinite polynomial ring. You would have just *one* generator x, and this one generator gives rise to an infinity of variables. So, it simply makes not much sense to define an infinite polynomial ring by an (infinite) list of variables. Again, my syntax is consistent, since InfinitePolynomialRing(QQ,'x') lists the *generators* of the object. 3) Sometimes one wants to have *several* generators of an infinite polynomial ring, and one wants to chose a *name* for the generator. Your suggestion does not address any of these points. Cheers, Simon -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel-unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
Re: [sage-devel] Re: InfinitePolynomialRing is -- very -- slow
Hi Simon, On Thu, Nov 26, 2009 at 01:16:09AM -0800, Simon King wrote: > > On Nov 26, 2009, at 12:35 AM, Florent Hivert wrote: > [...] > > I think this makes perfect sense...I'm actually surprised it's not > > implemented that way already. > > That's impossible. > > The whole point of InfinitePolynomialRing is that you do *not* know in > advance how many variables you will eventually need. Its main purpose > is to compute Groebner bases of so-called Symmetric Ideals, and during > such computation it may very well be that the number of variables > increases during computation. > > And then, as I mentioned in my previous post, there is the problem > that in some cases you will use only very few variables, although the > indices may be very large and, again, you don't know in advance *what* > indices you will need. This is why there is a non-default sparse > implementation. I don't understand why what you say here is an answer to the following sentence of mine: Is there a problem in Symmetric Ideals if you have unused variables ? > > > Though this could be improved by using a similar trick than doubling the > > > size of a list when appending element, I'm not sure that's what we want. > > > > I think this makes perfect sense...I'm actually surprised it's not > > implemented that way already. > > That's impossible. > Running to get my train... Cheers, Florent -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel-unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
[sage-devel] Re: InfinitePolynomialRing is -- very -- slow
Hi Robert! On Nov 26, 8:43 am, Robert Bradshaw wrote: > On Nov 26, 2009, at 12:35 AM, Florent Hivert wrote: [...] > I think this makes perfect sense...I'm actually surprised it's not > implemented that way already. That's impossible. The whole point of InfinitePolynomialRing is that you do *not* know in advance how many variables you will eventually need. Its main purpose is to compute Groebner bases of so-called Symmetric Ideals, and during such computation it may very well be that the number of variables increases during computation. And then, as I mentioned in my previous post, there is the problem that in some cases you will use only very few variables, although the indices may be very large and, again, you don't know in advance *what* indices you will need. This is why there is a non-default sparse implementation. > > In the mean time. I have the following workaround: Just start by > > declaring your last variable: Or start summation with the highest index, which has the same effect. Or use *symbolic* variables right away, since this is what Nathann needed anyway. > If one knows how many variables one needs ahead of time, than what's > the advantage of using the InfinitePolynomialRing over a finite one of > the right size? Sure. *If* one knows it and *if* the number of variables does not increase during computation then a usual polynomial ring is better. Cheers, Simon -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel-unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
[sage-devel] Re: InfinitePolynomialRing is -- very -- slow
Ok, now I understand... ;-) The trouble is that obviously, I have no idea of how many variables I will need. I do no want to ask the user, as not having to say it is -- really-- a relief ! My other problem is that sometimes computation on symbolic variables take a lot of time, and I think it comes from the fact that they are "so" general. Do you think it could be interesting to create a "custom" variable, just for linear functions ( and perhaps only for this application ) ? Do you think this could be a way to speed it up ? Thanks Nathann On Nov 26, 10:07 am, David Kohel wrote: > Rather I would say that "sparse" should be the default: > > P. = InfinitePolynomialRing(QQ, implementation="sparse") > > Moreover, this syntax (and for gens, etc.) is inconsistent > with PolynomialRing. The syntax: > > PolynomialRing(ring, integer, sparse=True) > > would be a more coherent, where integer=Set(ZZ) would give > an infinite polynomial ring. > > --David > > On Nov 26, 9:43 am, Robert Bradshaw > wrote: > > > On Nov 26, 2009, at 12:35 AM, Florent Hivert wrote: > > > > Hi Nathann, > > > >> For Linear Programming, I need to create plenty of symbolic variables > > >> which I use to represent linear functions To do it, I use the > > >> class InfinitePolynomialRing which lets me create them easily ( and > > >> it > > >> is really needed, as my colleagues often have to create Linear > > >> Programs using 1000~2000 variables. This is not a problem for the > > >> solvers, but Sage does not like it : > > >> To understand my problem, just try this code : > > > >> X. = InfinitePolynomialRing(RR) > > >> sum([x[i] for i in range(200)]) > > > >> Don't you think it is a bit long just to generate a sum ? I have to > > >> admit I do not know how this class is coded, and the slowness may be > > >> required for applications different from mine.. But wouldn't there be > > >> a way to speed this up ? If not, do you know of any way to generate > > >> many symbolic variables ( they do not need to be polynomial, just > > >> linear in my case ) ? > > > > This is indeed a problem. I think I know the cause... Each time a > > > new variable > > > is created, the ring itself is somehow changed. Therefore for each new > > > variable in your sum, there is a big computation which convert the > > > former sum > > > to the new ring. Though this could be improved by using a similar > > > trick than > > > doubling the size of a list when appending element, I'm not sure > > > that's what > > > we want. > > > I think this makes perfect sense...I'm actually surprised it's not > > implemented that way already. > > > > In the mean time. I have the following workaround: Just start by > > > declaring your last variable: > > > If one knows how many variables one needs ahead of time, than what's > > the advantage of using the InfinitePolynomialRing over a finite one of > > the right size? > > > - Robert -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel-unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
[sage-devel] Re: InfinitePolynomialRing is -- very -- slow
Rather I would say that "sparse" should be the default: P. = InfinitePolynomialRing(QQ, implementation="sparse") Moreover, this syntax (and for gens, etc.) is inconsistent with PolynomialRing. The syntax: PolynomialRing(ring, integer, sparse=True) would be a more coherent, where integer=Set(ZZ) would give an infinite polynomial ring. --David On Nov 26, 9:43 am, Robert Bradshaw wrote: > On Nov 26, 2009, at 12:35 AM, Florent Hivert wrote: > > > > > Hi Nathann, > > >> For Linear Programming, I need to create plenty of symbolic variables > >> which I use to represent linear functions To do it, I use the > >> class InfinitePolynomialRing which lets me create them easily ( and > >> it > >> is really needed, as my colleagues often have to create Linear > >> Programs using 1000~2000 variables. This is not a problem for the > >> solvers, but Sage does not like it : > >> To understand my problem, just try this code : > > >> X. = InfinitePolynomialRing(RR) > >> sum([x[i] for i in range(200)]) > > >> Don't you think it is a bit long just to generate a sum ? I have to > >> admit I do not know how this class is coded, and the slowness may be > >> required for applications different from mine.. But wouldn't there be > >> a way to speed this up ? If not, do you know of any way to generate > >> many symbolic variables ( they do not need to be polynomial, just > >> linear in my case ) ? > > > This is indeed a problem. I think I know the cause... Each time a > > new variable > > is created, the ring itself is somehow changed. Therefore for each new > > variable in your sum, there is a big computation which convert the > > former sum > > to the new ring. Though this could be improved by using a similar > > trick than > > doubling the size of a list when appending element, I'm not sure > > that's what > > we want. > > I think this makes perfect sense...I'm actually surprised it's not > implemented that way already. > > > In the mean time. I have the following workaround: Just start by > > declaring your last variable: > > If one knows how many variables one needs ahead of time, than what's > the advantage of using the InfinitePolynomialRing over a finite one of > the right size? > > - Robert -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel-unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
[sage-devel] Re: InfinitePolynomialRing is -- very -- slow
Hi Nathann!
On Nov 26, 8:18 am, Nathann Cohen wrote:
[...]
> To understand my problem, just try this code :
>
> X. = InfinitePolynomialRing(RR)
> sum([x[i] for i in range(200)])
>
> Don't you think it is a bit long just to generate a sum ? I have to
> admit I do not know how this class is coded, and the slowness may be
> required for applications different from mine.. But wouldn't there be
> a way to speed this up ?
InfinitePolynomialRing has an underlying *finite* polynomial ring,
that changes whenever you need a variable that is not in the finite
ring.
Therefore,
sum([x[199-i] for i in range(200)])
is much faster.
Reason:
InfinitePolynomialRing has a dense and a sparse implementation, that
both have advantages and disadvantages. The default is "dense". It
means: If x[199] is called, then a polynomial ring with all variables
ranging from x0 to x199 is created. So, if you start the sum with x
[199] then the ring can be kept.
In the sparse implementation, both summation orders would be slow. The
advantage of the sparse implementation is that you can have x[10]
without creating a ring with 10 generators.
> If not, do you know of any way to generate
> many symbolic variables ( they do not need to be polynomial, just
> linear in my case ) ?
Well, you know that InfinitePolynomialRing does not yield symbolic
variables.
I would consider creating the variable names that you need, and create
symbolic variables explicitely:
sum([var('x'+str(i)) for i in range(200)])
is fast enough, I guess.
Cheers,
Simon
--
To post to this group, send an email to sage-devel@googlegroups.com
To unsubscribe from this group, send an email to
sage-devel-unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-devel
URL: http://www.sagemath.org
