Sparse Multiplication of Multivariate Linear Differential Operators
Mark W. Giesbrecht, Qiao-Long Huang, Éric Schost · 2021
We propose a randomized algorithm for multiplication in the ring of non-commutative polynomials Κ [x1,…,xn]{#948;1,…,δn}, where δ i=xi∂over∂ xi, dedicated to sparse inputs. The complexity of our algorithm is polynomial in the input size and on an a priori sparsity bound for the output.