On 14.07.23 16:48, Waldek Hebisch wrote:
In my developement version I switched polynomial factorization
over prime fields to use new factorizer. That gives substantial
speedup. However, profiling showed that in my test case (which
was polynomial with 84 linear factors) abut 10% time was spent
in multiplying factors, of of which 8.4% went into comparing
exponents (POLYCAT-;smaller?)
Just a side remark.
Isn't the implementation of POLYCAT-;smaller? a bit weird if it is used
in factorization? It basically, compares the leading coefficients.
So we have...
(1) -> S := SMP(Integer, Symbol)
(31) -> px := x::S
(31) x
Type: SparseMultivariatePolynomial(Integer,Symbol)
(32) -> py := y::S
(32) y
Type: SparseMultivariatePolynomial(Integer,Symbol)
(33) -> smaller?(-py^100,px)
(33) true
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.
Sorry, I haven't looked into the factorization code to check why such a
linear order makes sense. In fact, I wonder why the factorizer uses the
linear order by smaller? at all. Doesn´t Comparable say that it is just
an arbitrary but total order. I wouldn´t be surprised if I override
smaller? in SMP by some other crazy order that the factorization might
go wrong. Wild speculation without looking at the code, of course, but I
understood that it makes sense to introduce Comparable for a printing
order, but I am not sure about it's usefulness in other algorithms, that
want a few more properties than just totality in order to get some
complexity measure.
It is not entirely clear to me what to do with Factored.
Ordering can be used to speed up computations only when
we have true order, otherwise we may get wrong results.
In what sense does the order influence correctness?
Additionally, ordering factors gives speedup only when
all or most factors is prime, for other factors we need
to use quadratic method anyway. My conclusion is that
we can not have really efficient operations with
generality offered by Factored, so probably should
not care too much about speed of Factored.
Oh, do you mean the sx := sort!(LispLessP, x) in makeFR $ Factored(R) ?
Why should one care about the order in the representation of Factored?
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 view this discussion on the web visit
https://groups.google.com/d/msgid/fricas-devel/490205dc-0c86-fd60-799b-3c3572c1e411%40hemmecke.org.
