Multivariate polynomials, duality, and structured matrices (Q1977144): Difference between revisions

The authors study solutions of systems of polynomial equations in several variables. They generalize Toeplitz, Hankel, Vandermonde, and other structured matrices to several variables and the relation to operations with polynomials. The authors also study Bezoutians, algebraic residues and relations between them. They apply the theory to rootfinding problems for systems of multivariate polynomial equations. The dual space, algebraic residues, Bezoutians and other structured matrices have an important role. Their algorithms improve over the previous methods, by an order of magnitude, the computational complexity of some problems. They give an overview of the univariate case followed by a generalization to multivariate polynomials. Let \(R=\mathbb C [x_1,x_2, \dots{}, x_n]\) be the ring of complex polynomials in the variables \(x_1, x_2, \dots{}, x_n\). Suppose \(A=R/I\) where \(I\) is the ideal generated by a finite set of polynomials with only finitely many roots \(\zeta_1, \zeta_2, \dots{}, \zeta_d\). \(R^*\) and \(A^*\) denote the dual spaces of linear functionals of \(R,A\) respectively. \(A^*\) can be identified with the the members of \(R^*\) that vanish on the ideal \(I\). The operator of multiplying by \(a\in A\) is denoted \(M_a\). Theorem 1: The set of eigenvalues of \(M_a\) is precisely \(\{ a(\zeta_1), a(\zeta_2), \dots{}, a(\zeta_d)\} \). Theorem 2: The common eigenvectors of the dual operator \({M_a}^*\) in \(A^*\) are, up to a scalar factor, the evaluations at \(\zeta_1, \zeta_2, \dots{}, \zeta_d\). Let \(E,F\) be finite subsets of \({\mathbb N}^n\). \(M\) is an \(E\times F\)-quasi-Toeplitz matrix if \(m_{\alpha,\beta }= m_{\gamma, \delta }\) provided \(\alpha - \beta = \gamma - \delta \). A matrix \(M\) is a quasi-Hankel if \(m_{\alpha, \beta } = m_{\gamma, \delta }\) whenever \(\alpha + \beta = \gamma + \delta \). Multiplication of a quasi-Toeplitz (-Hankel) matrix by a vector can be interpreted as (Laurent's) polynomial multiplication. The authors also define Bezout matrices and show that inverses of Bezout matrices are quasi-Hankel. They also discuss relations among Bezoutians, quasi-Hankel and multivariate Vandermonde matrices. The authors give an algorithm for computing the roots of a system of multivariate polynomial equations in the case of simple roots. The authors also give an algorithm for solving systems of multivariate polynomials in the case of multiple roots by computing a basis for the corresponding eignspaces. Another algorithm of the authors is for the solution of a polynomial system via the solution of a generalized eigenvector problem. In this latter algorithm they use Bezoutian matrices. Several other algorithms are also discussed for computing traces and real roots as well as multiplication in the dual spaces \(R^*\) and \(A^*\). All algorithms are illustrated by examples. Some open problems are also discussed.