Solving determinantal systems using homotopy techniques. (English) Zbl 1461.13034
Let \(R=K[x_1,\ldots,x_n]\) be the ring of polynomials with coefficients in the field \(K\) where \(K\) has characteristic zero. Let also \(\overline{K}\) be the algebraic closure of \(K\). Suppose that \(\mathbf{F}=[f_{i,j}]_{p\times q}\) is a polynomial matrix over \(R\) with \(p\le q\) and \(G=\{g_1,\ldots ,g_t\}\) is a set of non-zero polynomials in \(R\). Let us define
\[V_p(\mathbf{F},G)=\{\mathbf{x}\in \overline{K} \ | \ \mathrm{ rank }(\mathbf F(x)) < p \ \text{ and } \ g_1(\mathbf{x})=\cdots = g_t(\mathbf{x})=0\}.\]
The main interest behind the study of this algebraic set lies in the fields of polynomial optimization and computational geometry.
In the paper under review, the authors provide bounds on the number of isolated points in \(V_p(\mathbf{F},G)\) depending on the maxima of the degrees in rows (resp. columns) of \(\mathbf{F}\) and design probabilistic homotopy algorithms for computing those points. These algorithms have been implemented in Magma and their performance has been evaluated via a set of benchmark polynomials.
In the paper under review, the authors provide bounds on the number of isolated points in \(V_p(\mathbf{F},G)\) depending on the maxima of the degrees in rows (resp. columns) of \(\mathbf{F}\) and design probabilistic homotopy algorithms for computing those points. These algorithms have been implemented in Magma and their performance has been evaluated via a set of benchmark polynomials.
Reviewer: Amir Hashemi (Isfahan)
MSC:
| 13P15 | Solving polynomial systems; resultants |
| 65H20 | Global methods, including homotopy approaches to the numerical solution of nonlinear equations |
Keywords:
polynomial system solving; homotopy; symbolic computation; determinantal algebraic sets; complexityReferences:
| [1] | Adrovic, D.; Verschelde, J., A polyhedral method to compute all affine solution sets of sparse polynomial systems (2013), arXiv preprint |
| [2] | Allgower, E. L.; Georg, Kurt, Introduction to Numerical Continuation Methods (2003), Society for Industrial and Applied Mathematics · Zbl 1036.65047 |
| [3] | Alonso, M. E.; Becker, E.; Roy, M.-F.; Wörmann, T., Zeroes, multiplicities and idempotents for zerodimensional systems, (Algorithms in Algebraic Geometry and Applications. Proceedings of MEGA’94. Algorithms in Algebraic Geometry and Applications. Proceedings of MEGA’94, Progress in Mathematics, vol. 142 (1996), Birkhaüser), 1-15 · Zbl 0879.14033 |
| [4] | Atiyah, M.; MacDonald, I., Introduction to Commutative Algebra, Addison-Wesley Series in Mathematics (1969), Addison-Wesley · Zbl 0175.03601 |
| [5] | Aubry, P.; Rouillier, F.; Safey El Din, M., Real solving for positive dimensional systems, J. Symb. Comput., 34, 6, 543-560 (2002) · Zbl 1046.14031 |
| [6] | Bank, B.; Giusti, M.; Heintz, J.; Mbakop, G.-M., Polar varieties and efficient real elimination, Math. Z., 238, 1, 115-144 (2001) · Zbl 1073.14554 |
| [7] | Bank, B.; Giusti, M.; Heintz, J.; Pardo, L.-M., Generalized polar varieties: geometry and algorithms, J. Complex., 21, 4, 377-412 (2005) · Zbl 1085.14047 |
| [8] | Bank, B.; Giusti, M.; Heintz, J.; Safey El Din, M.; Schost, É., On the geometry of polar varieties, Appl. Algebra Eng. Commun. Comput., 33-83 (2010) · Zbl 1186.14060 |
| [9] | Bank, B.; Giusti, M.; Heintz, J.; Safey El Din, M., Intrinsic complexity estimates in polynomial optimization, J. Complex., 30, 4, 430-443 (2014) · Zbl 1302.65296 |
| [10] | Bank, B.; Giusti, M.; Heintz, J.; Lecerf, G.; Matera, G.; Solernó, P., Degeneracy loci and polynomial equation solving, Found. Comput. Math., 15, 1, 159-184 (2015) · Zbl 1341.14022 |
| [11] | Basu, S.; Roy, M.-F.; Safey El Din, M.; Schost, É., A baby-step giant-step roadmap algorithm for general real algebraic sets, Found. Comput. Math., 14, 6, 1117-1172 (2014) · Zbl 1322.14090 |
| [12] | Bates, D. J.; Hauenstein, J. D.; Peterson, C.; Sommese, A. J., A numerical local dimension test for points on the solution set of a system of polynomial equations, SIAM J. Numer. Anal., 47, 5, 3608-3623 (2009) · Zbl 1211.14066 |
| [13] | Bates, D. J.; Hauenstein, J. D.; Sommese, A. J.; Wampler, C. W., Numerically Solving Polynomial Systems with Bertini, Software, Environments, and Tools, vol. 25 (2013), Society for Industrial and Applied Mathematics (SIAM): Society for Industrial and Applied Mathematics (SIAM) Philadelphia, PA · Zbl 1295.65057 |
| [14] | Bates, D. J.; Brake, D. A.; Hauenstein, J. D.; Sommese, A. J.; Wampler, C. W., On computing a cell decomposition of a real surface containing infinitely many singularities, (Mathematical Software—ICMS 2014. Mathematical Software—ICMS 2014, Lecture Notes in Comput. Sci., vol. 8592 (2014), Springer: Springer Heidelberg), 246-252 · Zbl 1437.14061 |
| [15] | Bates, Daniel J.; Hauenstein, Jonathan D.; Sommese, Andrew J.; Wampler, Charles W., Bertini: Software for Numerical Algebraic Geometry (2006) |
| [16] | Besana, G. M.; Di Rocco, S.; Hauenstein, J. D.; Sommese, A. J.; Wampler, C. W., Cell decomposition of almost smooth real algebraic surfaces, Numer. Algorithms, 63, 4, 645-678 (2013) · Zbl 1271.65031 |
| [17] | Bompadre, A.; Matera, G.; Wachenchauzer, R.; Waissbein, A., Polynomial equation solving by lifting procedures for ramified fibers, Theor. Comput. Sci., 315, 2, 335-369 (2004) · Zbl 1060.65054 |
| [18] | Bosma, Wieb; Cannon, John; Playoust, Catherine, The magma algebra system I: the user language, J. Symb. Comput., 24, 3-4, 235-265 (1997) · Zbl 0898.68039 |
| [19] | Brake, D. A.; Bates, D. J.; Hao, W.; Hauenstein, J. D.; Sommese, A. J.; Wampler, C. W., Algorithm 976: : numerical decomposition of real algebraic curves and surfaces, ACM Trans. Math. Softw., 44, 1, Article 10 pp. (2017) · Zbl 1484.14109 |
| [20] | Breiding, Paul; Timme, Sascha, Homotopycontinuation.jl: a package for homotopy continuation in Julia, (Davenport, James H.; Kauers, Manuel; Labahn, George; Urban, Josef, Mathematical Software - ICMS 2018 (2018), Springer International Publishing: Springer International Publishing Cham), 458-465 · Zbl 1396.14003 |
| [21] | Conca, A.; Herzog, J., On the Hilbert function of determinantal rings and their canonical module, Proc. Am. Math. Soc., 122, 3, 677-681 (1994) · Zbl 0823.13008 |
| [22] | Dahan, X.; Schost, É., Sharp estimates for triangular sets, (ISSAC (2004), ACM), 103-110 · Zbl 1134.13308 |
| [23] | Della Dora, J.; Discrescenzo, C.; Duval, D., About a new method for computing in algebraic number fields, (EUROCAL’85. EUROCAL’85, LNCS, vol. 204 (1985), Springer), 289-290 |
| [24] | Eagon, J.; Northcott, D., Ideals defined by matrices and a certain complex associated with them, Proc. R. Soc. Lond. Ser. A, Math. Phys. Sci., 269, 1337, 188-204 (1962) · Zbl 0106.25603 |
| [25] | Eisenbud, D., Commutative Algebra with a View Toward Algebraic Geometry, Graduate Texts in Mathematics, vol. 150 (1995), Springer-Verlag · Zbl 0819.13001 |
| [26] | Faugère, J.-C.; Safey El Din, M.; Spaenlehauer, P.-J., Critical points and Gröbner bases: the unmixed case, (Proceedings of the 37th International Symposium on Symbolic and Algebraic Computation. Proceedings of the 37th International Symposium on Symbolic and Algebraic Computation, ISSAC ’12 (2012), ACM: ACM New York, NY, USA), 162-169 · Zbl 1308.68171 |
| [27] | Faugère, J.-C.; Safey El Din, M.; Spaenlehauer, P.-J., On the complexity of the generalized minrank problem, J. Symb. Comput., 55, 30-58 (2013) · Zbl 1302.13026 |
| [28] | Fulton, W.; Pragacz, P., Schubert Varieties and Degeneracy Loci (2006), Springer · Zbl 0913.14016 |
| [29] | Fulton, William, Flags, Schubert polynomials, degeneracy loci, and determinantal formulas, Duke Math. J., 65, 3, 381-420 (1992) · Zbl 0788.14044 |
| [30] | von zur Gathen, J.; Gerhard, J., Modern Computer Algebra (2003), Cambridge University Press · Zbl 1055.68168 |
| [31] | Gianni, P.; Mora, T., Algebraic solution of systems of polynomial equations using Groebner bases, (AAECC. AAECC, LNCS, vol. 356 (1989), Springer), 247-257 · Zbl 0692.13012 |
| [32] | Giusti, M.; Heintz, J.; Morais, J.-E.; Pardo, L.-M., When polynomial equation systems can be solved fast?, (AAECC-11. AAECC-11, LNCS, vol. 948 (1995), Springer), 205-231 · Zbl 0902.12005 |
| [33] | Giusti, M.; Heintz, J.; Morais, J.-E.; Morgenstern, J.; Pardo, L.-M., Straight-line programs in geometric elimination theory, J. Pure Appl. Algebra, 124, 101-146 (1998) · Zbl 0944.12004 |
| [34] | 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 |
| [35] | Greuet, A.; Safey El Din, M., Probabilistic algorithm for polynomial optimization over a real algebraic set, SIAM J. Optim., 24, 3, 1313-1343 (2014) · Zbl 1327.90232 |
| [36] | Guo, F.; Safey El Din, M.; Zhi, L., Global optimization of polynomials using generalized critical values and sums of squares, (Proceedings of the 2010 International Symposium on Symbolic and Algebraic Computation. Proceedings of the 2010 International Symposium on Symbolic and Algebraic Computation, ISSAC ’10 (2010), ACM: ACM New York, NY, USA), 107-114 · Zbl 1321.90127 |
| [37] | Hauenstein, J. D., Numerically computing real points on algebraic sets, Acta Appl. Math., 125, 105-119 (2013) · Zbl 1269.65048 |
| [38] | Heintz, J.; Krick, T.; Puddu, S.; Sabia, J.; Waissbein, A., Deformation techniques for efficient polynomial equation solving, J. Complex., 16, 1, 70-109 (2000) · Zbl 1041.65044 |
| [39] | Heintz, J.; Jeronimo, G.; Sabia, J.; Solerno, P., Intersection Theory and Deformation Algorithms: The Multi-Homogeneous Case (2002) |
| [40] | Herrero, M. I.; Jeronimo, G.; Sabia, J., Computing isolated roots of sparse polynomial systems in affine space, Theor. Comput. Sci., 411, 44, 3894-3904 (2010) · Zbl 1241.65046 |
| [41] | Herrero, M. I.; Jeronimo, G.; Sabia, J., Affine solution sets of sparse polynomial systems, J. Symb. Comput., 51, 34-54 (2013) · Zbl 1264.13027 |
| [42] | Herrero, M. I.; Jeronimo, G.; Sabia, J., Elimination for generic sparse polynomial systems, Discrete Comput. Geom., 51, 3, 578-599 (2014) · Zbl 1310.68261 |
| [43] | Huber, Birkett; Verschelde, Jan, Pieri homotopies for problems in enumerative geometry applied to pole placement in linear systems control, SIAM J. Control Optim., 38, 4, 1265-1287 (2000) · Zbl 0955.14038 |
| [44] | Jeronimo, G.; Perrucci, D., A probabilistic symbolic algorithm to find the minimum of a polynomial function on a basic closed semialgebraic set, Discrete Comput. Geom., 52, 2, 260-277 (2014) · Zbl 1328.90138 |
| [45] | Jeronimo, G.; Matera, G.; Solerno, P.; Waissbein, A., Deformation techniques for sparse systems, Found. Comput. Math., 9, 1, 1-50 (2009) · Zbl 1167.14039 |
| [46] | Kronecker, L., Grundzüge einer arithmetischen Theorie der algebraischen Grössen, J. Reine Angew. Math., 92, 1-122 (1882) · JFM 14.0038.02 |
| [47] | Lahaye, E., Une méthode de résolution d’une catégorie d’équations transcendantes, C. R. Acad. Sci. Paris, 198, 1840-1842 (1934) · JFM 60.0259.03 |
| [48] | Lecerf, G., Computing an equidimensional decomposition of an algebraic variety by means of geometric resolutions, (ISSAC’00 (2000), ACM), 209-216 · Zbl 1326.68360 |
| [49] | Macaulay, F. S., The Algebraic Theory of Modular Systems (1916), Cambridge University Press · JFM 46.0167.01 |
| [50] | Matsumura, H., Commutative Ring Theory, Cambridge Studies in Advanced Mathematics (1986), Cambridge University Press · Zbl 0603.13001 |
| [51] | Miller, E.; Sturmfels, B., Combinatorial Commutative Algebra (2005), Springer Verlag: Springer Verlag New York · Zbl 1090.13001 |
| [52] | Mourrain, B., Isolated points, duality and residues, Algorithms for Algebra, Eindhoven, 1996. Algorithms for Algebra, Eindhoven, 1996, J. Pure Appl. Algebra, 117/118, 469-493 (1997) · Zbl 0896.13020 |
| [53] | Nie, J.; Ranestad, K., Algebraic degree of polynomial optimization, SIAM J. Optim., 20, 1, 485-502 (April 2009) · Zbl 1190.14051 |
| [54] | Nie, J.; Demmel, J.; Sturmfels, B., Minimizing polynomials via sum of squares over the gradient ideal, Math. Program., 106, 3, 587-606 (2006) · Zbl 1134.90032 |
| [55] | Pardo, L.-M.; San Martín, J., Deformation techniques to solve generalised Pham systems, Theor. Comput. Sci., 315, 2-3, 593-625 (2004) · Zbl 1053.65038 |
| [56] | Rouillier, F., Solving zero-dimensional systems through the rational univariate representation, Appl. Algebra Eng. Commun. Comput., 9, 5, 433-461 (1999) · Zbl 0932.12008 |
| [57] | Rouillier, F.; Roy, M.-F.; Safey El Din, M., Finding at least one point in each connected component of a re al algebraic set defined by a single equation, J. Complex., 16, 716-750 (2000) · Zbl 1009.14010 |
| [58] | Safey El Din, M.; Schost, É., Polar varieties and computation of one point in each connected component of a smooth real algebraic set, (ISSAC’03 (2003), ACM), 224-231 · Zbl 1072.68693 |
| [59] | Safey El Din, M.; Schost, É., A baby steps/giant steps probabilistic algorithm for computing roadmaps in smooth bounded real hypersurface, Discrete Comput. Geom., 45, 1, 181-220 (2011) · Zbl 1213.14110 |
| [60] | Safey El Din, M.; Schost, É., Bit complexity for multi-homogeneous polynomial system solving application to polynomial minimization, J. Symb. Comput. (2017) |
| [61] | Safey El Din, M.; Schost, É., A nearly optimal algorithm for deciding connectivity queries in smooth and bounded real algebraic sets, J. ACM, 63, 6, 48:1-48:37 (January 2017) · Zbl 1426.68311 |
| [62] | Safey El Din, M.; Spaenlehauer, P.-J., Critical point computations on smooth varieties: degree and complexity bounds, (Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computation. Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computation, ISSAC ’16 (2016), ACM: ACM New York, NY, USA), 183-190 · Zbl 1362.14061 |
| [63] | Schost, É., Computing parametric geometric resolutions, Appl. Algebra Eng. Commun. Comput., 13, 5, 349-393 (2003) · Zbl 1058.68123 |
| [64] | Shub, M.; Smale, S., Complexity of bezout’s theorem I: geometric aspects, J. Am. Math. Soc., 6, 2, 459-501 (1993) · Zbl 0821.65035 |
| [65] | Sommese, A. J.; Wampler, C. W., The Numerical Solution of Systems of Polynomials Arising in Engineering and Science (2005), World Scientific · Zbl 1091.65049 |
| [66] | Sommese, Andrew J.; Verschelde, Jan, Numerical homotopies to compute generic points on positive dimensional algebraic sets, J. Complex., 16, 3, 572-602 (2000) · Zbl 0982.65070 |
| [67] | Sottile, F.; Vakil, R.; Verschelde, J., Solving Schubert problems with Littlewood-Richardson homotopies, (Proceedings of the 2010 International Symposium on Symbolic and Algebraic Computation (2010), ACM), 179-186 · Zbl 1321.68541 |
| [68] | Spaenlehauer, P.-J., On the complexity of computing critical points with Gröbner bases, SIAM J. Optim., 24, 3, 1382-1401 (2014) · Zbl 1325.90072 |
| [69] | Verschelde, J., Polyhedral Methods in Numerical Algebraic Geometry, Contemporary Mathematics, vol. 496, 243 (2009) · Zbl 1181.65073 |
| [70] | Verschelde, J.; Verlinden, P.; Cools, R., Homotopies exploiting Newton polytopes for solving sparse polynomial systems, SIAM J. Numer. Anal., 31, 3, 915-930 (1994) · Zbl 0809.65048 |
| [71] | Verschelde, Jan, Algorithm 795: Phcpack: a general-purpose solver for polynomial systems by homotopy continuation, ACM Trans. Math. Softw., 25, 2, 251-276 (1999) · Zbl 0961.65047 |
| [72] | Zariski, O.; Samuel, P., Commutative Algebra (1958), Van Nostrand · Zbl 0112.02902 |
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.
