#7580: bugs in infinite polynomial ring
-----------------------+----------------------------------------------------
Reporter: was | Owner: SimonKing
Type: defect | Status: new
Priority: major | Milestone: sage-4.3
Component: algebra | Keywords:
Work_issues: | Author:
Upstream: N/A | Reviewer:
Merged: |
-----------------------+----------------------------------------------------
Comment(by SimonKing):
Here some words on the requirement that variable names must be single
letters.
The generators x,y,... of an Infinite Polynomial Ring R are,
mathematically, generators of R as a free module over the group algebra of
the symmetric group G of the natural numbers (starting with 1, while 0 is
fixed).
A variable in R can be thought of as a pair (x,n), where x is a generator
of R and n is a natural number. G acts on the pair by acting on n. In a
text book, one would write it x_n. In the implementation, such variable
x_n is returned by x[n]. We refer to n as the "index" of x[n].
It has an underlying "classical" polynomial x[n]._p. The question is: To
what classical polynomial ring should x[n]._p belong?
* The dense implementation (due to Mike Hansen) is: x[n]._p belongs to
the ring with variables x0,x1,...,x{n},y0,y1,...,y{n}.
* The sparse implementation (my starting point) is: x[n]._p belongs to
the ring with variable x{n}.
Of course, when doing algebraic operations in the sparse implementation,
the underlying polynomial ring must be extended. In the dense
implementation, this is only needed when G acts, or if one does a
conversion, say, of a string 'x10000+2*y100001' into R.
But that's the point: How can I find the maximal index of Infinite
Polynomials when doing arithmetic, G-action or conversion? Note that by
arithmetic operations the terms of maximal index may cancel, so, it is not
easily possible to infer the maximal index of a sum, given the maximal
indices of a summand. And how should one find out the maximal index in a
given string?
I thought that an easy solution is to infer the maximal index from a
string representation of the underlying classical polynomial q._p, if q is
an Infinite Polynomial. This is one place where regular expressions occur.
In order to simplify the regular expressions, generator names should be as
simple as possible.
There is another point. I wanted to implement Aschenbrenner's and Hillar's
algorithm for finding Symmetric Groebner Bases. This requires a monomial
ordering on R. Of course, I am using monomial orderings of the underlying
classical polynomial rings.
But this means: If I construct the parent of q._p (again, q an Infinite
Polynomial) then I must order the occurring variables. Usually, the
variable names have to be sorted, first, by the name of the generator and,
secondly, by the index. Again, I sought to do this operation as quick and
easy as possible.
And these are the reasons why I imposed the name restriction:
1. The name of the variable name should allow (for a human) to infer the
name of the generator and the index. So, it should be something like
var_name = str(generator_name)+str(index) or var_name =
str(generator_name)+'_'+str(index).
2. For the computer, it should be easy and ''fast'' to determine generator
name and index from the variable name. This is why I ask to have a single
letter for the generator name, so that one has {{{generator_name, index =
var_name[0], int(var_name[1:]}}}.
But what about just requiring that generator_name must not contain "_".
Then, one could say var_name = str(generator_name)+'_'+str(index), and
process var_name by {{{split('_')}}}. How much slower would this be?
Apparently 50%:
{{{
sage: f = lambda x,y: (x,int(y))
sage: s = 'x_1234'
sage: timeit("a,b = f(*s.split('_',1))")
625 loops, best of 3: 1.73 µs per loop
sage: timeit("a,b = s[0],int(s[2:])")
625 loops, best of 3: 1.11 µs per loop
}}}
Actually the approach using "_" has one benefit: Suppose one is given the
string representation of the underlying polynomial and wants to determine
the maximal index. This can be found using a simple regular expression,
since a sequence of digits defines an index if and only if it is preceded
by "_". Thus:
{{{
sage: import re
sage: P = re.compile('_[0123456789]+') # this will be done only once
sage: s = '1000000*alpha_1234*beta_4321^1223923923+gamma_234*delta_1'
sage: max([int(x[1:]) for x in P.findall(s)])
4321
}}}
So, in the end of the day, using "_" could be faster.
Would it be OK to say "generator names must be alphanumeric and must not
contain underscore"?
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/7580#comment:2>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
