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 doing classical (not considering optimization like Karatsuba)
multiplication, there is fixed number of coefficient multiplication:
sp*sq.
The problem we discussed in previous threads is about data structure
-- storage consumption of those potentially temporary sp*sq monomials,
and time consumption of traverse those storage.
Our current algorithm, in best case: when sp = dp, sq = dq,
space complexity is sp+sq, time complexity is sq*(sp+sq).
In worst case, dp>>sp, dq>>sq, space complexity is sp*sq,
time complexity is sq*sp*sq.
My proposed sparse algorithm, best/worst/average space complexity is
sp*sq, time complexity is sp*sq*log(sq).
My proposed dense algorithm, best/worst/average space complexity is
dp+dq, time complexity (spent on data structure) is sp*sq.
So the distinguish could be: when (dp+dq) < sp*sq*Const, use
dense representation, otherwise use sparse representation.
The Const can be determined by benchmark. But IIUC, it should be
at least 4 -- The sparse representation need to store coefficient,
exponent, a cell to cons them together, another cell to store pointer
to next monomial, while the dense representation only need to store
coefficient.
- Qian
On 10/2/22 21:09, Kurt Pagani wrote:
On 02.10.2022 12:37, Qian Yun wrote:
On 10/2/22 13:18, Qian Yun wrote:
So first conclusion is to optimize for small inputs. There's not much
room for it, I think.
For bigger inputs, I think current implementation is bad both ways:
a) For sparse cases, simply chain the MxN terms together, sort and
dedupe is O(N^2*log(N)) better than current O(N^3).
b) For dense cases, using actual dense representation like array
should be a great improvement over current implementation:
we only need a (slightly larger than) (M+N) length array to store
the temp result.
No need to create an array to store temp result, we only need to
create array for input (p, q) and the coefficient of (p * q) can
be computed directly, for example:
https://github.com/sympy/sympy/blob/sympy-1.11.1/sympy/polys/densearith.py#L735
I think this will be valid optimization for small (but dense)
inputs as well. Will need data to determine when to use this
method -- what qualifies a polynomial as "dense"?
For example, max degree - min degree < 2 * number of monomials ?
A good question. I've never seen a satisfactory definition. While some
think of
(https://math.berkeley.edu/~bernd/cbms.pdf)
"""
Here and throughout this book, a polynomial is called sparse if we know
a priori which monomials appear with non-zero coefficients in that
polynomial.
"""
it may well make sense to distinguish sparse/dense:
What Can (and Can’t) we Do with Sparse Polynomials?
https://arxiv.org/pdf/1807.08289.pdf
https://www.usna.edu/Users/cs/roche/research/phd/
- Qian
--
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/4beb49c6-9b15-fb1d-90b5-778f787a24c0%40gmail.com.
