2014/01/26 by Andrew Arnold, Arnold, Andrew, Daniel S. Roche +1 · 1 citation
Computer Science · Engineering · #68W30 #Advanced Numerical Analysis Techniques #Data Structures and Algorithms (cs.DS) #F.2.1 #FOS: Computer and information sciences #G.4 #Handwritten Text Recognition Techniques #I.1.2 #Mathematical Software (cs.MS) #Natural Language Processing Techniques #Polynomial and algebraic computation #Symbolic Computation (cs.SC)
paper · pdf · doi:10.48550/arxiv.1401.6694
openalex publication_date 2014/01/26 · openalex created_date 2022/10/01 · openalex updated_date 2026/07/28
We present new techniques for reducing a multivariate sparse polynomial to a\nunivariate polynomial. The reduction works similarly to the classical and\nwidely-used Kronecker substitution, except that we choose the degrees randomly\nbased on the number of nonzero terms in the multivariate polynomial, that is,\nits sparsity. The resulting univariate polynomial often has a significantly\nlower degree than the Kronecker substitution polynomial, at the expense of a\nsmall number of term collisions. As an application, we give a new algorithm for\nmultivariate interpolation which uses these new techniques along with any\nexisting univariate interpolation algorithm.\n