[16] J. Berthomieu and J.-Ch. Faugère. Guessing Linear Recurrence Relations of Sequence Tuples and P-Recursive Sequences with Linear Algebra. In *Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computation*, ISSAC '16, pages 95–102, New York, NY, USA, 2016. Association for Computing Machinery.

[17] J. Berthomieu and J.-Ch. Faugère. A polynomial-division-based algorithm for computing linear recurrence relations. In *Proceedings of the 2018 ACM International Symposium on Symbolic and Algebraic Computation*, ISSAC '18, pages 79–86, New York, NY, USA, 2018. ACM.

[18] J. Berthomieu and J.-Ch. Faugère. In-depth comparison of the Berlekamp–Massey–Sakata and the Scalar-FGLM algorithms: The adaptive variants. *Journal of Symbolic Computation*, 101:270–303, 2020.

[19] J. Berthomieu and J.-Ch. Faugère. Polynomial-division-based algorithms for computing linear recurrence relations. *Journal of Symbolic Computation*, 109:1–30, 2022.

[20] J. Berthomieu, V. Neiger, and M. Safey El Din. Faster Change of Order Algorithm for Gröbner Bases under Shape and Stability Assumptions. In *Proceedings of the 2022 International Symposium on Symbolic and Algebraic Computation*, ISSAC '22, pages 409–418, New York, NY, USA, 2022. Association for Computing Machinery.

[21] J. Berthomieu and M. Safey El Din. Guessing Gröbner bases of structured ideals of relations of sequences. *Journal of Symbolic Computation*, 111:1–26, 2022.

[22] P. Boito and O. Ruatta. Extended Companion Matrix for Approximate GCD. In *Proceedings of the 2011 International Workshop on Symbolic-Numeric Computation*, SNC '11, pages 74–80, New York, NY, USA, 2012. Association for Computing Machinery.

[23] R. Bose and D. Ray-Chaudhuri. On a class of error correcting binary group codes. *Information and Control*, 3(1):68–79, 1960.

[24] W. Bosma, J. Cannon, and C. Playoust. The Magma algebra system. I. The user language. *J. Symbolic Comput.*, 24(3-4):235–265, 1997. Computational algebra and number theory (London, 1993).

[25] A. Bostan, M. Bousquet-Mélou, M. Kauers, and S. Melczer. On 3-dimensional lattice walks confined to the positive octant. *Annals of Combinatorics*, 20(4):661–704, 2016.

[26] A. Bostan, C.-P. Jeannerod, C. Mouilleron, and E. Schost. On matrices with displacement structure: Generalized operators and faster algorithms. *SIAM Journal on Matrix Analysis and Applications*, 38(3):733–775, 2017.

[27] A. Bostan, C.-P. Jeannerod, and É. Schost. Solving Toeplitz- and Vandermonde-like Linear Systems with Large Displacement Rank. In C. W. Brown, editor, *ISSAC '07*, pages 33–40. ACM Press, 2007.

[28] A. Bostan, K. Raschel, and B. Salvy. Non-D-finite excursions in the quarter plane. *J. Combin. Theory Ser. A*, 121:45–63, 2014.

[29] A. Bostan, B. Salvy, and É. Schost. Fast Algorithms for Zero-Dimensional Polynomial Systems Using Duality. *Appl. Algebra Eng. Commun. Comput.*, 14(4):239–272, 2003.

[30] M. Bousquet-Mélou and M. Mishna. Walks with small steps in the quarter plane. In *Algorithmic probability and combinatorics*, volume 520 of *Contemp. Math.*, pages 1–39. Amer. Math. Soc., Providence, RI, 2010.

[31] M. Bousquet-Mélou and M. Petkovšek. Walks confined in a quadrant are not always d-finite. *Theoret. Comput. Sci.*, 307(2):257–276, 2003. Random Generation of Combinatorial Objects and Bijeptive Combinatorics.
[32] J. Brachat, P. Comon, B. Mourrain, and E. P. P. Tsigaridas. Symmetric tensor decomposition. *Linear Algebra Appl.*, 433(11-12):1851-1872, 2010.

[33] P. Breiding, B. Sturmfels, and S. Timme. 3264 conics in a second. *Notices of the American Mathematical Society*, 67(1):30-37, 2020.

[34] R. P. Brent, F. G. Gustavson, and D. Y. Yun. Fast solution of Toeplitz systems of equations and computation of Padé approximants. *Journal of Algorithms*, 1(3):259-295, 1980.

[35] B. Buchberger. *Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal*. PhD thesis, University of Innsbruck, 1965.

[36] B. Buchberger. A Criterion for Detecting Unnecessary Reductions in the Construction of Gröbner Bases. In *EUROSAM '79, An International Symposium on Symbolic and Algebraic Manipulation*, volume 72 of *Lecture Notes in Computer Science*, pages 3-21, Berlin, 1979. Springer.

[37] L. Caniglia, A. Galligo, and J. Heintz. Some New Effectivity Bounds in Computational Geometry. In *Proceedings of the 6th International Conference, on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes*, AAECC-6, pages 131-151, Berlin, Heidelberg, 1988. Springer-Verlag.

[38] S. Collart, M. Kalkbrener, and D. Mall. Converting Bases with the Gröbner Walk. *J. Symbolic Comput.*, 24(3):465-469, 1997.

[39] C. Conradi, E. Feliu, M. Mincheva, and C. Wiuf. Identifying parameter regions for multistationarity. *PLOS Computational Biology*, 13(10):e1005751, 2017.

[40] D. Coppersmith. Solving homogeneous linear equations over GF(2) via block Wiedemann algorithm. *Math. Comp.*, 62(205):333-350, 1994.

[41] D. Cox, J. Little, and D. O'Shea. *Ideals, Varieties, and Algorithms*. Undergraduate Texts in Mathematics. Springer, New York, fourth edition, 2015. An introduction to computational algebraic geometry and commutative algebra.

[42] W. Decker, G.-M. Greuel, G. Pfister, and H. Schönemann. Singular 4.1-2 — A computer algebra system for polynomial computations. http://www.singular.uni-kl.de, 2019.

[43] R. Duan, H. Wu, and R. Zhou. Faster Matrix Multiplication via Asymmetric Hashing, 2022.

[44] Ch. Eder and J.-Ch. Faugère. A survey on signature-based algorithms for computing gröbner bases. *Journal of Symbolic Computation*, 80:719-784, 2017.

[45] M. Elkadi and B. Mourrain. *Introducction à la résolution des systèmes polynomiaux*, volume 59 of *Mathématiques et Applications*. Springer, 2007.

[46] J.-C. Faugère, P. Gaudry, L. Huot, and G. Renault. Sub-Cubic Change of Ordering for Gröbner Basis: A Probabilistic Approach. In *Proceedings ISSAC 2014*, pages 170-177. ACM, 2014.

[47] J.-Ch. Faugère. A New Efficient Algorithm for Computing Gröbner bases (F₄). *Journal of Pure and Applied Algebra*, 139(1):61-88, 1999.

[48] J.-Ch. Faugère. A New Efficient Algorithm for Computing Gröbner Bases Without Reduc-
tion to Zero (F₅). In *Proceedings of the 2002 International Symposium on Symbolic and Algebraic
Computation*, ISSAC '02, pages 75-83, New York, NY, USA, 2002. ACM.

[49] J.-Ch. Faugère. FGb: A Library for Computing Gröbner Bases. In K. Fukuda, J. v. d. Hoeven, M. Joswig, and N. Takayama, editors, *Mathematical Software - ICMS 2010*, pages 84-87, Berlin, Heidelberg, 2010. Springer.

[50] J.-Ch. Faugère, P. Gianni, D. Lazard, and T. Mora. Efficient Computation of Zero-dimensional Gröbner Bases by Change of Ordering. *J. Symbolic Comput.*, 16(4):329-344, 1993.
[51] J.-Ch. Faugère and A. Joux. Algebraic Cryptanalysis of Hidden Field Equation (HFE) Cryptosystems Using Gröbner Bases. In D. Boneh, editor, *Advances in Cryptology - CRYPTO 2003*, Lecture Notes in Computer Science, pages 44–60, Berlin, Heidelberg, 2003. Springer.

[52] J.-Ch. Faugère and C. Mou. Fast algorithm for change of ordering of zero-dimensional gröbner bases with sparse multiplication matrices. In *Proceedings of the 36th International Symposium on Symbolic and Algebraic Computation*, ISSAC '11, pages 115–122, New York, NY, USA, 2011. ACM.

[53] J.-Ch. Faugère and C. Mou. Sparse FGLM algorithms. *Journal of Symbolic Computation*, 80(3):538–569, 2017.

[54] J.-Ch. Faugère, M. Safey El Din, and Th. Verron. On the Complexity of Computing Gröbner Bases for Quasi-Homogeneous Systems. In *Proceedings of the 38th International Symposium on Symbolic and Algebraic Computation*, ISSAC '13, pages 189–196, New York, NY, USA, 2013. Association for Computing Machinery.

[55] J.-Ch. Faugère, M. Safey El Din, and Th. Verron. On the complexity of computing Gröbner bases for weighted homogeneous systems. *Journal of Symbolic Computation*, 76:107–141, 2016.

[56] J.-Ch. Faugère, P.-J. Spaenlehauer, and J. Svartz. Sparse Gröbner bases: The unmixed case. In *Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation*, ISSAC '14, pages 178–185, New York, NY, USA, 2014. ACM.

[57] J.-Ch. Faugère and J. Svartz. Gröbner bases of ideals invariant under a commutative group: The non-modular case. In *Proceedings of the 38th International Symposium on Symbolic and Algebraic Computation*, ISSAC '13, pages 347–354, New York, NY, USA, 2013. ACM.

[58] A. Ferguson and H. P. Le. Finer complexity estimates for the change of ordering of gröbner bases for generic symmetric determinantal ideals. In *Proceedings of the 2022 International Symposium on Symbolic and Algebraic Computation*, ISSAC '22, pages 399–407, New York, NY, USA, 2022. Association for Computing Machinery.

[59] P. Fortin, M. Gouicem, and S. Graillat. GPU-Accelerated Generation of Correctly Rounded Elementary Functions. *ACM Trans. Math. Softw.*, 43(3), 2016.

[60] J. García Fontán, A. Nayak, and M. Briot, S. Safey El Din. Singularity Analysis for the Perspective-Four and Five-Line Problems. *International Journal of Computer Vision*, 2022.

[61] M. R. Garey and D. S. Johnson. *Computers and Intractability; A Guide to the Theory of NP-Completeness*. W. H. Freeman & Co., USA, 1990.

[62] K. Gatermann and B. Huber. A Family of Sparse Polynomial Systems Arising in Chemical Reaction Systems. *Journal of Symbolic Computation*, 33(3):275–305, 2002.

[63] D. Gorenstein. An arithmetic theory of adjoint plane curves. *Trans. Amer. Math. Soc.*, 72:414–436, 1952.

[64] D. Henrion, J.-B. Lasserre, and C. Savorgnan. Approximate Volume and Integration for Basic Semialgebraic Sets. *SIAM Review*, 51(4):722–743, 2009.

[65] A. Hocquenghem. Codes correcteurs d'erreurs. *Chiffres*, 2:147–156, 1959.

[66] S. G. Hyun, V. Neiger, H. Rahkooy, and É. Schost. Block-Krylov techniques in the context of sparse-FGLM algorithms. *Journal of Symbolic Computation*, 98:163–191, 2020. Special Issue on Symb. and Alg. Comp.: ISSAC 2017.

[67] W. R. Inc. Mathematica, Version 13.1. Champaign, IL, 2022.
[68] C.-P. Jeannerod, V. Neiger, and G. Villard. Fast computation of approximant bases in canonical form. *Journal of Symbolic Computation*, 98:192–224, 2020. Special Issue on Symbolic and Algebraic Computation: ISSAC 2017.

[69] M. Kauers, M. Jaroschek, and F. Johansson. Ore Polynomials in Sage. In J. Gutierrez, J. Schicho, and M. Weimann, editors, *Computer Algebra and Polynomials: Applications of Algebra and Number Theory*, pages 105–125, Cham, 2015. Springer International Publishing.

[70] C. Kollreider and B. Buchberger. An improved algorithmic construction of Gröbner-bases for polynomial ideals. *SIGSAM Bull.*, 12:27–36, 1978.

[71] Ch. Koutschan. Holonomicfunctions (user's guide). Technical Report 10-01, Johannes Kepler Universitäti Linz, 2010.

[72] Y. Kuang, Y. Zheng, and K. øAström. Partial Symmetry in Polynomial Systems and Its Applications in Computer Vision. In *2014 IEEE Conference on Computer Vision and Pattern Recognition*, pages 438–445, 2014.

[73] P. Lairez and M. Safey El Din. Computing the dimension of real algebraic sets. In *Proceedings of the 46th International Symposium on Symbolic and Algebraic Computation*, ISSAC '21, pages 257–264, New York, NY, USA, 2021. Association for Computing Machinery.

[74] D. Lazard. Gröbner bases, Gaussian elimination and resolution of systems of algebraic equations. In *Computer algebra (London, 1983)*, volume 162 of *Lecture Notes in Comput. Sci.*, pages 146–156. Springer, Berlin, 1983.

[75] V. Levandovskyy. *Non-commutative Computer Algebra for polynomial algebras: Gröbner bases, applications and implementation*. PhD thesis, Technische Universität Kaiserslautern, 2005.

[76] F. S. Macaulay. Modern algebra and polynomial ideals. *Mathematical Proceedings of the Cambridge Philosophical Society*, 30:27–46, 1934.

[77] J. L. Massey. Shift-register synthesis and BCH decoding. *IEEE Trans. Inform. Theory*, 11:1522–127, 1969.

[78] S.J. Matsubara-Heo and S. Telen. Twisted cohomology and likelihood ideals, 2023.

[79] H. M. Möller and F. Mora. Upper and lower bounds for the degree of groebner bases. In J. Fitch, editor, *EUROSAM 84*, pages 172–183, Berlin, Heidelberg, 1984. Springer Berlin Heidelberg.

[80] G. Moreno-Socías. Degrevlex Gröbner bases of generic complete intersections. *Journal of Pure and Applied Algebra*, 180(3):263–283, 2003.

[81] B. Mourrain. Fast algorithm for border bases of artinian gorenstein algebras. In *Proceedings of the 2017 ACM on International Symposium on Symbolic and Algebraic Computation*, ISSAC '17, pages 333–340, New York, NY, USA, 2017. ACM.

[82] S. Naldi and V. Neiger. A divide-and-conquer algorithm for computing gröbner bases of syzygies in finite dimension. In *Proceedings of the 45th International Symposium on Symbolic and Algebraic Computation*, ISSAC '20, pages 380–387, New York, NY, USA, 2020. Association for Computing Machinery.

[83] V. Neiger and É. Schost. Computing syzygies in finite dimension using fast linear algebra. *Journal of Complexity*, 60:101502, 2020.

[84] J. Nie and K. Ranestad. Algebraic degree of polynomial optimization. *SIAM J. Optim.*, 20(1):485–502, 2009.

[85] S. Odake and R. Sasaki. Exactly solvable quantum mechanics and infinite families of multi-indexed orthogonal polynomials. *Physics Letters B*, 702(2):164–170, 2011.
[86] B. Parisse and R. De Graeve. Giac/Xcas, version 1.5.0, 2018. http://www-fourier.univ-grenoble-alpes.fr/~parisse/giac.html.

[87] B. Pascual-Escudero, A. Nayak, S. Briot, O. Kermorgant, Ph. Martinet, M. Safey El Din, and F. Chaumette. Complete Singularity Analysis for the Perspective-Four-Point Problem. *International Journal of Computer Vision*, 129(4):1217-1237, 2021.

[88] C. Pernet and A. Storjohann. Faster Algorithms for the Characteristic Polynomial. In *Proceedings ISSAC 2007*, pages 307-314. ACM, 2007.

[89] C. Pernet and A. Storjohann. Frobenius form in expected matrix multiplication time over sufficiently large fields. unpublished report, 2007.

[90] J. Rabinowitsch. Zum Hilbertschen Nullstellensatz. *Mathematische Annalen*, 102:520-520, 1930.

[91] M. Raghavan and B. Roth. Solving Polynomial Systems for the Kinematic Analysis and Synthesis of Mechanisms and Robot Manipulators. *Journal of Mechanical Design*, 117 (B):71-79, 1995.

[92] M. Safey El Din. Computing Sampling Points on a Singular Real Hypersurface using Lagrange's System. Research Report RR-5464, INRIA, 2005.

[93] S. Sakata. Finding a minimal set of linear recurring relations capable of generating a given finite two-dimensional array. *J. Symbolic Comput.*, 5(3):321-337, 1988.

[94] S. Sakata. *N*-dimensional Berlekamp-Massey algorithm for multiple arrays and construction of multivariate polynomials with preassigned zeros. In T. Mora, editor, *Applied Algebra, Algebraic Algorithms and Error-Correcting Codes*, volume 357 of *Lecture Notes in Computer Science*, pages 356-376. Springer Berlin Heidelberg, 1989.

[95] S. Sakata. Extension of the Berlekamp-Massey algorithm to *N* Dimensions. *Inform. and Comput.*, 84(2):207-239, 1990.

[96] S. Sakata. Decoding binary 2-D cyclic codes by the 2-D Berlekamp-Massey algorithm. *IEEE Trans. Inform. Theory*, 37(4):1200-1203, 1991.

[97] S. Sakata. The bms algorithm. In M. Sala, S. Sakata, T. Mora, C. Traverso, and L. Perret, editors, *Gröbner Bases, Coding, and Cryptography*, pages 143–163. Springer Berlin Heidelberg, Berlin, Heidelberg, 2009.

[98] B. Salvy. Linear Differential Equations as a Data Structure. *Foundations of Computational Mathematics*, 19:1071-1112, 2019.

[99] B. Salvy and P. Zimmermann. GFUN: A Maple Package for the Manipulation of Generating and Holonomic Functions in One Variable. *ACM Trans. Math. Softw.*, 20(2):163-177, jun 1994.

[100] T. Sauer. Prony's method in several variables: Symbolic solutions by universal interpolation. *Journal of Symbolic Computation*, 84:95-112, 2018.

[101] A. K. Steel. Direct solution of the (11, 9, 8)-MinRank problem by the block Wiedemann algorithm in magma with a tesla GPU. In *Proceedings of the 2015 International Workshop on Parallel Symbolic Computation*, PASCO 2015, Bath, United Kingdom, July 10-12, 2015, pages 2-6. ACM, 2015.

[102] A. Storjohann. *Algorithms for Matrix Canonical Forms*. Phd thesis, Swiss Federal Institute of Technology - ETH, 2000.

[103] The Sage Developers. *SageMath, the Sage Mathematics Software System (Version 9.1)*, 2020. https://www.sagemath.org.
[104] C. Traverso. Hilbert Functions and the Buchberger Algorithm. *Journal of Symbolic Computation*, 22(4):355-376, 1996.

[105] Th. Verron. On the computation of Gröbner bases for matrix-weighted homogeneous systems, 2022.

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

This habilitation thesis deals with polynomial system solving through Gröbner bases computations.
It focuses on the link between multivariate polynomials and linear recurrence relations satisfied by
a multi-indexed sequence for computing Gröbner bases.

Our contributions mainly lie on the theoretical and practical aspects on these Gröbner bases computations. First, we present `msolve`, a new open source C library, for solving polynomial systems using Gröbner bases. Second, we describe new algorithms and complexity estimates for computing Gröbner bases either for a total degree order or the lexicographic one. Then, we present linear algebras-based and polynomial-division-based algorithms for guessing linear recurrences with constant or polynomial coefficients, in generic and structured situations.

Finally, we detail our research project for the forthcoming years on these aspects.

Résumé

Cette thèse d'habilitation traite de la résolution de systèmes polynomiaux *via* le calcul de bases de Gröbner. Elle se concentre sur le lien entre les polynômes multivariés et les relations de récurrence linéaires satisfaites par une suite multi-indexée pour calculer des bases de Gröbner.

Nos contributions portent principalement sur les aspects théoriques et pratiques de ces calculs de bases de Gröbner. Tout d'abord, nous présentons `msolve`, une nouvelle bibliothèque C `open source`, pour la résolution de systèmes polynomiaux en utilisant les bases de Gröbner. Ensuite, nous décrivons de nouveaux algorithmes et donnons des estimations de complexité pour le calcul des bases de Gröbner soit pour un ordre de degré total, soit pour l'ordre lexicographique. Ensuite, nous présentons des algorithmes basés sur l'algèbre linéaire et sur la division de polynômes pour deviner les récurrences linéaires à coefficients constants ou polynomiaux, dans des situations génériques et structurées.

Enfin, nous détaillons notre projet de recherche pour les années à venir sur ces aspects.