I have an idea for sparse/dense distinguish in the context of
multiplication:
For polynomial p and q, define:
sp := numberOfMonomials p -- number of cells of sparse rep
sq := numberOfMonomials q
dp := degree p - minimumDegree p + 1 -- length of dense rep
dq := degree q - minimumDegree q + 1
When
On Sun, Oct 02, 2022 at 01:18:32PM +0800, Qian Yun wrote:
> I'm talking about multiplication in SparseUnivariatePolynomial,
> it is implemented in Domain PolynomialRing, the relevant part starts
> at line 431 of poly.spad. (aka the 'addm!' local function.)
>
> First, this function has complexity
Correction for the Maxima case:
I used expression instead of polynomial in my previous version.
The following version is corrected. (Using "rat" is the key.)
The conclusion also changes: the Maxima implementation is O(n^2)
when polys are dense and O(n^3) when polys are sparse.
Similar to current
