On 02/15/2017 03:35 AM, Waldek Hebisch wrote:
>> I basically remove VarSet and thus the (assumed) structure of
>> Expon.
>
> To be more precise: the test should work as before if there is
> 'totalDegree' function. All you do is to allow more domains, some of
> them may miss 'totalDegree'. In principle current code allows this,
> but currently PolynomialCategory is asserted to have 'totalDegree',
> while in general this is not true.
I don't understand the part with "may miss 'totalDegree'".
And what test do you actually mean? I don't change PolynomialCategory,
so totalDegree will be there (unconditionally).
But after changing GroebnerPackage and GroebnerInternalPackage to also
allow domains of a more general category, it is no longer clear whether
Dpol comes with totalDegree or not. Since Gröbner basis computations
depends on totalDegree only for enabling virtualDegree, i.e., for
selecting the "sugar strategy", an optional totalDegree does not hurt
the final result in the Gröbner basis computation, but only in the
strategy (selecting S-polynomials) of how to compute it. As a user
always may pass a Dpol that exports totalDegree, it's completely up to
the user to do it correctly. GroebnerInternalPackage allows this by
implementing
if Dpol has totalDegree : Dpol -> NonNegativeInteger then
virtualDegree p == totalDegree p
else
virtualDegree p == 0
(which according to Dpol: PolynomialCategory(Dom, Expon, VarSet) never
hit the else branch).
So generalising GroebnerInternalPackage is a true extension.
> So one question is why do you want to generalize Groebner. Do you
> just want to get rid of need to pass VarSet?
Exactly. I have constructed domains that do not have variable names and
I don't see a good reason to introduce them if it is soo easy to
generalise the GroebnerPackage. Buchberger's algorithm relies on an
order of the terms and lcm, multiplication, and division on terms, but
not on the existence of variables.
> If yes, code should work as before.
Why do you think, it doesn't? As I argued above, I don't see a reason
why my patch breaks existing behaviour.
> Do you want to compute Groebner bases for non-polynomial domains?
Currently, my domains basically look polynomial. The only difference is
that I don't have variable names. As I said in my previous mail, if you
don't like totalDegree as an export of FreeModuleCategory, because it
makes (mathematically) no sense, then I accept that.
Still, I want PolynomialRing(R,E) to (conditionally) export totalDegree
if E is "well-behaved", so that I can use PolynomialRing(R,E) in a
Gröbner computation and I am sure that the "sugar strategy" is applied.
I think, it is a burden for a user (and in theory for Buchberger's
algorithm unnecessary) to convert PolynomialRing(R,E) to some
appropriate existing multivariat polynomial domain in FriCAS and
"invent" random variable names that are thrown away after the computation.
The only thing, I am not sure about is, what exactly "well-behaved"
should mean. I currently have
coerce: % -> Vector NNI
but it could also be
grade: % -> NNI
or maybe something more appropriate. I have chosen the first, because
this already is in DirectProduct and SplitHomogeneousDirectProduct.
So whatever condition will become "well-behaved", these DirectProduct
domains should export it.
> To some degree yes. Actually, AFAICS for efficient computation of
> Groebner basese we need some notion of size which interacts in
> predictable way with ordering. It seems that total degree is fulfils
> this role (at least it works well for sugar strategy).
Right. The emphasis here is "efficient". The sugar strategy actually is
a way to compute with non-homogeneous polynomials so that the selection
of S-polynomials work as if the polynomials had been homogenised before
the computation. But all this refers to the selection of S-polynomials
during Buchberger's algorithm, it does not have any influence on the
final Gröbner basis, since this is (at least the reduced one) unique and
does not depend on the way to compute it. It's only that the "sugar
strategy" is believed to be one of the more "efficient" strategies.
There are other strategies. slimgb comes to my mind where the
S-polynomial selection depends on the size of the (leading) coefficient(s).
> I admit that ATM I do not know what is the best way. Current code
> considers ordering, degree, etc to be part of type. This is
> consistent with Axiom philosophy. OTOH one can think about having
> some base type and ordering, degree. etc being external structure.
> Natural realization of this idea is to have additional functional
> parameters giving the extra operations. Or extra package parameter.
>
> Specifically, IIUC for current Groebner code we assume ability to
> compute leading exponent. 'totalDegree' is just kind of norm on
> leading exponent. So one solution may be to have some restriction on
> exponents requestion norm for them.
>
>> Anyway, because of the sugar strategy I want totalDegree in
>> PolynomialRing under the condition that my exponent domain is
>> well-behaved, i.e., for example exports
>>
>> coerce: E -> Vector NNI
>>
>> In fact, I would also be happy if E exports a function (not sure
>> about a reasonable name, so I use "grade" here)
>>
>> grade: E -> NNI
>
> 'grade' could be defined in noncommutative case, coercion to Vector
> NNI essentially implies commutativity. Also, for Groebner it is
> enough if 'grade' is subadditive (I am not sure how well sugar
> strategy would work), while coercion makes sense only if it is
> additive.
>
>> and then define totalDegree in PolynomialRing as
>>
>> totalDegree(p) == grade degree p
>>
>
> Here I would expect additve 'grade'.
Oh, of course, we could generalize GroebnerPackage to also work for
non-commutative polynomials. But that would be a major task. There are a
number of things to add to make Buchberger's algorithm work for the
non-commutative situation. Would be nice to have this, but that's
somewhat orthogonal to my generalisation.
I am satisfied with commutative terms that do not require variable names.
I'll try to clean up my patches and will suggest something soon. As I
said no need to delay the release for it.
Ralf
--
You received this message because you are subscribed to the Google Groups
"FriCAS - computer algebra system" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to fricas-devel+unsubscr...@googlegroups.com.
To post to this group, send email to fricas-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/fricas-devel.
For more options, visit https://groups.google.com/d/optout.
