Rational univariate reduction via toric resultants. (English) Zbl 1174.13041
Summary: We describe algorithms for solving a given system of multivariate polynomial equations via the Rational Univariate Reduction (RUR). We compute the RUR from the toric resultant of the input system. Our algorithms derandomize several of the choices made in similar prior algorithms. We also propose a new derandomized algorithm for solving an overdetermined system. Finally, we analyze the computational complexity of the algorithm, and discuss its implementation and performance.
MSC:
| 13P10 | Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) |
| 14Q99 | Computational aspects in algebraic geometry |
| 14M25 | Toric varieties, Newton polyhedra, Okounkov bodies |
Keywords:
polynomial system solving; rational univariate representation; geometric resolution; toric (or sparse) resultantReferences:
| [1] | Aubry, P.; Rouillier, F.; El Din, M. S., Real solving for positive dimensional systems, Journal of Symbolic Computation, 34, 6, 543-560 (2002) · Zbl 1046.14031 |
| [2] | Basu, S.; Pollack, R.; Roy, M.-F., Algorithms in Real Algebraic Geometry (2003), Springer · Zbl 1031.14028 |
| [3] | Bernstein, D. N., The number of roots of a system of equations, Functional Analysis and its Applications, 9, 2, 183-185 (1975) · Zbl 0328.32001 |
| [4] | Blum, L.; Cucker, F.; Shub, M.; Smale, S., Complexity and Real Computation (1997), Springer · Zbl 0948.68068 |
| [5] | Canny, J., Some algebraic and geometric computations in pspace, (Proc. of 20th Annual Symposium on Theory of Computation (1988), ACM), 460-467 |
| [6] | Canny, J. F., Generalized characteristic polynomials, Journal of Symbolic Computation, 9, 3, 241-250 (1990) · Zbl 0704.12004 |
| [7] | Canny, J. F.; Emiris, I. Z., An efficient algorithm for the sparse mixed resultant, (Proc. of 10th AAECC. Proc. of 10th AAECC, LNCS, vol. 673 (1993), Springer), 89-104 · Zbl 0789.65034 |
| [8] | Canny, J. F.; Emiris, I. Z., A subdivision-based algorithm for the sparse resultant, Journal of ACM, 47, 3, 417-451 (2000) · Zbl 1094.65508 |
| [9] | Cox, D., What is a toric variety?, (Goldman, R.; Krasauskas, R., Topics in Algebraic Geometry and Geometric Modeling. Topics in Algebraic Geometry and Geometric Modeling, Contemporary Mathematics, vol. 334 (2003), AMS), 203-223 · Zbl 1038.14021 |
| [10] | Cox, D.; Little, J.; O’Shea, D., Ideals, Varieties, and Algorithms (1996), Springer · Zbl 0861.13012 |
| [11] | Cox, D.; Little, J.; O’Shea, D., Using Algebraic Geometry (1998), Springer · Zbl 0920.13026 |
| [12] | D’Andrea, C., Macaulay style formulas for sparse resultants, Transactions of the AMS, 354, 7, 2595-2629 (2002) · Zbl 0987.13019 |
| [13] | D’Andrea, C.; Emiris, I. Z., Computing sparse projection operators, (Green, E. L.; etal., Symbolic Computation: Solving equations in Algebra, Geometry and Engineering. Symbolic Computation: Solving equations in Algebra, Geometry and Engineering, Contemporary Mathematics, vol. 286 (2001), AMS), 121-139 · Zbl 1013.14017 |
| [14] | D’Andrea, C.; Emiris, I. Z., Sparse resultant perturbation, (Joswig, M.; Takayama, N., Algebra, Geometry, and Software (2003), Springer), 93-107 · Zbl 1027.65054 |
| [15] | Dickenstein, A.; Emiris, I. Z., Multihomogeneous resultant formulae by means of complexes, Journal of Symbolic Computation, 36, 3-4, 317-342 (2003) · Zbl 1095.13547 |
| [16] | Din, M. S.E.; Shost, E., Properness defects of projections and computation of at least one point in each connected component of a real algebraic set, Discrete and Computational Geometry, 32, 3, 417-430 (2004) · Zbl 1067.14057 |
| [17] | Dykstra, P.C., Muuss, M.J., 1989. The BRL-CAD package an overview. Tech. rep., Advanced Computer Systesms Team, Ballistics Research Laboratory, Aberdeen Proving Ground, MD http://ftp.arl.mil/brlcad/; Dykstra, P.C., Muuss, M.J., 1989. The BRL-CAD package an overview. Tech. rep., Advanced Computer Systesms Team, Ballistics Research Laboratory, Aberdeen Proving Ground, MD http://ftp.arl.mil/brlcad/ |
| [18] | Emiris, I. Z., On the complexity of sparse elimination, Journal of Complexity, 12, 2, 134-166 (1996) · Zbl 0935.12008 |
| [19] | Emiris, I. Z., A complete implementation for computing general dimensional convex hulls, International Journal of Computational Geometry and Applications, 8, 2, 223-253 (1998) · Zbl 1035.68529 |
| [20] | Emiris, I. Z., Enumerating a subset of the integer points inside a Minkowski sum, Computational Geometry, 22, 1-3, 143-166 (2002) · Zbl 1016.68143 |
| [21] | Emiris, I. Z., Discrete geometry for algebraic elimination, (Joswig, M.; Takayama, N., Algebra, Geometry, and Software (2003), Springer), 77-91 · Zbl 1027.65065 |
| [22] | Emiris, I. Z.; Canny, J. F., Efficient incremental algorithm for the sparse resultant and the mixed volume, Journal of Symbolic Computation, 20, 2, 117-149 (1995) · Zbl 0843.68036 |
| [23] | Emiris, I. Z.; Pan, Y. V., Symbolic and numeric methods for exploiting structure in constructing resultant matrices, Journal of Symbolic Computation, 33, 4, 393-413 (2002) · Zbl 1017.65049 |
| [24] | Gelfand, I. M.; Kapranov, M. M.; Zelevinsky, A. V., Discriminants, Resultants, and Multidimensional Determinants (1994), Birkhauser · Zbl 0827.14036 |
| [25] | Giusti, M.; Lecerf, G.; Salvy, B., A Gröbner free alternative for polynomial system solving, Journal of Complexity, 17, 1, 154-211 (2001) · Zbl 1003.12005 |
| [26] | Gonzalez-Vega, L., A subresultant theory for multivariate polynomials, (Proc. of ISSAC ’91 (1991), ACM), 79-85 · Zbl 0921.13017 |
| [27] | Gonzalez-Vega, L.; Rouillier, F.; Roy, M.-F., Symbolic recipes for polynomial system solving, (Cohen, A. M.; Cuypers, H.; Sterk, H., Some Tapas of Computer Algebra. Some Tapas of Computer Algebra, Algorithms and Computation in Mathematics, vol. 4 (1999), Springer), 34-65 · Zbl 0966.13020 |
| [28] | Hong, H.; Minimair, M., Sparse resultant of composed polynomials I mixed-unmixed case, Journal of Symbolic Computation, 33, 4, 447-465 (2002) · Zbl 1041.13019 |
| [29] | Huber, B.; Sturmfels, B., Bernstein’s theorem in affine space, Discrete and Computational Geometry, 17, 2, 137-141 (1997) · Zbl 0891.65055 |
| [30] | Jeronimo, G.; Krick, T.; Sabia, J.; Sombra, M., The computational complexity of the chow form, Foundations of Computational Mathematics, 4, 1, 41-117 (2004) · Zbl 1058.14075 |
| [31] | Kaltofen, E.; Villard, G., Computing the sign or the value of the determinant of an integer matrix, a complexity survey, Journal of Computational and Applied Mathematics, 162, 1, 133-146 (2004) · Zbl 1037.65044 |
| [32] | Keyser, J.; Ouchi, K.; Rojas, J. M., The exact rational univariate representation and its application, (Janardan, R.; Smid, M.; Dutta, D., Geometric and Algorithmic Aspects of Computer-Aided Design and Manufacturing. Geometric and Algorithmic Aspects of Computer-Aided Design and Manufacturing, AMS/DIMACS, vol. 67 (2005), AMS), 299-328 · Zbl 1272.65023 |
| [33] | Khetan, A., The resultant of an unmixed bivariate system, Journal of Symbolic Computation, 36, 3-4, 425-442 (2003) · Zbl 1068.14070 |
| [34] | Khetan, A., Exact matrix formula for the unmixed resultant in three variables, Journal of Pure and Applied Algebra, 198, 1-3, 237-256 (2005) · Zbl 1069.14056 |
| [35] | Kronecker, L., Leopold Kronecker’s Werke (1895-1931), Teubner · Zbl 0003.05003 |
| [36] | Lecerf, G., Quadratic Newton iteration for systems with multiplicity, Journal of Foundations of Computational Mathematics, 2, 3, 247-293 (2002) · Zbl 1030.65050 |
| [37] | Li, T. Y.; Wang, X., The BKK root count in \(C^n\), Mathematics of Computation, 65, 216, 1477-1484 (1996) · Zbl 0855.65053 |
| [38] | Minimair, M., Sparse resultant of composed polynomials II mixed-unmixed case, Journal of Symbolic Computation, 33, 4, 467-478 (2002) · Zbl 1041.13020 |
| [39] | Mourrain, B., A new criterion for normal form algorithms, (Proc. of 13th International Symposium, AAECC 13 ’99. Proc. of 13th International Symposium, AAECC 13 ’99, LNCS, vol. 1719 (1999), Springer), 430-443 · Zbl 0976.12005 |
| [40] | Pedersen, P.; Sturmfels, B., Product formulas for resultants and chow forms, Mathematische Zeitschrift, 214, 3, 377-396 (1993) · Zbl 0792.13006 |
| [41] | Rojas, J. M., Toric laminations, sparse generalized characteristic polynomials, and a refinement of Hilbert’s tenth problem, (Cucker, F.; Shub, M., Foundations of Computational Mathematics (1997), Springer), 369-381 · Zbl 0911.13012 |
| [42] | Rojas, J. M., Solving degenerate sparse polynomial systems faster, Journal of Symbolic Computation, 28, 1-2, 155-186 (1999) · Zbl 0943.65060 |
| [43] | Rojas, J. M., Toric intersection theory for affine root counting, Journal of Pure and Applied Algebra, 136, 1, 67-100 (1999) · Zbl 0943.14027 |
| [44] | Rojas, J. M., Algebraic geometry over four rings and the frontier to tractability, (J., D.; etal., Hilbert’s Tenth Problem: Relations with Arithmetic and Algebraic Geometry. Hilbert’s Tenth Problem: Relations with Arithmetic and Algebraic Geometry, Contemporary Mathematics, vol. 270 (2000), AMS), 275-321 · Zbl 1064.14074 |
| [45] | Rojas, J. M., Why polyhedra matter in non-linear equation solving, (Goldman, R.; Krasauskas, R., Topics in Algebraic Geometry and Geometric Modeling. Topics in Algebraic Geometry and Geometric Modeling, Contemporary Mathematics, vol. 334 (2003), AMS), 293-320 · Zbl 1073.12007 |
| [46] | Rojas, J. M.; Wang, X., Counting affine roots of polynomial systems via pointed Newton poly topes, Journal of Complexity, 12, 2, 116-133 (1996) · Zbl 0885.12007 |
| [47] | Rouillier, F., Solving zero-dimensional systems through the rational univariate representation, Applicable Algebra in Engineering, Communication and Computing, 9, 5, 433-461 (1999) · Zbl 0932.12008 |
| [48] | Sturmfels, B., On the Newton polytope of the resultant, Journal of Algebraic Combinatorics, 3, 2, 207-236 (1994) · Zbl 0798.05074 |
| [49] | Sturmfels, B., Solving Systems of Polynomial Equations (2002), AMS · Zbl 1101.13040 |
| [50] | von zur Gathen, J.; Gerhard, J., Modern Computer Algebra (2003), Cambridge University Press · Zbl 1055.68168 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
