research-article

Elimination ideal and bivariate resultant over finite fields

Author:

Gilles VillardAuthors Info & Claims

ISSAC '23: Proceedings of the 2023 International Symposium on Symbolic and Algebraic Computation

Pages 526 - 534

https://doi.org/10.1145/3597066.3597100

Published: 24 July 2023 Publication History

Abstract

A new algorithm is presented for computing the largest degree invariant factor of the Sylvester matrix (with respect either to x or y) associated to two polynomials a and b in which have no non-trivial common divisors. The algorithm is randomized of the Monte Carlo type and requires (delog q)1 + o(1) bit operations, where d and e respectively bound the input degrees in x and in y. It follows that the same complexity estimate is valid for computing: a generator of the elimination ideal (or ), as long as the polynomial system a = b = 0 has not roots at infinity; the resultant of a and b when they are sufficiently generic, especially so that the Sylvester matrix has a unique non-trivial invariant factor. Our approach is to use the reduction of the problem to a problem of minimal polynomial in the quotient algebra . By proposing a new method based on structured polynomial matrix division for computing with the elements in the quotient, we manage to improve the best known complexity bounds.

References

[1]

[1] M.-E. Alonso, E. Becker, M.-F. Roy, and T. Wörmann. Zeros, multiplicities, and idempotents for zero-dimensional systems. In Algorithms in Algebraic Geometry and Applications, pages 1–15. PM vol. 143, Birkhaüser, 1996.

[2]

[2] E. Becker, T. Mora, M. G. Marinari, and C. Traverso. The Shape of the Shape Lemma. In ISSAC ’94: Proceedings of the international symposium on Symbolic and algebraic computation, pages 129–133. ACM Press, 1994.

[3]

[3] B. Beckermann and G. Labahn. A Uniform Approach for the Fast Computation of Matrix-Type Padé Approximants. SIAM J. Matrix Analysis and Applications, 15(3):804–823, 1994.

Digital Library

[4]

[4] J. Berthomieu, V. Neiger, and M. Safey El Din. Faster Change of Order Algorithm for Gröbner Bases under Shape and Stability Assumptions. In ISSAC ’22: Proceedings of the international symposium on Symbolic and algebraic computation, pages 409–418. ACM Press, 2022.

[5]

[5] V. Bhargava, S. Ghosh, Z. Guo, M. Kumar, and C. Umans. Fast Multivariate Multipoint Evaluation Over All Finite Fields. In IEEE 63rd Annual Symposium on Foundations of Computer Science, pages 221–232. IEEE, 2022.

[6]

[6] D. Bini and V. Y. Pan. Polynomial and Matrix Computations. Birkhäuser, 1994.

Digital Library

[7]

[7] J. L. Bordewijk. Inter-reciprocity applied to electrical networks. PhD thesis, Technische Hogeschool Delft, 1956.

[8]

[8] A. Bostan, P. Flajolet, B. Salvy, and E. Schost. Fast computation of special resultants. J. Symb. Comput., 41(1):1–29, 2006.

Digital Library

[9]

[9] A. Bostan, G. Lecerf, and É. Schost. Tellegen’s principle into practice. In ISSAC ’03: Proceedings of the international symposium on Symbolic and algebraic computation, pages 37–44. ACM Press, 2003.

[10]

[10] A. Bostan, B. Salvy, and É. Schost. Fast Algorithms for Zero-Dimensional Polynomial Systems using Duality. Appl. Algebr. Eng. Comm., 14:239–272, 2003.

[11]

[11] R. P. Brent and H. T. Kung. Fast algorithms for manipulating formal power series. J. ACM, 25(4):581–595, 1978.

Digital Library

[12]

[12] P. Bürgisser, M. Clausen, and M. A. Shokrollahi. Algebraic complexity theory, volume 315 of Grundlehren der mathematischen Wissenschaften. Springer, 1997.

[13]

[13] D. Coppersmith, A. M. Odlzyko, and R. Schroeppel. Discrete logarithms in GF(p). Algorithmica, 1(1-4):1–15, 1986.

Digital Library

[14]

[14] J.-M. Couveignes and R. Lercier. Fast construction of irreducible polynomials over finite fields. Isr. J. Math., 194(1):77–105, 2013.

[15]

[15] D. A. Cox and C. D’Andrea. Subresultants and the Shape Lemma. Math. Comput., 2003.

[16]

[16] D. A. Cox, J. Little, and D. O’Shea. Using Algebraic Geometry. Springer-Verlag, New-York, 1998. 2nd edition 2005.

[17]

[17] X. Dahan. Lexicographic Gröbner bases of bivariate polynomials modulo a univariate one. J. Symb. Comput., 110:24–65, 2022.

Digital Library

[18]

[18] J.-C. Faugère, P. Gaudry, L. Huot, and G. Renault. Sub-cubic change of ordering for Gröbner basis: a probabilistic approach. In ISSAC ’14: Proceedings of the international symposium on Symbolic and algebraic computation, pages 170–177. ACM Press, 2014.

[19]

[19] J.-C. Faugère and C. Mou. Fast algorithm for change of ordering of zero-dimensional Gröbner bases with sparse multiplication matrices. In Proc. ISSAC, pages 115–122. ACM Press, 2011.

[20]

[20] J.-C. Faugère and C. Mou. Sparse FGLM algorithms. J. Symb. Comput., 80(3):538–569, 2017.

[21]

[21] C. M. Fiduccia. On the algebraic complexity of matrix multiplication. PhD thesis, Brown University, 1973. https://cr.yp.to/bib/1973/fiduccia-matrix.html.

Digital Library

[22]

[22] J. von zur Gathen and J. Gerhard. Modern Computer Algebra. Cambridge University Press, 1999. Third edition 2013.

Digital Library

[23]

[23] P. Gianni, B. Trager, and G. Zacharias. Gröbner bases and primary decomposition of polynomial ideals. J. Symb. Computation, 6(2-3):149–167, 1988.

Digital Library

[24]

[24] L. Gonzalez-Vega, F. Rouillier, and M.-F. Roy. Symbolic Recipes for Polynomial System Solving. In Algorithms and Computation in Mathematics, Some Tapas of Computer Algebra, pages 34–65. Springer, 1999.

[25]

[25] J. van der Hoeven. On the Complexity of Multivariate Polynomial Division. In ACA 2015: Applications of Computer Algebra, pages 447–458. Springer, PROMS 198, 2017.

[26]

[26] J. van der Hoeven and R. Larrieu. Fast Gröbner basis computation and polynomial reduction for generic bivariate ideals. Appl. Algebr. Eng. Comm., 30(6):509–539, 2019.

[27]

[27] J. van der Hoeven and G. Lecerf. Fast multivariate multi-point evaluation revisited. J. of Complexity, 56, 2020.

[28]

[28] J. van der Hoeven and G. Lecerf. Fast computation of generic bivariate resultants. J. of Complexity, 62, 2021.

[29]

[29] J. van der Hoeven and G. Lecerf. On the Complexity Exponent of Polynomial System Solving. Found. Comput. Math., 21(1):1–57, 2021.

Digital Library

[30]

[30] S. G. Hyun, S. Melczer, É. Schost, and C. St-Pierre. Change of basis for m-primary ideals in one and two variables. In ISSAC ’19: Proceedings of the international symposium on Symbolic and algebraic computation, pages 227–234. ACM Press, 2019.

[31]

[31] N. Jacobson. Basic Algebra I. Dover Publications Inc., 2009. Second Edition W.H. Freeman 1985.

[32]

[32] T. Kailath. Linear Systems. Prentice-Hall, 1980.

[33]

[33] T. Kailath, S. Y. Kung, and M. Morf. Displacement ranks of matrices and linear equations. J. Math. Anal. Appl., 68(2):395–407, 1979.

[34]

[34] E. Kaltofen. Asymptotically fast solution of Toeplitz-like singular linear systems. In ISSAC ’94: Proceedings of the international symposium on Symbolic and algebraic computation, pages 297–304. ACM Press, 1994.

[35]

[35] E. Kaltofen. Challenges of Symbolic Computation: My Favorite Open Problems. J. Symbolic Computation, 29(6):891–919, 2000.

Digital Library

[36]

[36] E. Kaltofen and V. Y. Pan. Processor efficient parallel solution of linear systems over an abstract field. In SPAA ’91: Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, pages 180–191. ACM, 1991.

[37]

[37] E. Kaltofen and D. Saunders. On Wiedemann’s method of solving sparse linear systems. In AAECC 1991: Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, volume 539 of LNCS, pages 29–38. Springer Verlag, 1991.

[38]

[38] E. Kaltofen and V. Shoup. Subquadratic-time factoring of polynomials over finite fields. Mathematics of Computation, 67(233):1179–1197, 1998.

Digital Library

[39]

[39] K. S. Kedlaya and C. Umans. Fast Polynomial Factorization and Modular Composition. SIAM J. on Computing, 40(6):1767–1802, 2011.

Digital Library

[40]

[40] G. Labahn. Inversion components of block Hankel-like matrices. Linear Algebra Appl., 177:7–48, 1992.

[41]

[41] D. Lazard. Résolution des systèmes d’équations algébriques. Theor. Comput. Sci., 15(1):77–110, 1981.

[42]

[42] D. Lazard. Ideal Bases and Primary Decomposition: Case of Two Variables. J. Symb. Comput., 1(3):261–270, 1985.

Digital Library

[43]

[43] D. Lazard. Solving zero-dimensional algebraic systems. J. Symb. Comput., 13(2):117–131, 1992.

Digital Library

[44]

[44] R. Lebreton, E. Mehrabi, and É. Schost. On the complexity of solving bivariate systems: the case of non-singular solutions. In ISSAC ’13: Proceedings of the international symposium on Symbolic and algebraic computation, pages 251–258, 2013.

Digital Library

[45]

[45] G. Lecerf. On the complexity of the Lickteig-Roy subresultant algorithm. J. Symb. Comput., 92:243–268, 2019.

[46]

[46] B. Mourrain and V. Y. Pan. Multivariate Polynomials, Duality, and Structured matrices. J. of Complexity, 16(1):110–180, 2000.

[47]

[47] V. Y. Pan. Structured Matrices and Polynomials: Unified Superfast Algorithms. Springer, 2001.

[48]

[48] C. Pascal and É. Schost. Change of order for bivariate triangular sets. In ISSAC ’06: Proceedings of the international symposium on Symbolic and algebraic computation, pages 277–284. ACM Press, 2006.

[49]

[49] C. Pernet, H. Signargout, and G. Villard. High-order lifting for polynomial Sylvester matrices. Hal-03740320, 2022.

[50]

[50] A. Poteaux and É. Schost. Modular Composition Modulo Triangular Sets and Applications. Comput. Complex., 22(3):463–516, 2013.

Digital Library

[51]

[51] J. Rifà and J. Borrell. Improving the time complexity of the computation of irreducible and primitive polynomials in finite fields. In AAECC 1991: Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, LNCS 539, pages 352–359, 1991.

[52]

[52] F. Rouillier. Solving Zero-Dimensional Systems Through the Rational Univariate Representation. Appl. Algebra Eng. Commun. Comput., 9:433–461, 1999.

[53]

[53] V. Shoup. A Fast Deterministic Algorithm for Factoring Polynomials over Finite Fields of Small Characteristic. In Proc. ISSAC, pages 14–21, 1991.

Digital Library

[54]

[54] V. Shoup. Fast Construction of Irreducible Polynomials over Finite Fields. J. Symb. Comput., 17(5):371–391, 1994.

Digital Library

[55]

[55] V. Shoup. A new polynomial factorization algorithm and its implementation. J. Symb. Comput., 20(4):363–397, 1995.

Digital Library

[56]

[56] V. Shoup. Efficient computation of minimal polynomials in algebraic extensions of finite fields. In ISSAC ’99: Proceedings of the international symposium on Symbolic and algebraic computation, pages 53–58. ACM Press, 1999.

[57]

[57] A. Storjohann. Algorithms for Matrix Canonical Forms. PhD thesis, Institut für Wissenschaftliches Rechnen, ETH-Zentrum, Zurich, Switzerland, November 2000.

[58]

[58] J. A. Thiong Ly. Note for computing the minimun polynomial of elements in large finite fields. In Coding Theory 1988: Coding Theory and Applications, LNCS 388, pages 185–192, 1989.

[59]

[59] G. Villard. Fast Parallel Algorithms for Matrix Reduction to Normal Forms. Appl. Algebra Eng. Commun. Comput., 8(6):511–537, 1997.

[60]

[60] G. Villard. On Computing the Resultant of Generic Bivariate Polynomials. In ISSAC ’18: Proceedings of the international symposium on Symbolic and algebraic computation, pages 391–398. ACM Press, 2018.

[61]

[61] G. Villard. Elimination ideal and bivariate resultant over finite fields. Hal-03999414, 2023.

[62]

[62] D. Wiedemann. Solving sparse linear equations over finite fields. IEEE Trans. Information Theory, 32(1):54–62, 1986.

Digital Library

Cited By

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
https://doi.org/10.1016/j.jsc.2024.102367
Dahan X(2023)Chinese Remainder Theorem for bivariate lexicographic Gröbner basesProceedings of the 2023 International Symposium on Symbolic and Algebraic Computation10.1145/3597066.3597082(208-217)Online publication date: 24-Jul-2023
https://dl.acm.org/doi/10.1145/3597066.3597082

Recommendations

On Computing the Resultant of Generic Bivariate Polynomials
ISSAC '18: Proceedings of the 2018 ACM International Symposium on Symbolic and Algebraic Computation

An algorithm is presented for computing the resultant of two generic bivariate polynomials over a field K. For such p and q K[x,y] both of degree d in x and n in y , the algorithm computes the resultant with respect to y using (n² - 1/ømega d) ^1+o(1) ...
The resultant of an unmixed bivariate system
Special issue: International symposium on symbolic and algebraic computation (ISSAC 2002)

This paper gives an explicit formula for computing the resultant of any sparse unmixed bivariate system with a given support. We construct square matrices whose determinant is exactly the resultant, with no extraneous factors. This is the first time ...
On the resultant of degree-deficient polynomials
ISTASC'07: Proceedings of the 7th Conference on 7th WSEAS International Conference on Systems Theory and Scientific Computation - Volume 7

The resultant is an algebraic expression, computable in a finite number of arithmetic operations from the coefficients of two univariate polynomials, that vanishes if, and only if, the two polynomials have common zeros. The paper considers formal ...

Comments

Information & Contributors

Information

Published In

cover image ACM Other conferences

ISSAC '23: Proceedings of the 2023 International Symposium on Symbolic and Algebraic Computation

July 2023

567 pages

ISBN:9798400700392

DOI:10.1145/3597066

Editors:
Alicia Dickenstein
University of Buenos Aires, Argentina
,
Elias Tsigaridas
INRIA Paris and Sorbonne University, France
,
Gabriela Jeronimo
University of Buenos Aires, Argentina

Copyright © 2023 ACM.

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: 24 July 2023

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article
Research
Refereed limited

Conference

ISSAC 2023

ISSAC 2023: International Symposium on Symbolic and Algebraic Computation 2023

July 24 - 27, 2023

Tromsø, Norway

Acceptance Rates

Overall Acceptance Rate 395 of 838 submissions, 47%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
36
Total Downloads

Downloads (Last 12 months)15
Downloads (Last 6 weeks)0

Reflects downloads up to 04 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

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
https://doi.org/10.1016/j.jsc.2024.102367
Dahan X(2023)Chinese Remainder Theorem for bivariate lexicographic Gröbner basesProceedings of the 2023 International Symposium on Symbolic and Algebraic Computation10.1145/3597066.3597082(208-217)Online publication date: 24-Jul-2023
https://dl.acm.org/doi/10.1145/3597066.3597082

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.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

HTML Format

View this article in HTML Format.

Media

Figures

Other

Tables

View Table of Contents