×

zbMATH — the first resource for mathematics

Block-Krylov techniques in the context of sparse-FGLM algorithms. (English) Zbl 1446.68203
Summary: Consider a zero-dimensional ideal \(I\) in \(\mathbb{K} [X_1, \ldots, X_n]\). Inspired by Faugère and Mou’s Sparse FGLM algorithm, we use Krylov sequences based on multiplication matrices of \(I\) in order to compute a description of its zero set by means of univariate polynomials.
Steel recently showed how to use Coppersmith’s block-Wiedemann algorithm in this context; he describes an algorithm that can be easily parallelized, but only computes parts of the output in this manner. Using generating series expressions going back to work of Bostan, Salvy, and Schost, we show how to compute the entire output for a small overhead, without making any assumption on the ideal \(I\) other than it having dimension zero. We then propose a refinement of this idea that partially avoids the introduction of a generic linear form. We comment on experimental results obtained by an implementation based on the C++ libraries Eigen, LinBox and NTL.
MSC:
68W30 Symbolic computation and algebraic computation
13P10 Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)
13P15 Solving polynomial systems; resultants
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alonso, M. E.; Becker, E.; Roy, M.-F.; Wörmann, T., Zeroes, multiplicities and idempotents for zero-dimensional systems, (MEGA’94. MEGA’94, Progress in Mathematics, vol. 142 (1996), Birkhäuser), 1-15 · Zbl 0879.14033
[2] Bardet, M.; Faugère, J.-C.; Salvy, B., On the complexity of the F5 Gröbner basis algorithm, J. Symb. Comput., 70, 49-70 (2015) · Zbl 1328.68319
[3] Becker, E.; Mora, T.; Marinari, M.; Traverso, C., The shape of the Shape Lemma, (ISSAC’94 (1994), ACM), 129-133 · Zbl 0925.13006
[4] Becker, E.; Wörmann, T., Radical computations of zero-dimensional ideals and real root counting, Math. Comput. Simul., 42, 4-6, 561-569 (1996) · Zbl 1037.68540
[5] Beckermann, B.; Labahn, G., A uniform approach for the fast computation of matrix-type Padé approximants, SIAM J. Matrix Anal. Appl., 15, 3, 804-823 (1994) · Zbl 0805.65008
[6] Bosma, W.; Cannon, J.; Playoust, C., The Magma algebra system. I. The user language, J. Symb. Comput., 24, 3-4, 235-265 (1997) · Zbl 0898.68039
[7] Bostan, A.; Flajolet, P.; Salvy, B.; Schost, É., Fast computation of special resultants, J. Symb. Comput., 41, 1, 1-29 (2006) · Zbl 1121.13037
[8] Bostan, A.; Salvy, B.; Schost, É., Fast algorithms for zero-dimensional polynomial systems using duality, Appl. Algebra Eng. Commun. Comput., 14, 239-272 (2003) · Zbl 1058.68122
[9] Brent, R. P.; Gustavson, F. G.; Yun, D. Y.Y., Fast solution of Toeplitz systems of equations and computation of Padé approximants, J. Algorithms, 1, 3, 259-295 (1980) · Zbl 0475.65018
[10] Coppersmith, D., Solving homogeneous linear equations over \(GF(2)\) via block Wiedemann algorithm, Math. Comput., 62, 205, 333-350 (1994) · Zbl 0805.65046
[11] Faugère, J.-C., A new efficient algorithm for computing Gröbner bases without reductions to zero (F5), (ISSAC’02 (2002), ACM), 75-83 · Zbl 1072.68664
[12] Faugère, J.-C.; Gaudry, P.; Huot, L.; Renault, G., Polynomial systems solving by fast linear algebra (2013)
[13] Faugère, J.-C.; Gaudry, P.; Huot, L.; Renault, G., Sub-cubic change of ordering for Gröbner basis: a probabilistic approach, (ISSAC’14 (2014), ACM), 170-177 · Zbl 1325.68277
[14] Faugère, J.-C.; Gianni, P.; Lazard, D.; Mora, T., Efficient computation of zero-dimensional Gröbner bases by change of ordering, J. Symb. Comput., 16, 4, 329-344 (1993) · Zbl 0805.13007
[15] Faugère, J.-C.; Mou, C., Sparse FGLM algorithms, J. Symb. Comput., 80, 8, 538-569 (2017) · Zbl 1404.13031
[16] Faugère, J.-C.; Safey El Din, M.; Spaenlehauer, P.-J., On the complexity of the generalized MinRank problem, J. Symb. Comput., 30-58 (2013) · Zbl 1302.13026
[17] Gianni, P.; Mora, T., Algebraic solution of systems of polynomial equations using Gröbner bases, (AAECC’5. AAECC’5, Lecture Notes in Comput. Sci., vol. 356 (1989), Springer), 247-257
[18] Giorgi, P.; Jeannerod, C.-P.; Villard, G., On the complexity of polynomial matrix computations, (ISSAC’03 (2003), ACM), 135-142 · Zbl 1072.68708
[19] Giorgi, P.; Lebreton, R., Online order basis algorithm and its impact on the block Wiedemann algorithm, (ISSAC’14 (2014), ACM), 202-209 · Zbl 1325.68281
[20] Guennebaud, G.; Jacob, B., Eigen (2018), version 3.3.7
[21] Kailath, T., Linear Systems (1980), Prentice-Hall · Zbl 0458.93025
[22] Kaltofen, E., Analysis of Coppersmith’s block Wiedemann algorithm for the parallel solution of sparse linear systems, Math. Comput., 64, 210, 777-806 (1995) · Zbl 0828.65035
[23] Kaltofen, E.; Villard, G., On the complexity of computing determinants, (ISSAC’01 (2001), ACM), 13-27 · Zbl 1012.65505
[24] Kaltofen, E.; Villard, G., On the complexity of computing determinants, Comput. Complex., 13, 3-4, 91-130 (2004) · Zbl 1061.68185
[25] Keller-Gehrig, W., Fast algorithms for the characteristic polynomial, Theor. Comput. Sci., 36, 2-3, 309-317 (1985) · Zbl 0565.68041
[26] LaMacchia, B. A.; Odlyzko, A. M., Solving large sparse linear systems over finite fields, (Adv. in Cryptography, Crypto ’90. Adv. in Cryptography, Crypto ’90, Lectures Notes in Computer Science, vol. 537 (1990), Springer), 109-133 · Zbl 0786.65028
[27] Macaulay, F. S., The Algebraic Theory of Modular Systems (1916), Cambridge University Press · JFM 46.0167.01
[28] Marinari, M. G.; Möller, H. M.; Mora, T., On multiplicities in polynomial system solving, Trans. Am. Math. Soc., 348, 8, 3283-3321 (1996) · Zbl 0910.13009
[29] Moreno-Socías, G., Autour de la fonction de Hilbert-Samuel (escaliers d’idéaux polynomiaux) (1991), École Polytechnique, Ph.D. thesis
[30] Morgan, A., Solving Polynomial Systems Using Continuation for Engineering and Scientific Problems (1988), Prentice-Hall
[31] Mourrain, B., Isolated points, duality and residues, J. Pure Appl. Algebra, 117/118, 469-493 (1997) · Zbl 0896.13020
[32] Neiger, V., Bases of Relations in One or Several Variables: Fast Algorithms and Applications (Nov. 2016), École Normale Supérieure de Lyon, Ph.D. thesis
[33] Neiger, V.; Rahkooy, H.; Schost, É., Algorithms for zero-dimensional ideals using linear recurrent sequences, (CASC’17 (2017), Springer), 313-328 · Zbl 1455.13047
[34] Poteaux, A.; Schost, E., On the complexity of computing with zero-dimensional triangular sets, J. Symb. Comput., 50, 110-138 (2013) · Zbl 1332.68300
[35] Rouillier, F., Solving zero-dimensional systems through the Rational Univariate Representation, Appl. Algebra Eng. Commun. Comput., 9, 5, 433-461 (1999) · Zbl 0932.12008
[36] Sakata, S., Extension of the Berlekamp-Massey algorithm to N dimensions, Inf. Comput., 84, 2, 207-239 (1990) · Zbl 0692.68024
[37] Shoup, V., Fast construction of irreducible polynomials over finite fields, J. Symb. Comput., 17, 5, 371-391 (1994) · Zbl 0815.11059
[38] Shoup, V., Efficient computation of minimal polynomials in algebraic extensions of finite fields, (ISSAC’99 (1999), ACM), 53-58
[39] Shoup, V., NTL: a library for doing number theory (2018), version 11.3.2
[40] Steel, A., Direct solution of the (11, 9,8)-MinRank problem by the block Wiedemann algorithm in Magma with a Tesla GPU, (PASCO’15 (2015), ACM), 2-6
[41] Storjohann, A., High-order lifting and integrality certification, J. Symb. Comput., 36, 613-648 (2003) · Zbl 1059.15020
[42] FFLAS-FFPACK: Finite Field Linear Algebra Subroutines / Package (2019), version 2.3.2
[43] Linbox: linear algebra over black-box matrices (2018), version 1.5.3
[44] Turner, W. J., Black Box Linear Algebra with the LINBOX Library (2002), North Carolina State University, Ph.D. thesis
[45] Van Barel, M.; Bultheel, A., A general module theoretic framework for vector M-Padé and matrix rational interpolation, Numer. Algorithms, 3, 451-462 (1992) · Zbl 0780.41014
[46] Villard, G., Further analysis of Coppersmith’s block Wiedemann algorithm for the solution of sparse linear systems, (ISSAC’97 (1997), ACM), 32-39 · Zbl 0917.65041
[47] Villard, G., A Study of Coppersmith’s Block Wiedemann Algorithm Using Matrix Polynomials (1997), Tech. rep., LMC-IMAG, Report 975 IM · Zbl 0917.65041
[48] von zur Gathen, J.; Gerhard, J., Modern Computer Algebra (2013), Cambridge University Press: Cambridge University Press Cambridge · Zbl 1277.68002
[49] Wiedemann, D., Solving sparse linear equations over finite fields, IEEE Trans. Inf. Theory, IT-32, 54-62 (1986) · Zbl 0607.65015
[50] Wolovich, W. A., Linear Multivariable Systems, Applied Mathematical Sciences, vol. 11 (1974), Springer-Verlag: Springer-Verlag New-York · Zbl 0291.93002
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.