Semidefinite characterization and computation of zero-dimensional real radical ideals (Q1029543)

As far as the reviewer can judge, the paper proposes a revolutionary method for computing the real radical \(\root{\mathbb R}\of{I}\) of an ideal \(I\subseteq \mathbb R[x]=\mathbb R[x_1,\dots, x_n],\) provided it is zero dimensional. Working completely in the realm of the reals it also allows to find the associated real variety \(V_\mathbb R(I)=V_\mathbb C(I)\cap \mathbb R\) without the computational overhead associated to algebraic methods that take the complex zeros into account. The method is also developed for finding complex varieties but authors do not claim it competitive for this case. Given a real (generalized) sequence \(y=(y_{\alpha})_{\alpha\in \mathbb N^n},\) one defines the (symmetric) moment matrix \(M(y)=(y_{\alpha+\beta}).\) A polynomial \(h=\sum_\alpha h_\alpha x^\alpha\in \mathbb R[x]\) is encoded by vec\((h)=(h_\alpha),\) and induces a new sequence \(hy:= M(y)\mathrm{vec}(h).\) This in turn defines \(M(hy),\) and, in a natural way, the kernel of \(M(y)\) as the set of polynomials \(h\) so that \(hy=0.\) A fundamental observation is Proposition 1.1: Let \(I=\langle h_1,\dots, h_m \rangle,\) with \(h_i\in \mathbb R[x]\) and assume \(V_\mathbb R(I)\) is finite. If \(M(y)\succeq 0,\) and \(M(h_jy)=0\) for \(j=1,\dots, m,\) then \(I(V_\mathbb R(I))\subseteq \mathrm{Ker}M(y)\) with equality iff \(M(y)\) has maximum rank. In practice one can work with finite truncated moment matrices \(M_t(y)\) in which one requires \(\sum_i\alpha_i=:|\alpha|,|\beta|\leq t;\) see below. Once an appropriate matrix \(M_t(y)\) is found, the row indices of a maximum nonsingular principal submatrix of \(M_t(y)\) correspond to a linear basis \(\mathcal{B}\) of \(R[x]/I(V_\mathbb R(I)).\) From \(M_t(y),\) a matrix of any multiplication operator in \(\mathbb R[x]/I(V_\mathbb R(I))\) can be calculated, and from this in turn \(V_\mathbb R(I)\) using the well known eigenvalue method. When \(\mathcal{B}\) is stable under division, one easily finds a border basis for \(I(V_{\mathbb R}(I))\) as defined in [\textit{H. J. Stetter}, Numerical polynomial algebra. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM) (2004; Zbl 1058.65054)]. Suitable matrices \(M_t(y)\) are found via interior point methods for semidefinite programming; see \textit{L. Vandenberghe} and \textit{S. Boyd} [SIAM Rev. 38, No. 1, 49--95 (1996; Zbl 0845.65023)]. The paper draws on much background material which is presented as follows: section 2 contains preliminaries about polynomial ideals. In section 2.1 real radical ideals are characterized and the classical Nullstellensatz and the real Nullstellensatz saying \(\root{\mathbb R}\of{I}=I(V_\mathbb R(I))\) are enunciated. In subsections 2.2 to 2.5, the quotient algebra ring \(\mathbb K[x]/I,\) \(\mathbb K=\mathbb R\) or \(\mathbb C,\) multiplication matrices, Gröbner bases, as well as known results relating points of a variety \(V_{\mathbb C}(I)\) with the eigenvalues of the multiplication matrices are recalled; a set of standard monomials in \( \mathbb K[x]/I\) is found from an independence oracle; and border bases, an extension of Groebner bases, have a subsection of their own. Section 3 has preliminaries about real and complex moment matrices and results relating real radical ideals and kernels of positive semidefinite moment matrices. In particular subsection 3.2 explains the relation between moments and finite varieties: for \(v\in \mathbb C^n\) let \(\zeta_v=(v^\alpha)_{\alpha\in \mathbb N^n}.\) Now let \(W\subset \mathbb R^n\) be finite and \(\mu=\sum_{v\in W} \lambda_v \delta_v\) be a positive measure supported on \(W;\) i.e. \(\lambda_v>0.\) Define the sequence \(y^\mu= (y^\mu_\alpha)\) by \(y^\mu_\alpha=\int x^\alpha d\mu=\sum_{v\in W} \lambda_v v^\alpha.\) Then \(M(y^\mu)\succeq 0\) and Ker\(M(y^\mu)=I(W)\subseteq \mathbb R[x],\) the ideal defined by \(W.\) Next let \(d_j= \lceil (\deg h_j)/2 \rceil,\) \( d=\max_j d_j,\) and \(K_t=\{y\in \mathbb R^{\mathbb N_{2t}^n}:y_0=1, M_t(y)\succeq 0, M_{t-d_j}(h_jy)=0, \text{ for } j=1,\dots, m \}.\) In the simple lemma 3.1 one finds the first indications of inclusion relations between the kernels of moment matrices and real radical ideals in a finite setting: if \(t\geq d\) and \(y\in K_t\) is such that \(\mathrm{rank} M_t(y)\) is maximum then \(\mathrm{Ker}M_t(y) \subseteq I(V_{\mathbb R}(I)).\) Subsection 3.3 is dedicated to flat extensions of matrices and finite rank moment matrices; in particular results due to \textit{R. E. Curto} and \textit{L. A. Fialkow} [Solution of the truncated complex moment problem for flat data, Mem. Am. Math. Soc. 568 (1996; Zbl 0876.30033)] play an important part; one of their results is that given a moment matrix \(M(y)\succeq 0\) of finite rank, \(y\) stems in the sense above from a finite pointset \(W\) in \(\mathbb R^n\) and which will have \(\mathrm{Ker} M(y)=I(W).\) Towards the end of section 3 one finally finds the proof of proposition 1.1. Section 4 presents a semidefinite characterization of the real radical ideal and gives the algorithm. Proposition 1.1 is `finitized' in Proposition 4.4: Let \(t\geq d,\) and \(y\in K_t\) achieve maximal rank of \(M_t(y).\) Assume \( 2d\leq s\leq t\) and \(\mathrm{rank}M_s(y)= \mathrm{rank}M_{s-1}(y)\) or for some \(d\leq s \leq t\) \(\mathrm{rank}M_s(y)= \mathrm{rank}M_{s-d}(y).\) Then \(I(V_{\mathbb R}(I))=\langle \mathrm{Ker} M_s(y)\rangle.\) Similar results are also proved for \(I(V_{\mathbb R}(I)\cap S),\) where \(S\) is a semialgebraic set. Proposition 4.6 shows that for \(t\) large enough the criterium of proposition 4.4 is met so that the algorithm presented in section 4.4 will terminate for such \(t\). (Subsection 4.3 is dedicated to \(I(V_{\mathbb C}(I)).\)) The algorithm consists for a given order \(t\geq d\) of five steps explained in detail in subsubsections: 4.4.1: Finding an \(y\in K_t\) that maximizes the rank of \(M_t(y)\), a step done by semidefinite programming; 4.4.2: checking the ranks of submatrices of \(M_t(y)\) via singular value decomposition also used in the next step 4.4.3: computing a basis for the column space of \(M_{s-1}(y)\) and the quotient space \(\mathbb K[x]/J;\) 4.4.4: computing formal multiplication matrices; 4.4.5: constructing a basis for the ideal \(\langle \mathrm{Ker}M_s(y)\rangle.\) Section 5 reports on numerical examples. When all roots of a system are real, one can sometimes expect simpler solutions for the classical radical than by Seidenberg's method. A reader will find a parallel study of \textit{M. Laurent}'s survey [in: The IMA Volumes in Mathematics and its Applications 149, 157--270 (2009; Zbl 1163.13021)] profitable.