Truncated normal forms for solving polynomial systems: generalized and efficient algorithms. (English) Zbl 1443.13024
Summary: We consider the problem of finding the isolated common roots of a set of polynomial functions defining a zero-dimensional ideal \(I\) in a ring \(R\) of polynomials over \(\mathbb{C}\). Normal form algorithms provide an algebraic approach to solve this problem. The framework presented in [S. Telen et al., SIAM J. Matrix Anal. Appl. 39, No. 3, 1421–1447 (2018; Zbl 1401.65054)] uses truncated normal forms (TNFs) to compute the algebra structure of \(R/I\) and the solutions of \(I\). This framework allows for the use of much more general bases than the standard monomials for \(R/I\). This is exploited in this paper to introduce the use of two special (non-monomial) types of basis functions with nice properties. This allows us, for instance, to adapt the basis functions to the expected location of the roots of \(I\). We also propose algorithms for efficient computation of TNFs and a generalization of the construction of TNFs in the case of non-generic zero-dimensional systems. The potential of the TNF method and usefulness of the new results are exposed by many experiments.
MSC:
| 13P15 | Solving polynomial systems; resultants |
| 14Q65 | Geometric aspects of numerical algebraic geometry |
| 65H14 | Numerical algebraic geometry |
| 68W30 | Symbolic computation and algebraic computation |
Keywords:
polynomial systems; truncated normal forms; computational algebraic geometry; orthogonal polynomialsCitations:
Zbl 1401.65054References:
| [1] | Bates, D. J.; Hauenstein, J. D.; Sommese, A. J.; Wampler, C. W., Numerically Solving Polynomial Systems with Bertini, vol. 25 (2013), SIAM · Zbl 1295.65057 |
| [2] | Batselier, K.; Dreesen, P.; De Moor, B., A fast recursive orthogonalization scheme for the Macaulay matrix, J. Comput. Appl. Math., 267, 20-32 (2014) · Zbl 1293.65064 |
| [3] | Cattani, E.; Cox, D. A.; Chèze, G.; Dickenstein, A.; Elkadi, M.; Emiris, I. Z.; Galligo, A.; Kehrein, A.; Kreuzer, M.; Mourrain, B., Solving Polynomial Equations: Foundations, Algorithms, and Applications, Algorithms and Computation in Mathematics (2005) · Zbl 1061.12001 |
| [4] | Corless, R. M.; Gianni, P. M.; Trager, B. M., A reordered Schur factorization method for zero-dimensional polynomial systems with multiple roots, (Proceedings of the 1997 International Symposium on Symbolic and Algebraic Computation (1997), ACM), 133-140 · Zbl 0917.65048 |
| [5] | Cox, D. A.; Little, J.; O’Shea, D., Ideals, Varieties, and Algorithms, vol. 3 (1992), Springer · Zbl 0756.13017 |
| [6] | Cox, D. A.; Little, J.; O’Shea, D., Using Algebraic Geometry, vol. 185 (2006), Springer Science & Business Media |
| [7] | Dreesen, P.; Batselier, K.; De Moor, B., Back to the roots: polynomial system solving, linear algebra, systems theory, IFAC Proc. Vol., 45, 16, 1203-1208 (2012) |
| [8] | Elkadi, M.; Mourrain, B., Introduction à la résolution des systèmes polynomiaux, Mathématiques et Applications, vol. 59 (2007), Springer · Zbl 1127.13001 |
| [9] | Emiris, I. Z.; Mourrain, B., Matrices in elimination theory, J. Symb. Comput., 28, 1-2, 3-44 (1999) · Zbl 0943.13005 |
| [10] | Faugère, J.-C., FGb: a library for computing Gröbner bases, (Fukuda, K.; Hoeven, J.; Joswig, M.; Takayama, N., Mathematical Software - ICMS 2010. Mathematical Software - ICMS 2010, Lecture Notes in Computer Science, vol. 6327 (September 2010), Springer Berlin/Heidelberg: Springer Berlin/Heidelberg Berlin, Heidelberg), 84-87 · Zbl 1294.68156 |
| [11] | Joswig, M.; Müller, B.; Paffenholz, A., and lattice polytopes, (21st International Conference on Formal Power Series and Algebraic Combinatorics. 21st International Conference on Formal Power Series and Algebraic Combinatorics, FPSAC 2009, Nancy. 21st International Conference on Formal Power Series and Algebraic Combinatorics. 21st International Conference on Formal Power Series and Algebraic Combinatorics, FPSAC 2009, Nancy, Discrete Math. Theor. Comput. Sci. Proc., AK. Assoc. Discrete Math. Theor. Comput. Sci. (2009)), 491-502 · Zbl 1391.52019 |
| [12] | Möller, H. M.; Tenberg, R., Multivariate polynomial system solving using intersections of eigenspaces, J. Symb. Comput., 32, 5, 513-531 (2001) · Zbl 1084.65523 |
| [13] | Mourrain, B., A new criterion for normal form algorithms, (Proceedings of the 13th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes. Proceedings of the 13th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, LNCS (1999), Springer-Verlag: Springer-Verlag London, UK), 430-443 · Zbl 0976.12005 |
| [14] | Mourrain, B., Pythagore’s dilemma, symbolic-numeric computation, and the border basis method, (Symbolic-Numeric Computation (2007), Springer), 223-243 · Zbl 1117.65076 |
| [15] | Mourrain, B.; Pavone, J. P., Subdivision methods for solving polynomial equations, J. Symb. Comput., 44, 3, 292-306 (2009) · Zbl 1158.13010 |
| [16] | Mourrain, B.; Trébuchet, P., Generalized normal forms and polynomial system solving, (Proceedings of the 2005 International Symposium on Symbolic and Algebraic Computation (2005), ACM), 253-260 · Zbl 1360.68947 |
| [17] | Mourrain, B.; Trébuchet, P., Stable normal forms for polynomial system solving, Theor. Comput. Sci., 409, 2, 229-240 (2008) · Zbl 1159.68045 |
| [18] | Nakatsukasa, Y.; Noferini, V.; Townsend, A., Computing the common zeros of two bivariate functions via Bézout resultants, Numer. Math., 129, 1, 181-209 (2015) · Zbl 1308.65076 |
| [19] | Sorber, L.; Van Barel, M.; De Lathauwer, L., Numerical solution of bivariate and polyanalytic polynomial systems, SIAM J. Numer. Anal., 52, 1551-1572 (2014) · Zbl 1302.65135 |
| [20] | Stetter, H. J., Matrix eigenproblems are at the heart of polynomial system solving, ACM SIGSAM Bull., 30, 4, 22-25 (1996) · Zbl 1097.65530 |
| [21] | Sturmfels, B., Solving Systems of Polynomial Equations, CBMS Regional Conferences, vol. 97 (2002), Amer. Math. Soc. · Zbl 1101.13040 |
| [22] | Szegő, G., Orthogonal Polynomials (1967), American Mathematical Society · JFM 61.0386.03 |
| [23] | Telen, S.; Mourrain, B.; Van Barel, M., Solving polynomial systems via truncated normal forms, SIAM J. Matrix Anal. Appl., 39, 3, 1421-1447 (2018) · Zbl 1401.65054 |
| [24] | Telen, S.; Van Barel, M., A stabilized normal form algorithm for generic systems of polynomial equations, J. Comput. Appl. Math., 342, 119-132 (2018) · Zbl 1393.13006 |
| [25] | Townsend, A.; Trefethen, L. N., An extension of Chebfun to two dimensions, SIAM J. Sci. Comput., 35 (2013) · Zbl 1300.65010 |
| [26] | Trefethen, L. N., Approximation Theory and Approximation Practice, vol. 128 (2013), Siam · Zbl 1264.41001 |
| [27] | Trefethen, L. N.; Bau, D., Numerical Linear Algebra, vol. 50 (1997), Siam · Zbl 0874.65013 |
| [28] | Verschelde, J., 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 |
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.
