On Fri, Jul 14, 2023 at 10:43:51PM +0200, Ralf Hemmecke wrote:
> > > Certainly not a problem for the definition of smaller?, as it just
> > > wants a linear order, but for factorization I would have expected
> > > that a polynomial with a smaller degree counts as smaller.
> >
> > Well, SparseMultivariatePolynomial uses lexicographic order.No. That is
> > not true.S := SMP(Integer, Symbol);px := x::S;py := y::S;
> smaller?(-py^100,px) -- returns true
> smaller?( py^100,px) -- returns false
>
> For Gröbner bases lex order just works on the exponent vectors and
> doesn't care about the coefficient ring at all.
Well, I would say that for Groebner bases order _is_ on exponent
vectors. But given order in base ring and order on exponents,
we have unique extention to polynomials satisfying axioms of
ordered ring such that monomial with coefficient 1 are ordered
via exponents.
> Certainly not a total
> order suitable for Comparable. A simpler probably cheaper total order
> for SMP would be to just compare degree in the main variable and only if
> that is equal apply smaller? to the leading coefficient (a polynomial in
> one variable less). That also ends with calling smaller?(r1,r2) on the
> base ring R, but most probably recusion is not so deep because the
> polynomials differ in degree in the main variable.
Well, for ordered sets currently Comparable gives the same order
as order from OrderedSet. Not stricly necessary, but simplifies
things because we can reuse implementations.
Concerning order in SparseMultivariatePolynomial, both 'degree' and
'leadingCoefficient' are expensive, but 'degree' is more expensice.
Namely, 'degree' produces list of pairs (symbol, exponent) (element of
IndexedExponents). To do this 'degree' must recurse. Similar
recursion is used for 'leadingCoefficient', but 'leadingCoefficient'
can just return its result. 'degree' must create appropriate
data structure. AFAICS there are several small and moderate
inefficiences in 'smaller?' that together lead to slowness.
> > Current answer to your wish for degree order is "use domain with degree
> > order like HomogeneousDistributedMultivariatePolynomial".
>
> No, no. I never wished for something. Just my expectations were not met.
>
> > I must say that I am not fully satisfied with this answer, but
> > lexicographic order as _default_ order for SparseMultivariatePolynomial
> > makes a lot of sense.
>
> Yes, of course. But what order are you talking about, the one given by
> smaller? is maybe lexicographic, but not in the sense it is usually used
> in Gröbner bases theory. POLYCAT-;smaller? implement an order that works
> by virtually introducing 0-coefficients in order to bring both
> polynomials to the same degree. Possible, but I have the feeling that it
> is costly.
That is just _one_ of several small things slowing 'smaller?'.
> > Including coefficients is necessary to have ordered ring. Note that
> > over fields our univariate factors are monic. Over integers we
> > normalize factors so that leading coefficient is positive. So in
> > both cases bigger degree will win.
>
> I don't check now, but on this subset both implementations might give the
> same result, but I still claim that the one that only recurses if the
> degrees in the main variable are equal has less work to do.
You missed significant part: 'smaller?' is in PolynomialCategory,
it only sees degree as element of IndexedExponents. In particular
'smaller?' has no idea that there is main variable. It works
essentially the same if you give it
HomogeneousDistributedMultivariatePolynomial. 'smaller?' simply
calls 'degree' to get representation of exponent vector, than
calls comparison functions to compare exponents. Then calls
'leadingCoefficient' to extract leading coefficient. Main cost
is due to genrality: all those things have to be SPADCALL-s.
Due to SPADCALL-s real work is probably less than overhead of
dispatch.
Specialized version for SparseMultivariatePolynomial could be
much faster, it still would have do work to extract leading
coefficient, but could do this in a loop using inlinable code
instead of recursion via SPADCALL-s.
--
Waldek Hebisch
--
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 view this discussion on the web visit
https://groups.google.com/d/msgid/fricas-devel/ZLHMx5rVW0s4ekg1%40fricas.math.uni.wroc.pl.
