On 15.07.23 00:31, Waldek Hebisch wrote:
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.
Hmmmm.... maybe I misinterpret something...
https://github.com/fricas/fricas/blob/master/src/algebra/polycat.spad#L647
This smaller? calls degree and degree is implemented in SMP.
The representation is recursive.
https://github.com/fricas/fricas/blob/master/src/algebra/multpoly.spad#L108
Now I would have expected the following. (Sorry this is without having
yet studied the implementation of SMP.)
Suppose I have two real polynomial not just elements of R, then they are
univariate polynomials in the main variable.
So the polynomial with the smaller main variable counts as smaller.
If they have the same main variable then check the degree in this
variable. And if the degrees are equal, recurse to the leading coefficient.
But hey, I see
https://github.com/fricas/fricas/blob/master/src/algebra/multpoly.spad#L647
degree p ==
p case R => 0
degree(leadingCoefficient(p.ts)) + monomial(degree(p.ts), p.v)
Oh, no! That computes the degree over all variables. It basically treat
the polynomial like in a distributed fashion. Sorry, I have not
recognized this before.
For an implementation of the smaller? from Compare in SMP, I would
definitely use the univariate recursive structure, i.e. consider the
degree function from D and eventually break ties with smaller? from R.
https://github.com/fricas/fricas/blob/master/src/algebra/multpoly.spad#L108C1-L108C1
D := SparseUnivariatePolynomial(%)
VPoly := Record(v : VarSet, ts : D)
Rep := Union(R, VPoly)
Certainly my previous mail must have been confusing. I was thinking of a
exactly this univariate degree function for smaller?.
And certainly that smaller? function must be implemented in SMP itself,
because it makes use of the particular representation.
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 [email protected].
To view this discussion on the web visit
https://groups.google.com/d/msgid/fricas-devel/bd96a1df-a1a5-bebd-a60f-81b49a28965c%40hemmecke.org.
