×

A stabilized normal form algorithm for generic systems of polynomial equations. (English) Zbl 1393.13006

The ring of all polynomials in \(n\) variables \(x_1,\dots,x_n\) with coefficients in \(\mathbb{C}\) is denoted by \(\mathbb{C}[x_1,\dots,x_n]\), shortly \(\mathbb{C}[x]\). A set of \(n\) polynomials \(\{f_1,\dots,f_n\} \subset \mathbb{C}[x]\) defines a square ideal \[ I = \langle f_1,\dots,f_n \rangle = \{g_1f_1+\dots+g_nf_n : g_1,\dots,g_n \in \mathbb{C}[x]\} \subset \mathbb{C}[x]. \] The affine variety associated to \(I\) is \[ \mathbb{V}(I) = \{x \in \mathbb{C}^n : f(x) = 0, \forall f\in I\} = \{x \in \mathbb{C}^n : f_1(x) =\dots = f_n (x) = 0\}. \] In this paper, the authors assume that the variety \(\mathbb{V}(I)\) consists of finitely many points \(\{z_1,\dots,z_N\} \subset \mathbb{C}^n\). Such a variety is called 0-dimensional. They also assume that the homogenized equations \(f_1^h=\dots=f_n^h=0\) have a finite number of solutions in the projective \(n\)-space \(\mathbb{P}^n\). Furthermore, they assume that none of the solutions lie on the hyperplane at infinity. For a zero-dimensional ideal \(I\), \(\mathbb{C}[x]/I\) is a vector space with the dimension equal to the number of points in \(\mathbb{V}(I) \subset \mathbb{C}^n\), counting multiplicities.
The quotient ring \(\mathbb{C}[x]/I\) and the linear mapping \(m_f : \mathbb{C}[x]/I \to \mathbb{C}[x]/I\) are defined. The linear mapping \(m_f\) can be represented by a matrix \(N\times N\), where \(N\) is the Bézout number. The authors discuss the eigenstructure and properties of this matrix.
Let \(\mathcal{O} = \{[b_1],\dots,[b_N]\}\) be a basis for \(\mathbb{C}[x]/I\). For any given polynomial \(g \in \mathbb{C}[x]\), let \[ [g] = a_1[b_1]+\dots+ a_N[b_N]=[a_1 b_1 +\dots +a_N b_N], \quad a_i \in \mathbb{C}, \] be the unique representation of \([g]\) in the basis \(\mathcal{O}\). Then \(a_1 b_1 + \dots + a_N b_N\) is the normal form of \(g\) w.r.t. \(\mathcal{O}\). It is denoted \(\bar{g}^{\mathcal{O}} = a_1 b_1 + \dots + a_N b_N\). In the paper, the authors propose an algorithm how to choose a basis \(\mathcal{O}\) for \(\mathbb{C}[x]/I\) such that the multiplication operators can be computed as accurately as possible.
As a motivation, the authors investigate the Macaulay matrices associated to the set of polynomials \(\{f_1,\dots,f_n\} \subset \mathbb{C}[x]\). These matrices are then used to compute the normal form for a generic dense system of polynomial equations. The authors propose to make the choice of basis \(\mathcal{O}\) by using a QR factorization with optimal column pivoting on (part of) the Macaulay matrix.
Numerical examples are given in the last part of the paper along with suggestions for future work.

MSC:

13A15 Ideals and multiplicative ideal theory in commutative rings
65F30 Other matrix algorithms (MSC2010)
65F15 Numerical computation of eigenvalues and eigenvectors of matrices
13P15 Solving polynomial systems; resultants
PDFBibTeX XMLCite
Full Text: DOI arXiv Link

References:

[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] Verschelde, J., Algorithm 795: phcpack: A general-purpose solver for polynomial systems by homotopy continuation, ACM Trans. Math. Software (TOMS), 25, 2, 251-276, (1999) · Zbl 0961.65047
[3] Cox, D. A.; Little, J.; O’shea, D., Ideals, varieties, and algorithms, vol. 3, (1992), Springer
[4] Cox, D. A.; Little, J.; O’shea, D., Using algebraic geometry, vol. 185, (2006), Springer Science & Business Media
[5] Mourrain, B., A new criterion for normal form algorithms, (Proceedings of the 13th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, LNCS, (1999), Springer-Verlag London, UK), 430-443 · Zbl 0976.12005
[6] Stetter, H. J., Numerical polynomial algebra, (2004), Society for Industrial and Applied Mathematics · Zbl 1058.65054
[7] Mourrain, B., Pythagore’s dilemma, symbolic-numeric computation, and the border basis method, (Symbolic-Numeric Computation, (2007), Springer), 223-243 · Zbl 1117.65076
[8] Emiris, I. Z.; Canny, J., A practical method for the sparse resultant, Proc. ACM Intern. Symp. on Symbolic and Algebraic Computation, 183-192, (1993) · Zbl 0924.65046
[9] Dreesen, P., Back to the roots, (2013), KU Leuven - Faculty of Engineering Science, promotor: Bart De Moor
[10] Batselier, K., A numerical linear algebra framework for solving problems with multivariate polynomials, (2013), KU Leuven - Faculty of Engineering Science, promotor: Bart De Moor
[11] Hartshorne, R., Algebraic geometry, (1977), Springer · Zbl 0367.14001
[12] Elkadi, M.; Mourrain, B., Introduction à la résolution des systèmes polynomiaux, Mathématiques et Applications, Vol. 59, (2007), Springer · Zbl 1127.13001
[13] E. Cattani, D.A. Cox, G. Chèze, A. Dickenstein, M. Elkadi, I.Z. Emiris, A. Galligo, A. Kehrein, M. Kreuzer, B. Mourrain, Solving Polynomial equations: foundations, algorithms, and applications (Algorithms and Computation in Mathematics), 2005.; E. Cattani, D.A. Cox, G. Chèze, A. Dickenstein, M. Elkadi, I.Z. Emiris, A. Galligo, A. Kehrein, M. Kreuzer, B. Mourrain, Solving Polynomial equations: foundations, algorithms, and applications (Algorithms and Computation in Mathematics), 2005.
[14] Macaulay, F. S., The algebraic theory of modular systems, (1994), Cambridge University Press · JFM 46.0167.01
[15] Buchberger, B.; Winkler, F., Gröbner bases and applications, vol. 251, (1998), Cambridge University Press
[16] Faugère, J.-C., A new efficient algorithm for computing Gröbner bases (F4), J. Pure Appl. Algebra, 139, 1, 61-88, (1999) · Zbl 0930.68174
[17] Mourrain, B.; Trebuchet, 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
[18] Mourrain, B.; Trébuchet, P., Stable normal forms for polynomial system solving, Theoret. Comput. Sci., 409, 2, 229-240, (2008) · Zbl 1159.68045
[19] Eisenbud, D., The geometry of syzygies: A second course in commutative algebra and algebraic geometry, (2005), Springer New York, NY, OCLC: 249751633 · Zbl 1066.14001
[20] Golub, G., Numerical methods for solving linear least squares problems, Numer. Math., 7, 3, 206-216, (1965) · Zbl 0142.11502
[21] Bates, D. J.; Newell, A. J.; Niemerg, M., Bertinilab: A MATLAB interface for solving systems of polynomial equations, Numer. Algorithms, 71, 1, 229-244, (2016) · Zbl 1333.65054
[22] Guan, Y.; Verschelde, J., Phclab: a MATLAB/octave interface to phcpack, IMA Vol. Math. Appl., 148, 15, (2008) · Zbl 1148.68578
[23] N. Vervliet, O. Debals, L. Sorber, M. Van Barel, L. De Lathauwer, Tensorlab 3.0. Available online, URL: www.tensorlab.net; N. Vervliet, O. Debals, L. Sorber, M. Van Barel, L. De Lathauwer, Tensorlab 3.0. Available online, URL: www.tensorlab.net
[24] S.E. Leurgans, R.T. Ross, R.B. Abel, A decomposition for three-way arrays. 14(4): 1064-1083, 1993. http://dx.doi.org/10.1137/0614071; S.E. Leurgans, R.T. Ross, R.B. Abel, A decomposition for three-way arrays. 14(4): 1064-1083, 1993. http://dx.doi.org/10.1137/0614071 · Zbl 0788.65145
[25] De Lathauwer, L., A link between the canonical decomposition in multilinear algebra and simultaneous matrix diagonalization, SIMAX, 28, 3, 642-666, (2006) · Zbl 1126.15007
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.