Daniel S. Roche
ABSTRACT
Simply put, a sparse polynomial is one whose zero coefficients are not explicitly stored. Such objects are ubiquitous in exact computing, and so naturally we would like to have efficient algorithms to handle them. However, with this compact storage comes new algorithmic challenges, as fast algorithms for dense polynomials may no longer be efficient. In this tutorial we examine the state of the art for sparse polynomial algorithms in three areas: arithmetic, interpolation, and factorization. The aim is to highlight recent progress both in theory and in practice, as well as opportunities for future work.
Supplemental Material
- F. Amoroso and M. Sombra. Factorization of bivariate sparse polynomials. online, 2017. URL https://arxiv.org/abs/1710.11479.Google Scholar
- A. Arnold. Sparse Polynomial Interpolation and Testing. PhD thesis, University of Waterloo, 2016. URL http://hdl.handle.net/10012/10307.Google Scholar
- A. Arnold and E. L. Kaltofen. Error-correcting sparse interpolation in the chebyshev basis. ISSAC '15, pages 21--28. ACM, 2015. Google ScholarDigital Library
- A. Arnold and D. S. Roche. Multivariate sparse interpolation using randomized Kronecker substitutions. ISSAC '14, pages 35--42. ACM, 2014. Google ScholarDigital Library
- A. Arnold and D. S. Roche. Output-sensitive algorithms for sumset and sparse polynomial multiplication. ISSAC '15, pages 29--36. ACM, 2015. Google ScholarDigital Library
- A. Arnold, M. Giesbrecht, and D. S. Roche. Faster sparse interpolation of straight-line programs. In V. P. Gerdt, W. Koepf, E. W. Mayr, and E. V. Vorozhtsov, editors, Proc. Computer Algebra in Scientific Computing (CASC 2013), volume 8136 of Lecture Notes in Computer Science, pages 61--74. Springer, September 2013. Google ScholarDigital Library
- A. Arnold, M. Giesbrecht, and D. S. Roche. Sparse interpolation over finite fields via low-order roots of unity. ISSAC '14, pages 27--34. ACM, 2014. Google ScholarDigital Library
- A. Arnold, M. Giesbrecht, and D. S. Roche. Faster sparse multivariate polynomial interpolation of straight-line programs. Journal of Symbolic Computation, 2015. Google ScholarDigital Library
- M. Ben-Or and P. Tiwari. A deterministic algorithm for sparse multivariate polynomial interpolation. STOC '88, pages 301--309. ACM, 1988. Google ScholarDigital Library
- F. Biscani. Parallel sparse polynomial multiplication on modern hardware architectures. ISSAC '12, 2012. Google ScholarDigital Library
- R. E. Blahut. A universal reed-solomon decoder. IBM Journal of Research and Development, 28 (2): 150--158, March 1984. Google ScholarDigital Library
- A. Borodin and P. Tiwari. On the decidability of sparse univariate polynomial interpolation. Computational Complexity, 1: 67--90, 1991.Google ScholarCross Ref
- A. Bostan, G. Lecerf, and E. Schost. Tellegen's principle into practice. ISSAC '03, pages 37--44. ACM, 2003. Google ScholarDigital Library
- A. Bostan, F. Chyzak, M. Giusti, R. Lebreton, G. Lecerf, B. Salvy, and E. Schost. Algorithmes Efficaces en Calcul Formel. 1.0 edition, Aug. 2017.Google Scholar
- B. Boyer, M. T. Comer, and E. L. Kaltofen. Sparse polynomial interpolation by variable shift in the presence of noise and outliers in the evaluations. In Electr. Proc. Tenth Asian Symposium on Computer Mathematics (ASCM 2012), 2012.Google Scholar
- D. G. Cantor and E. Kaltofen. On fast multiplication of polynomials over arbitrary algebras. Acta Informatica, 28: 693--701, 1991. Google ScholarDigital Library
- A. Chattopadhyay, B. Grenet, P. Koiran, N. Portier, and Y. Strozecki. Computing the multilinear factors of lacunary polynomials without heights. Manuscript (submitted), 2013. URL https://arxiv.org/abs/1311.5694.Google Scholar
- M. T. Comer, E. L. Kaltofen, and C. Pernet. Sparse polynomial interpolation and Berlekamp/Massey algorithms that correct outlier errors in input values. ISSAC '12, pages 138--145. ACM, 2012. Google ScholarDigital Library
- F. Cucker, P. Koiran, and S. Smale. A polynomial time algorithm for Diophantine equations in one variable. J. Symbolic Comput., 27 (1): 21--29, 1999. Google ScholarDigital Library
- A. Cuyt and W. Lee. Sparse interpolation of multivariate rational functions. Theoretical Computer Science, 412 (16): 1445 -- 1456, 2011. Google ScholarDigital Library
- A. Cuyt, W. shin Lee, and X. Wang. On tensor decomposition, sparse interpolation and Padé approximation. Jaen journal on approximation, 8 (1): 33--58, 2016.Google Scholar
- J. H. Davenport and J. Carette. The sparsity challenges. In Symbolic and Numeric Algorithms for Scientific Computing (SYNASC), 2009 11th International Symposium on, pages 3 --7, Sept. 2009. Google ScholarDigital Library
- R. Fateman. Comparing the speed of programs for sparse polynomial multiplication. SIGSAM Bull., 37 (1): 4--15, March 2003. Google ScholarDigital Library
- R. Fateman. Draft: What's it worth to write a short program for polynomial multiplication? Online, Dec. 2008. URL http://www.cs.berkeley.edu/fateman/papers/shortprog.pdf.Google Scholar
- R. J. Fateman. Endpaper: Frpoly: A benchmark revisited. LISP and Symbolic Computation, 4 (2): 155--164, Apr 1991. Google ScholarDigital Library
- M. A. Forbes and A. Shpilka. Complexity theory column 88: Challenges in polynomial factorization. SIGACT News, 46 (4): 32--49, Dec. 2015. Google ScholarDigital Library
- r(2007)}Fur07M. Fürer. Faster integer multiplication. STOC '07, pages 57--66. ACM, 2007. Google ScholarDigital Library
- S. Garg and É. Schost. Interpolation of polynomials given by straight-line programs. Theoretical Computer Science, 410 (27--29): 2659--2662, 2009. Google ScholarDigital Library
- M. Gastineau and J. Laskar. Development of TRIP: Fast sparse multivariate polynomial multiplication using burst tries. In V. Alexandrov, G. van Albada, P. Sloot, and J. Dongarra, editors, Computational Science - ICCS 2006, volume 3992 of Lecture Notes in Computer Science, pages 446--453. Springer Berlin Heidelberg, 2006. Google ScholarDigital Library
- M. Gastineau and J. Laskar. Highly scalable multiplication for distributed sparse multivariate polynomials on many-core systems. In V. P. Gerdt, W. Koepf, E. W. Mayr, and E. V. Vorozhtsov, editors, Computer Algebra in Scientific Computing, pages 100--115, Cham, 2013. Springer International Publishing. Google ScholarDigital Library
- M. Gastineau and J. Laskar. Parallel sparse multivariate polynomial division. PASCO '15, pages 25--33. ACM, 2015. Google ScholarDigital Library
- nd Gerhard(2003)}vzGG03J. Gathenvon zur Gathen and J. Gerhard. Modern Computer Algebra. Cambridge University Press, Cambridge, second edition, 2003. Google ScholarDigital Library
- nd Panario(2001)}vzGP01J. Gathenvon zur Gathen and D. Panario. Factoring polynomials over finite fields: A survey. Journal of Symbolic Computation, 31 (1--2): 3 -- 17, 2001.Google Scholar
- M. Giesbrecht and D. S. Roche. On lacunary polynomial perfect powers. ISSAC '08, pages 103--110. ACM, 2008. Google ScholarDigital Library
- M. Giesbrecht and D. S. Roche. Interpolation of shifted-lacunary polynomials. Computational Complexity, 19: 333--354, 2010. Google ScholarDigital Library
- }GR11M. Giesbrecht and D. S. Roche. Detecting lacunary perfect powers and computing their roots. Journal of Symbolic Computation, 46 (11): 1242--1259, 2011. Google ScholarDigital Library
- }GR11aM. Giesbrecht and D. S. Roche. Diversification improves interpolation. ISSAC '11, pages 123--130. ACM, 2011. Google ScholarDigital Library
- M. Giesbrecht, E. Kaltofen, and W. Lee. Algorithms for computing sparsest shifts of polynomials in power, chebyshev, and pochhammer bases. Journal of Symbolic Computation, 36 (3--4): 401 -- 424, 2003. ISSAC 2002. Google ScholarDigital Library
- B. Grenet. Bounded-degree factors of lacunary multivariate polynomials. Journal of Symbolic Computation, 75: 171--192, 2016. Special issue on the conference ISSAC 2014: Symbolic computation and computer algebra. Google ScholarDigital Library
- and Lecerf}GHL15B. Grenet, J. Hoevenvan der Hoeven, and G. Lecerf. Randomized root finding over finite FFT-fields using tangent Graeffe transforms. In Proc. 40th International Symposium on Symbolic and Algebraic Computation, ISSAC '15, page to appear, 2015. Google ScholarDigital Library
- D. Y. Grigoriev and M. Karpinski. The matching problem for bipartite graphs with polynomially bounded permanents is in NC. In Foundations of Computer Science, 1987., 28th Annual Symposium on, pages 166--172, Oct. 1987. Google ScholarDigital Library
- D. Y. Grigoriev, M. Karpinski, and M. F. Singer. Fast parallel algorithms for sparse multivariate polynomial interpolation over finite fields. SIAM Journal on Computing, 19 (6): 1059--1063, 1990. Google ScholarDigital Library
- W. Hart, M. van Hoeij, and A. Novocin. Practical polynomial factoring in polynomial time. ISSAC '11, pages 163--170. ACM, 2011. Google ScholarDigital Library
- and Lecerf}HHL17D. Harvey, J. Hoevenvan der Hoeven, and G. Lecerf. Faster polynomial multiplication over finite fields. J. ACM, 63 (6): 52:1--52:23, Jan. 2017. Google ScholarDigital Library
- nd Lecerf(2012)}HL12aJ. Hoevenvan der Hoeven and G. Lecerf. On the complexity of multivariate blockwise polynomial multiplication. In Proc. ISSAC 2012, pages 211--218, 2012. Google ScholarDigital Library
- nd Lecerf(2013)}HL13J. Hoevenvan der Hoeven and G. Lecerf. On the bit-complexity of sparse polynomial and series multiplication. Journal of Symbolic Computation, 50: 227--0254, 2013. Google ScholarDigital Library
- nd Lecerf(2015)}HL15J. Hoevenvan der Hoeven and G. Lecerf. Sparse polynomial interpolation in practice. ACM Commun. Comput. Algebra, 48 (3/4): 187--191, Feb. 2015. Google ScholarDigital Library
- M.-D. A. Huang and A. J. Rao. Interpolation of sparse multivariate polynomials over large finite fields with applications. Journal of Algorithms, 33 (2): 204--228, 1999. Google ScholarDigital Library
- Q. Huang and X. Gao. Faster deterministic sparse interpolation algorithms for straight-line program multivariate polynomials. CoRR, abs/1709.08979, 2017. URL http://arxiv.org/abs/1709.08979.Google Scholar
- E. Imamoglu, E. L. Kaltofen, and Z. Yang. Sparse polynomial interpolation with arbitrary orthogonal polynomial bases. In Proc. ISSAC'18, 2018. Google ScholarDigital Library
- S. M. M. Javadi and M. Monagan. Parallel sparse polynomial interpolation over finite fields. PASCO '10, pages 160--168. ACM, 2010. Google ScholarDigital Library
- S. C. Johnson. Sparse polynomial arithmetic. SIGSAM Bull., 8: 63--71, August 1974. Google ScholarDigital Library
- E. Kaltofen. Notes on polynomial and rational function interpolation. Unpublished manuscript, 1988.Google Scholar
- E. Kaltofen. Polynomial factorization: A success story. ISSAC '03, pages 3--4. ACM, 2003. Google ScholarDigital Library
- E. Kaltofen and P. Koiran. On the complexity of factoring bivariate supersparse (lacunary) polynomials. ISSAC '05, pages 208--215. ACM, 2005. Google ScholarDigital Library
- E. Kaltofen and P. Koiran. Finding small degree factors of multivariate supersparse (lacunary) polynomials over algebraic number fields. ISSAC '06, pages 162--168. ACM, 2006. Google ScholarDigital Library
- E. Kaltofen and W. Lee. Early termination in sparse interpolation algorithms. Journal of Symbolic Computation, 36 (3--4): 365--400, 2003. ISSAC 2002. Google ScholarDigital Library
- E. Kaltofen and L. Yagati. Improved sparse multivariate polynomial interpolation algorithms. In P. Gianni, editor, Symbolic and Algebraic Computation, volume 358 of Lecture Notes in Computer Science, pages 467--474. Springer Berlin / Heidelberg, 1989. Google ScholarDigital Library
- E. Kaltofen and Z. Yang. On exact and approximate interpolation of sparse rational functions. ISSAC '07, pages 203--210. ACM, 2007. Google ScholarDigital Library
- E. Kaltofen, Y. N. Lakshman, and J.-M. Wiley. Modular rational sparse multivariate polynomial interpolation. ISSAC '90, pages 135--139. ACM, 1990. Google ScholarDigital Library
- E. L. Kaltofen. Fifteen years after DSC and WLSS2: What parallel computations I do today {invited lecture at PASCO 2010}. PASCO '10, pages 10--17. ACM, 2010. Google ScholarDigital Library
- E. L. Kaltofen and M. Nehring. Supersparse black box rational function interpolation. ISSAC '11, pages 177--186. ACM, 2011. Google ScholarDigital Library
- E. L. Kaltofen and Z. Yang. Sparse multivariate function recovery from values with noise and outlier errors. ISSAC '13, pages 219--226. ACM, 2013. Google ScholarDigital Library
- E. L. Kaltofen, C. Pernet, A. Storjohann, and C. Waddell. Early termination in parametric linear system solving and rational function vector recovery with error correction. ISSAC '17, pages 237--244. ACM, 2017. Google ScholarDigital Library
- M. Khochtali, D. S. Roche, and X. Tian. Parallel sparse interpolation using small primes. PASCO '15, pages 70--77. ACM, 2015. Google ScholarDigital Library
- L. Kronecker. Grundzüge einer arithmetischen Theorie der algebraischen Grössen. Journal für die reine und angewandte Mathematik, 92: 1--122, 1882.Google Scholar
- Y. N. Lakshman and B. D. Saunders. Sparse polynomial interpolation in nonstandard bases. SIAM Journal on Computing, 24 (2): 387--397, 1995. Google ScholarDigital Library
- H. W. Lenstra, Jr. Finding small degree factors of lacunary polynomials. In Number theory in progress, Vol. 1 (Zakopane-Ko'scielisko, 1997), pages 267--276. de Gruyter, Berlin, 1999.Google Scholar
- M. Monagan and R. Pearce. Polynomial division using dynamic arrays, heaps, and packed exponent vectors. In V. Ganzha, E. Mayr, and E. Vorozhtsov, editors, Computer Algebra in Scientific Computing, volume 4770 of Lecture Notes in Computer Science, pages 295--315. Springer Berlin / Heidelberg, 2007. Google ScholarDigital Library
- M. Monagan and R. Pearce. Parallel sparse polynomial multiplication using heaps. ISSAC '09, pages 263--270. ACM, 2009. Google ScholarDigital Library
- M. Monagan and R. Pearce. Sparse polynomial division using a heap. Journal of Symbolic Computation, In Press, Corrected Proof, 2010. Google ScholarDigital Library
- M. Monagan and R. Pearce. Sparse polynomial multiplication and division in maple 14. ACM Commun. Comput. Algebra, 44 (3/4): 205--209, Jan. 2011. Google ScholarDigital Library
- M. Monagan and R. Pearce. POLY: A new polynomial data structure for maple 17. ACM Commun. Comput. Algebra, 46 (3/4): 164--167, Jan. 2013. Google ScholarDigital Library
- M. Monagan and R. Pearce. The design of Maple's sum-of-products and POLY data structures for representing mathematical objects. ACM Commun. Comput. Algebra, 48 (3/4): 166--186, Feb. 2015. Google ScholarDigital Library
- B. Mourrain. Fast algorithm for border bases of artinian gorenstein algebras. ISSAC '17, pages 333--340. ACM, 2017. Google ScholarDigital Library
- D. A. Plaisted. New NP-hard and NP-complete polynomial and integer divisibility problems. Theoret. Comput. Sci., 31 (1--2): 125--138, 1984.Google ScholarCross Ref
- D. A. Popescu and R. T. Garcia. Multivariate polynomial multiplication on gpu. Procedia Computer Science, 80: 154 -- 165, 2016. International Conference on Computational Science 2016, ICCS 2016, 6--8 June 2016, San Diego, California, USA. Google ScholarDigital Library
- B. d. Prony. Essai expérimental et analytique sur les lois de la Dilatabilité des fluides élastique et sur celles de la Force expansive de la vapeur de l'eau et de la vapeur de l'alkool, à différentes températures. J. de l'École Polytechnique, 1: 24--76, 1795.Google Scholar
- D. S. Roche. Adaptive polynomial multiplication. In Proc. Milestones in Computer Algebra (MICA), pages 65--72, 2008.Google Scholar
- D. S. Roche. Chunky and equal-spaced polynomial multiplication. Journal of Symbolic Computation, 46 (7): 791--806, July 2011. Google ScholarDigital Library
- mann(2003)}Sch03H. Schönemann. Singular in a framework for polynomial computations. In M. Joswig and N. Takayama, editors, Algebra, Geometry and Software Systems, pages 163--176, Berlin, Heidelberg, 2003. Springer Berlin Heidelberg.Google ScholarCross Ref
- J. Solomon. Numerical Algorithms. AK Peters/CRC Press, 2015.Google Scholar
- A. Steel. Multivariate polynomial rings. In The Magma Handbook. Computational Algebra Group, University of Sydney, 2018. URL http://magma.maths.usyd.edu.au/magma/handbook/text/223#1924.Google Scholar
- W. Stein and T. Sage Development Team. Polynomial rings. In Sage Reference Manual. URL https://doc.sagemath.org/html/en/reference/polynomial_rings. v8.2.Google Scholar
- T. Yan. The geobucket data structure for polynomials. Journal of Symbolic Computation, 25 (3): 285--293, 1998. Google ScholarDigital Library
- R. Zippel. Probabilistic algorithms for sparse polynomials. In E. Ng, editor, Symbolic and Algebraic Computation, volume 72 of Lecture Notes in Computer Science, pages 216--226. Springer Berlin / Heidelberg, 1979. Google ScholarDigital Library
- R. Zippel. Interpolating polynomials from their values. Journal of Symbolic Computation, 9 (3): 375--403, 1990. Computational algebraic complexity editorial. Google ScholarDigital Library
Index Terms
- What Can (and Can't) we Do with Sparse Polynomials?
Recommendations
On solving univariate sparse polynomials in logarithmic time
Special issue: Foundations of computational mathematics 2002 workshopsLet f be a degree D univariate polynomial with real coefficients and exactly m monomial terms. We show that in the special case m = 3 we can approximate within ε all the roots of f in the interval [0,R] using just O(log(D)log(D log R/ε)) arithmetic ...
Polynomials arising in factoring generalized Vandermonde determinants: an algorithm for computing their coefficients
We consider generalized Vandermonde determinants of the form where the x"i are distinct points belonging to an interval [a, b] of the real line, the index s stands for the order, the sequence @m consists of ordered integers 0 @? @m"1 < @m"2 < ... < @m"...
On probabilistic analysis of randomization in hybrid symbolic-numeric algorithms
SNC '07: Proceedings of the 2007 international workshop on Symbolic-numeric computationAlgebraic randomization techniques can be applied to hybrid symbolic-numeric algorithms. Here we consider the problem of interpolating a sparse rational function from noisy values. We develop a new hybrid algorithm based on Zippel's original sparse ...
Comments