A stabilized normal form algorithm for generic systems of polynomial equations (Q1639532)

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.