×

zbMATH — the first resource for mathematics

Multilinear polynomial systems: root isolation and bit complexity. (English) Zbl 07312668
Summary: We exploit structure in polynomial system solving by considering polynomials that are linear in subsets of the variables. We focus on algorithms and their Boolean complexity for computing isolating hyperboxes for all the isolated complex roots of well-constrained, unmixed systems of multilinear polynomials based on resultant methods. We enumerate all expressions of the multihomogeneous (or multigraded) resultant of such systems as a determinant of Sylvester-like matrices, aka generalized Sylvester matrices. We construct these matrices by means of Weyman homological complexes, which generalize the Cayley-Koszul complex. The computation of the determinant of the resultant matrix is the bottleneck for the overall complexity. We exploit the quasi-Toeplitz structure to reduce the problem to efficient matrix-vector multiplication, which corresponds to multivariate polynomial multiplication, by extending the seminal work on Macaulay matrices of Canny, Kaltofen, and Yagati Canny et al. (1989) to the multihomogeneous case. We compute a rational univariate representation of the roots, based on the primitive element method. In the case of 0-dimensional systems we present a Monte Carlo algorithm with probability of success \(1 - 1 / 2^\varrho \), for a given \(\varrho \geq 1\), and bit complexity \(\widetilde{\mathcal{O}}_B( n^2 D^{4 + \epsilon}( n^{N + 1} + \tau) + n D^{2 + \epsilon} \varrho(D + \varrho))\) for any \(\epsilon > 0\), where \(n\) is the number of variables, \(D\) equals the multilinear Bézout bound, \(N\) is the number of variable subsets, and \(\tau\) is the maximum coefficient bitsize. We present an algorithmic variant to compute the isolated roots of overdetermined and positive-dimensional systems. Thus our algorithms and complexity analysis apply in general with no assumptions on the input.
MSC:
68Qxx Theory of computing
68Wxx Algorithms in computer science
11Yxx Computational number theory
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alonso, M. E.; Becker, E.; Roy, M.-F.; Wörmann, T., Algorithms in algebraic geometry and applications, (Zeros, Multiplicities, and Idempotents for Zero-Dimensional Systems (1996)), 1-15
[2] Arnold, A.; Roche, D. S., Output-sensitive algorithms for sumset and sparse polynomial multiplication, (Proc. ACM ISSAC (2015)), 29-36 · Zbl 1346.68266
[3] Bender, M.; Faugère, J.-C.; Mantzaflaris, A.; Tsigaridas, E., Bilinear systems with two supports: Koszul resultant matrices, eigenvalues, and eigenvectors, (Proc. of Int’l Symposium on Symbolic and Algebraic Computation (ISSAC’18) (2018), ACM), 63-70 · Zbl 1467.13056
[4] Bostan, A.; Lecerf, G.; Schost, E., Tellegen’s principle into practice, (Proc. ISSAC (2003)), 37-44 · Zbl 1072.68649
[5] Bostan, A.; Salvy, B.; Schost, É., Fast algorithms for zero-dimensional polynomial systems using duality, Appl. Algebra Eng. Commun. Comput., 14, 4, 239-272 (2003) · Zbl 1058.68122
[6] Bouzidi, Y.; Lazard, S.; Moroz, G.; Pouget, M.; Rouillier, F.; Sagraloff, M., Improved algorithms for solving bivariate systems via Rational Univariate Representations (June 2015), Inria, Tech. Report
[7] Canny, J., Some algebraic and geometric computations in PSPACE, (Proc. 20th STOC (1988), ACM), 460-467
[8] Canny, J., Generalised characteristic polynomials, J. Symb. Comput., 9, 3, 241-250 (1990) · Zbl 0704.12004
[9] Canny, J. F.; Kaltofen, E.; Yagati, L., Solving systems of nonlinear polynomial equations faster, (Proc. ACM ISSAC (1989)), 121-128
[10] Cox, D.; Materov, E., Tate resolutions for Segre embeddings, Algebra Number Theory, 2, 5, 523-550 (2008) · Zbl 1168.13009
[11] Dahan, X.; Schost, E., Sharp estimates for triangular sets, (Proc. ACM ISSAC (2004)), 103-110 · Zbl 1134.13308
[12] D’Andrea, C.; Dickenstein, A., Explicit formulas for the multivariate resultant, J. Pure Appl. Algebra, 164, 1-2, 59-86 (2001) · Zbl 1066.14061
[13] D’Andrea, C.; Emiris, I. Z., Computing sparse projection operators, (Symbolic Computation: Solving Equations in Algebra, Geometry, and Engineering. Symbolic Computation: Solving Equations in Algebra, Geometry, and Engineering, Contemporary Mathematics, vol. 286 (2001), AMS: AMS Providence), 121-140 · Zbl 1013.14017
[14] Dickenstein, A.; Emiris, I. Z., Multihomogeneous resultant formulae by means of complexes, J. Symb. Comput., 36, 3, 317-342 (2003) · Zbl 1095.13547
[15] Eisenbud, D.; Schreyer, F.-O.; Weyman, J., Resultants and Chow forms via exterior syzygies, J. Am. Math. Soc., 16, 3, 537-579 (2003) · Zbl 1069.14019
[16] Emiris, I. Z.; Mantzaflaris, A., Multihomogeneous resultant formulae for systems with scaled support, J. Symb. Comput., 47, 7, 820-842 (2012) · Zbl 1258.65038
[17] Emiris, I. Z.; Mantzaflaris, A.; Tsigaridas, E., On the bit complexity of solving bilinear polynomial systems, (Proc. of Int’l Symposium on Symbolic and Algebraic Computation (ISSAC’16) (2016), ACM: ACM New York, NY, USA), 215-222 · Zbl 1360.13066
[18] Emiris, I. Z.; Mourrain, B.; Tsigaridas, E. P., The DMM bound: multivariate (aggregate) separation bounds, (Proc. ACM ISSAC (2010)), 243-250 · Zbl 1321.68528
[19] Emiris, I. Z.; Mourrain, B.; Tsigaridas, E., Separation bounds for polynomial systems, J. Symb. Comput., 101, 128-151 (2019) · Zbl 1446.68202
[20] Emiris, I. Z.; Pan, V. Y., Symbolic and numeric methods for exploiting structure in constructing resultant matrices, J. Symb. Comput., 33, 4, 393-413 (Apr. 2002)
[21] Emiris, I. Z.; Pan, V. Y., Improved algorithms for computing determinants and resultants, J. Complex., 21, 1, 43-71 (Feb. 2005)
[22] Emiris, I. Z.; Vidunas, R., Root counts of semi-mixed systems, and an application to counting Nash equilibria, (Proc. ACM ISSAC (2014), ACM Press: ACM Press Kobe, Japan), 154-161 · Zbl 1325.68275
[23] Faugere, J.-C.; El Din, M. S.; Spaenlehauer, P.-J., Gröbner bases of bihomogeneous ideals generated by polynomials of bidegree (1, 1): algorithms and complexity, J. Symb. Comput., 46, 4, 406-437 (2011) · Zbl 1226.13017
[24] Faugère, J.-C.; Levy-Dit-Vehel, F.; Perret, L., Cryptanalysis of minrank, (Advances in Cryptology (2008), Springer), 280-296 · Zbl 1183.94033
[25] Faugère, J.-C.; Safey El Din, M.; Spaenlehauer, P.-J., Gröbner bases of bihomogeneous ideals generated by polynomials of bidegree (1, 1): algorithms and complexity, J. Symb. Comput., 46, 406-437 (2011) · Zbl 1226.13017
[26] Gelfand, I.; Kapranov, M.; Zelevinsky, A., Discriminants, Resultants and Multidimensional Determinants (1994), Birkhäuser: Birkhäuser Boston · Zbl 0827.14036
[27] Giusti, M.; Heintz, J., La détermination des points isolés et de la dimension d’une variété algébrique peut se faire en temps polynomial, (Proc. Int. Meeting on Commutative Algebra. Proc. Int. Meeting on Commutative Algebra, Cortona (1993)) · Zbl 0829.14029
[28] Giusti, M.; Lecerf, G.; Salvy, B., A Gröbner free alternative for polynomial system solving, J. Complex., 17, 1, 154-211 (2001) · Zbl 1003.12005
[29] Hartshorne, R., Algebraic Geometry (1977), Springer: Springer New York · Zbl 0367.14001
[30] Higham, N. J., Accuracy and Stability of Numerical Algorithms (2002), Society for Industrial and Applied Mathematics: Society for Industrial and Applied Mathematics Philadelphia · Zbl 1011.65010
[31] Hoeven, J.v.d.; Lecerf, G., On the bit-complexity of sparse polynomial multiplication, J. Symb. Comput., 50, 227-254 (2013) · Zbl 1261.65017
[32] Jeronimo, G.; Sabia, J., Computing multihomogeneous resultants using straight-line programs, J. Symb. Comput., 42, 1-2, 218-235 (2007) · Zbl 1207.65056
[33] Joux, A., A new index calculus algorithm with complexity \(L(1 / 4 + o(1))\) in small characteristic, (Selected Areas in Cryptography-SAC 2013 (2014), Springer), 355-379 · Zbl 1362.94034
[34] Kaltofen, E. L.; Nehring, M., Supersparse black box rational function interpolation, (Proceedings of the 36th International Symposium on Symbolic and Algebraic Computation. Proceedings of the 36th International Symposium on Symbolic and Algebraic Computation, ISSAC’11 (2011), ACM: ACM New York, NY, USA), 177-186 · Zbl 1323.68606
[35] Kaltofen, E.; Villard, G., On the complexity of computing determinants, Comput. Complex., 13, 3-4, 91-130 (2005) · Zbl 1061.68185
[36] Mantzaflaris, A.; Mourrain, B., Deflation and certified isolation of singular zeros of polynomial systems, (Proc. ACM ISSAC (2011)), 249-256 · Zbl 1323.65054
[37] Mantzaflaris, A.; Mourrain, B., Singular zeros of polynomial systems, (Dokken, T.; Muntingh, G., Advances in Shapes, Geometry, and Algebra. Advances in Shapes, Geometry, and Algebra, Geometry and Computing, vol. 10 (2014), Springer), 77-103 · Zbl 1331.65074
[38] Mantzaflaris, A.; Schost, E.; Tsigaridas, E., Sparse rational univariate representation, (Proceedings of the 2017 ACM on International Symposium on Symbolic and Algebraic Computation. Proceedings of the 2017 ACM on International Symposium on Symbolic and Algebraic Computation, ISSAC’17 (2017), ACM: ACM New York, NY, USA), 301-308 · Zbl 1458.68285
[39] McCoy, N., On the resultant of a system of forms homogeneous in each of several sets of variables, Trans. Am. Math. Soc., 35, 1, 215-233 (1933) · JFM 59.0132.01
[40] Mehrabi, E.; Schost, É., A softly optimal Monte Carlo algorithm for solving bivariate polynomial systems over the integers, J. Complex., 34, 78-128 (2016) · Zbl 1352.68299
[41] Muir, T., The resultant of a set of lineo-linear equations, Proc. R. Soc., South Africa, 2, 1, 373-380 (1910)
[42] Ourivski, A. V.; Johansson, T., New technique for decoding codes in the rank metric and its cryptography applications, Probl. Inf. Transm., 38, 3, 237-246 (2002) · Zbl 1026.94023
[43] Pan, V. Y., Univariate polynomials: nearly optimal algorithms for numerical factorization and root-finding, J. Symb. Comput., 33, 5, 701-733 (2002) · Zbl 1004.65061
[44] Pan, V. Y.; Tsigaridas, E., Accelerated approximation of the complex roots and factors of a univariate polynomial, Theor. Comput. Sci., 681, 138-145 (2017) · Zbl 1375.65066
[45] Pan, V. Y.; Tsigaridas, E., Nearly optimal computations with structured matrices, Theor. Comput. Sci., 681, 117-137 (2017) · Zbl 1375.65047
[46] Rouillier, F., Solving zero-dimensional systems through the rational univariate representation, Appl. Algebra Eng. Commun. Comput., 9, 5, 433-461 (1999) · Zbl 0932.12008
[47] Safey El Din, M.; Schost, É., Polar varieties and computation of one point in each connected component of a smooth real algebraic set, (Proc. ACM ISSAC (2003)), 224-231 · Zbl 1072.68693
[48] Safey El Din, M.; Schost, É., Bit complexity for multi-homogeneous polynomial system solving – application to polynomial minimization, J. Symb. Comput., 87, 176-206 (2018) · Zbl 1391.13056
[49] Spaenlehauer, P.-J., Solving multi-homogeneous and determinantal systems: algorithms, complexity, applications (Oct. 2012), Université Pierre et Marie Curie (Univ. Paris 6), Thesis
[50] Sturmfels, B.; Zelevinsky, A., Multigraded resultants of Sylvester type, J. Algebra, 163, 1, 115-127 (1994) · Zbl 0813.13018
[51] Sylvester, J., On the degree and weight of the resultant of a multipartite system of equations, Proc. R. Soc. Lond., 12, 674-676 (1862)
[52] von zur Gathen, J.; Gerhard, J., Modern Computer Algebra (2013), Cambridge University Press · Zbl 1277.68002
[53] Weyman, J., Calculating discriminants by higher direct images, Trans. Am. Math. Soc., 343, 1, 367-389 (1994) · Zbl 0823.14040
[54] Weyman, J., Cohomology of Vector Bundles and Syzygies, Cambridge Tracts in Mathematics, vol. 149 (2003), Cambridge Univ. Press · Zbl 1075.13007
[55] Weyman, J.; Zelevinsky, A., Determinantal formulas for multigraded resultants, J. Algebraic Geom., 3, 4, 569-597 (1994) · Zbl 0816.13007
[56] Yap, C.-K., Fundamental Problems of Algorithmic Algebra (2000), Oxford University Press: Oxford University Press New York · Zbl 0999.68261
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.