Cited By
View all- Villard G(2025)Bivariate polynomial reduction and elimination ideal over finite fieldsJournal of Symbolic Computation10.1016/j.jsc.2024.102367127(102367)Online publication date: Mar-2025
Faster Modular Composition
Abstract
A new Las Vegas algorithm is presented for the composition of two polynomials modulo a third one, over an arbitrary field. When the degrees of these polynomials are bounded by n, the algorithm uses O(n1.43) field operations, breaking through the 3/2 barrier in the exponent for the first time. The previous fastest algebraic algorithms, due to Brent and Kung in 1978, require O(n1.63) field operations in general, and n3/2+o(1) field operations in the special case of power series over a field of large enough characteristic. If cubic-time matrix multiplication is used, the new algorithm runs in n5/3+o(1) operations, while previous ones run in O(n2) operations.
Our approach relies on the computation of a matrix of algebraic relations that is typically of small size. Randomization is used to reduce arbitrary input to this favorable situation.
References
[1]
Simon Abelard, Alain Couvreur, and Grégoire Lecerf. 2020. Sub-quadratic time for Riemann-Roch spaces: Case of smooth divisors over nodal plane projective curves. In Proc. ISSAC. ACM Press, 14–21. DOI:
[2]
Simon Abelard, Alain Couvreur, and Grégoire Lecerf. 2021. Efficient Computation of Riemann-Roch Spaces for Plane Curves with Ordinary Singularities. HAL Report hal-03110135. Retrieved from https://hal.archives-ouvertes.fr/hal-03110135
[3]
Josh Alman and Virginia Vassilevska Williams. 2021. A refined laser method and faster matrix multiplication. In Proc. SODA. SIAM, 522–539. DOI:
[4]
Bernhard Beckermann and George Labahn. 1994. A uniform approach for the fast computation of matrix-type Padé approximants. SIAM J. Matrix Analysis and Applications 26, 3 (1994), 804–823. DOI:
[5]
Bernhard Beckermann, George Labahn, and Gilles Villard. 1999. Shifted normal forms of polynomial matrices. In Proc. ISSAC. ACM Press, 189–196. DOI:
[6]
Daniel J. Bernstein. 1998. Composing power series over a finite ring in essentially linear time. J. Symb. Comput. 26, 3 (1998), 339–341. DOI:
[7]
Vishwas Bhargava, Sumanta Ghosh, Zeyu Guo, Mrinal Kumar, and Chris Umans. 2022. Fast multivariate multipoint evaluation over all finite fields. In Proc. FOCS. IEEE, 221–232. DOI:
[8]
Vishwas Bhargava, Sumanta Ghosh, Mrinal Kumar, and Chandra Kanta Mohapatra. 2022. Fast, algebraic multivariate multipoint evaluation in small characteristic and applications. In Proc. STOC. ACM Press, 403–415. DOI:
[9]
Dario Bini and Victor Y. Pan. 1994. Polynomial and Matrix Computations. Birkhäuser. DOI:
[10]
Alin Bostan, Frédéric Chyzak, Marc Giusti, Romain Lebreton, Grégoire Lecerf, Bruno Salvy, and Éric Schost. 2017. Algorithmes Efficaces en Calcul Formel. In French. Edited by the authors. Retrieved from https://hal.archives-ouvertes.fr/AECF/
[11]
Alin Bostan, Frédéric Chyzak, François Ollivier, Bruno Salvy, Éric Schost, and Alexandre Sedoglavic. 2007. Fast computation of power series solutions of systems of differential equations. In Proc. SODA. SIAM, 1012–1021. Retrieved from
[12]
Alin Bostan, Philippe Flajolet, Bruno Salvy, and Éric Schost. 2006. Fast computation of special resultants. J. Symb. Comput. 41, 1 (2006), 1–29. DOI:
[13]
Alin Bostan, Grégoire Lecerf, and Éric Schost. 2003. Tellegen’s principle into practice. In Proc. ISSAC. ACM Press, 37–44. DOI:
[14]
Alin Bostan, Bruno Salvy, and Éric Schost. 2008. Power series composition and change of basis. In Proc. ISSAC. ACM Press, 269–276. DOI:
[15]
Richard P. Brent, Fred G. Gustavson, and David Y. Y. Yun. 1980. Fast solution of toeplitz systems of equations and computation of padé approximants. J. Algorithms 1, 3 (1980), 259–295. DOI:
[16]
Richard P. Brent and H. T. Kung. 1977. Fast algorithms for composition and reversion of multivariate power series. In Proc. Conference on Theoretical Computer Science (Waterloo ON, August 15–17, 1977). University of Waterloo, 149–158.
[17]
Richard P. Brent and H. T. Kung. 1978. Fast algorithms for manipulating formal power series. J. ACM 25, 4 (1978), 581–595. DOI:
[18]
Marshall W. Buck, Raymond A. Coley, and David P. Robbins. 1992. A generalized vandermonde determinant. J. Algebraic Combin. 1, 2 (1992), 105–109. DOI:
[19]
Peter Bürgisser, Michael Clausen, and Mohammad Amin Shokrollahi. 1997. Algebraic Complexity Theory. Grundlehren der mathematischen Wissenschaften, Vol. 315. Springer. DOI:
[20]
Don Coppersmith. 1994. Solving homogeneous linear equations over GF(2) via block wiedemann algorithm. Math. Comput. 62, 205 (1994), 333–350. DOI:
[21]
Jean Della Dora, Claire Discrescenzo, and Dominique Duval. 1985. About a new method for computing in algebraic number fields. In EUROCAL’85 (LNCS), Vol. 204. Springer, 289–290. DOI:
[22]
Ran Duan, Hongxun Wu, and Renfei Zhou. 2023. Faster matrix multiplication via asymmetric hashing. In Proc. FOCS. IEEE, 2129–2138. DOI:
[23]
David S. Dummit and Richard M. Foote. 2003. Abstract Algebra. John Wiley & Sons.
[24]
Wayne Eberly, Mark Giesbrecht, Pascal Giorgi, Arne Storjohann, and Gilles Villard. 2007. Faster inversion and other black box matrix computation using efficient block projections. In Proc. ISSAC. ACM Press, 143–150. DOI:
[25]
Mariano Gasca and José J. Martínez. 1987. On the computation of multivariate confluent Vandermonde determinants and its applications. In Proc. Mathematics of Surfaces II. Vol. 11. Oxford Univ. Press, 101–114.
[26]
Joachim von zur Gathen and Jürgen Gerhard. 1999. Modern Computer Algebra. Third edition 2013. Cambridge University Press. DOI:
[27]
Joachim von zur Gathen and Victor Shoup. 1992. Computing frobenius maps and factoring polynomials. Comput. Complex. 2 (1992), 187–224. DOI:
[28]
Jürgen Gerhard. 2004. Modular Algorithms in Symbolic Summation and Symbolic Integration. Springer. DOI:
[29]
Patrizia Gianni and Barry Trager. 1996. Square-free algorithms in positive characteristic. Appl. Algebra Eng. Commun. Comput. 7, 1 (1996), 1–14. DOI:
[30]
Mark Giesbrecht, Armin Jamshidpey, and Éric Schost. 2021. Subquadratic-time algorithms for normal bases. Comput. Complex. 35, 1 (2021). DOI:
[31]
Pascal Giorgi, Claude-Pierre Jeannerod, and Gilles Villard. 2003. On the complexity of polynomial matrix computations. In Proc. ISSAC. ACM Press, 135–142. DOI:
[32]
Joris van der Hoeven. 2002. Relax, but don’t be too lazy. J. Symb. Comput. 34, 6 (2002), 479–542. DOI:
[33]
Joris van der Hoeven and Robin Larrieu. 2019. Fast Gröbner basis computation and polynomial reduction for generic bivariate ideals. Appl. Algebr. Eng. Comm. 30, 6 (2019), 509–539. DOI:
[34]
Joris van der Hoeven and Grégoire Lecerf. 2017. Composition modulo powers of polynomials. In Proc. ISSAC. ACM Press, 445–452. DOI:
[35]
Joris van der Hoeven and Grégoire Lecerf. 2018. Modular composition via factorization. J. Complexity 48 (2018), 36–68. DOI:
[36]
Joris van der Hoeven and Grégoire Lecerf. 2019. Accelerated tower arithmetic. J. Complexity 55 (2019), 101402. DOI:
[37]
Joris van der Hoeven and Grégoire Lecerf. 2020. Directed evaluation. J. Complexity 60 (2020), 101498. DOI:
[38]
Joris van der Hoeven and Grégoire Lecerf. 2021. Amortized bivariate multi-point evaluation. In Proc. ISSAC. ACM Press, 179–185. DOI:
[39]
Joris van der Hoeven and Grégoire Lecerf. 2021. Fast amortized multi-point evaluation. J. Complexity 67 (2021), 101574. DOI:
[40]
Joris van der Hoeven and Grégoire Lecerf. 2021. Fast computation of generic bivariate resultants. J. Complexity 62 (2021), 101499. DOI:
[41]
Xiohan Huang and Victor Y. Pan. 1998. Fast rectangular matrix multiplication and applications. J. Complexity 14 (1998), 257–299. DOI:
[42]
Claude-Pierre Jeannerod, Vincent Neiger, and Gilles Villard. 2020. Fast computation of approximant bases in canonical form. J. Symb. Comput. 98 (2020), 192–224. DOI:
[43]
Thomas Kailath. 1980. Linear Systems. Prentice-Hall.
[44]
Erich Kaltofen. 1992. On computing determinants without divisions. In Proc. ISSAC. ACM Press, 342–349. DOI:
[45]
Erich Kaltofen. 2000. Challenges of symbolic computation: My favorite open problems. J. Symb. Comput. 29, 6 (2000), 891–919. DOI:
[46]
Erich Kaltofen and Victor Y. Pan. 1991. Processor efficient parallel solution of linear systems over an abstract field. In Proc. SPAA. ACM, 180–191. DOI:
[47]
Erich Kaltofen and B. David Saunders. 1991. On wiedemann’s method of solving sparse linear systems. In AAECC-9 (LNCS), Vol. 539. Springer Verlag, 29–38. DOI:
[48]
Erich Kaltofen and Victor Shoup. 1997. Fast polynomial factorization over high algebraic extensions of finite fields. In Proc. ISSAC. ACM Press, 184–188. DOI:
[49]
Erich Kaltofen and Victor Shoup. 1998. Subquadratic-time factoring of polynomials over finite fields. Math. Comp. 67, 233 (1998), 1179–1197. DOI:
[50]
Erich Kaltofen and Gilles Villard. 2005. On the complexity of computing determinants. Comput. Complex. 13, 3 (2005), 91–130. DOI:
[51]
Erich Kaltofen and George Yuhasz. 2013. On the matrix berlekamp-massey algorithm. ACM Trans. Algorithms 9, 4 (2013), 33:1–33:24. DOI:
[52]
Kiran S. Kedlaya and Christopher Umans. 2011. Fast polynomial factorization and modular composition. SIAM J. on Computing 40, 6 (2011), 1767–1802. DOI:
[53]
George Labahn, Vincent Neiger, and Wei Zhou. 2017. Fast, deterministic computation of the Hermite normal form and determinant of a polynomial matrix. J. Complexity 42 (2017), 44–71. DOI:
[54]
Daniel Lazard. 1985. Ideal bases and primary decomposition: case of two variables. J. Symb. Comput. 1, 3 (1985), 261–270. DOI:
[55]
François Le Gall. 2023. Faster Rectangular Matrix Multiplication by Combination Loss Analysis. arXiv:2307.06535. Retrieved from https://arxiv.org/abs/cs/2307.06535
[56]
François Le Gall and Florent Urrutia. 2018. Improved rectangular matrix multiplication using powers of the Coppersmith-Winograd tensor. In Proc. SODA. SIAM, 1029–1046. DOI:
[57]
Grégoire Lecerf. 2008. Fast separable factorization and applications. Appl. Algebra Eng. Commun. Comput. 19, 2 (2008), 135–160. DOI:
[58]
John D. Lipson. 1976. Newton’s method: A great algebraic algorithm. In Proc. SYMSAC. ACM Press, 260–270. DOI:
[59]
Thom Mulders and Arne Storjohann. 2003. On lattice reduction for polynomial matrices. J. Symb. Comput. 35, 4 (2003), 377–401. DOI:
[60]
Vincent Neiger. 2016. Bases of relations in one or several variables: fast algorithms and applications. Ph.D. Dissertation. École Normale Supérieure de Lyon. Retrieved from https://tel.archives-ouvertes.fr/tel-01431413/
[61]
Vincent Neiger, Johan Rosenkilde, and Grigory Solomatov. 2020. Generic bivariate multi-point evaluation, interpolation and modular composition with precomputation. In Proc. ISSAC. ACM Press, 388–395. DOI:
[62]
Morris Newman. 1972. Integral Matrices. Academic Press. First edition.
[63]
Michael Nüsken and Martin Ziegler. 2004. Fast multipoint evaluation of bivariate polynomials. In Algorithms—ESA 2004. Springer, Berlin, 544–555. DOI:
[64]
Michael Paterson and Larry J. Stockmeyer. 1973. On the number of nonscalar multiplications necessary to evaluate polynomials. SIAM J. Comput. 2, 1 (1973), 60–66. DOI:
[65]
Adrien Poteaux and É. Schost. 2013. Modular composition modulo triangular sets and applications. Comput. Complex. 22, 3 (2013), 463–516. DOI:
[66]
Adrien Poteaux and Éric Schost. 2013. On the complexity of computing with zero-dimensional triangular sets. J. Symb. Comput. 50 (2013), 110–138. DOI:
[67]
Daniel Reischert. 1997. Asymptotically fast computation of subresultants. In Proc. ISSAC. ACM Press, 233–240. DOI:
[68]
Peter Ritzmann. 1986. A fast numerical algorithm for the composition of power series with complex coefficients. Theoret. Comput. Sci. 44, 1 (1986), 1–16. DOI:
[69]
Victor Shoup. 1994. Fast construction of irreducible polynomials over finite fields. J. Symb. Comput. 17, 5 (1994), 371–391. DOI:
[70]
Victor Shoup. 1995. A new polynomial factorization algorithm and its implementation. J. Symb. Comput. 20, 4 (1995), 363–397. DOI:
[71]
Victor Shoup. 1999. Efficient computation of minimal polynomials in algebraic extensions of finite fields. In Proc. ISSAC. ACM Press, 53–58. DOI:
[72]
Christopher Umans. 2008. Fast polynomial factorization and modular composition in small characteristic. In Proc. STOC. ACM Press, 481–490. DOI:
[73]
Marc Van Barel and Adhemar Bultheel. 1992. A general module theoretic framework for vector M-Padé and matrix rational interpolation. Numer. Algorithms 3 (1992), 451–462. DOI:
[74]
Gilles Villard. 1997. A study of Coppersmith’s Block Wiedemann Algorithm using Matrix Polynomials. RR 975 IM IMAG. Retrieved from http://perso.ens-lyon.fr/gilles.villard/BIBLIOGRAPHIE/PDF/rr0497.pdf
[75]
Gilles Villard. 2018. On computing the resultant of generic bivariate polynomials. In Proc. ISSAC. ACM Press, 391–398. DOI:
[76]
Douglas H. Wiedemann. 1986. Solving sparse linear equations over finite fields. IEEE Trans. Information Theory 32, 1 (1986), 54–62. DOI:
[77]
Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, and Renfei Zhou. 2024. New bounds for matrix multiplication: From alpha to omega. In Proc. SODA. SIAM, 3792–3835. DOI:
[78]
William A. Wolovich. 1974. Linear Multivariable Systems. Applied Mathematical Sciences, Vol. 11. Springer-Verlag New-York. DOI:
[79]
W. Zhou and G. Labahn. 2012. Efficient algorithms for order basis computation. J. Symb. Comput. 47, 7 (2012), 793–819. DOI:
[80]
Wei Zhou, George Labahn, and Arne Storjohann. 2012. Computing minimal nullspace bases. In Proc. ISSAC. ACM Press, 366–373. DOI:
Recommendations
Fast polynomial factorization and modular composition in small characteristic
STOC '08: Proceedings of the fortieth annual ACM symposium on Theory of computingWe obtain randomized algorithms for factoring degree n univariate polynomials over F_q that use O(n1.5 + o(1) + n1 + o(1)log q) field operations, when the characteristic is at most no(1). When log q < n, this is asymptotically faster than the best ...
Fast Polynomial Factorization and Modular Composition
We obtain randomized algorithms for factoring degree $n$ univariate polynomials over $\mathbb{F}_q$ requiring $O(n^{1.5 + o(1)}\,{\rm log}^{1+o(1)} q+ n^{1 + o(1)}\,{\rm log}^{2+o(1)} q)$ bit operations. When ${\rm log}\, q < n$, this is asymptotically ...
Faster algorithms for the characteristic polynomial
ISSAC '07: Proceedings of the 2007 international symposium on Symbolic and algebraic computationA new randomized algorithm is presented for computing the characteristic polynomial of an n x n matrix over a field. Over a suffciently large field the asymptotic expected complexity of the algorithm is O(nθ)field operations, improving by a factor of ...
Comments
Information & Contributors
Information
Published In
April 2024
627 pages
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 10 April 2024
Online AM: 25 December 2023
Accepted: 06 December 2023
Revised: 28 August 2023
Received: 25 October 2021
Published in JACM Volume 71, Issue 2
Check for updates
Author Tags
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 186Total Downloads
- Downloads (Last 12 months)186
- Downloads (Last 6 weeks)13
Reflects downloads up to 30 Sep 2024
Other Metrics
Citations
Cited By
View all- Villard G(2025)Bivariate polynomial reduction and elimination ideal over finite fieldsJournal of Symbolic Computation10.1016/j.jsc.2024.102367127(102367)Online publication date: Mar-2025
View Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in