Skip to Main content Skip to Navigation
Journal articles

Multivariate Polynomials, Duality, and Structured Matrices

Abstract : We first review the basic properties of the well known classes of Toeplitz, Hankel, Vandermonde, and other related structured matrices and reexamine their correlation to operations with univariate polynomials. Then we define some natural extensions of such classes of matrices based on their correlation to multivariate polynomials. We describe the correlation in terms of the associated operators of multiplication in the polynomial ring and its dual space, which allows us to generalize these structures to the multivariate case. Multivariate Toeplitz, Hankel, and Vandermonde matrices, Bezoutians, algebraic residues, and relations between them are studied. Finally, we show some applications of this study to rootfinding problems for a system of multivariate polynomial equations, where the dual space, algebraic residues, Bezoutians, and other structured matrices play an important role. The developed techniques enable us to obtain a better insight into the major problems of multivariate polynomial computations and to improve substantially the known techniques of the study of these problems. In particular, we simplify and/or generalize the known reduction of the multivariate polynomial systems to the matrix eigenproblem, the derivation of the Bézout and Bernshtein bounds on the number of the roots, and the construction of multiplication tables. From the algorithmic and computational complexity point, we yield acceleration by one order of magnitude of the known methods for some fundamental problems of solving multivariate polynomial systems of equations.
Document type :
Journal articles
Complete list of metadata
Contributor : Bernard Mourrain Connect in order to contact the contributor
Submitted on : Monday, October 8, 2012 - 2:04:08 PM
Last modification on : Thursday, January 20, 2022 - 4:12:21 PM

Links full text




Bernard Mourrain, Victor Pan. Multivariate Polynomials, Duality, and Structured Matrices. Journal of Complexity, Elsevier, 2000, 16 (1), pp.110 - 180. ⟨10.1006/jcom.1999.0530⟩. ⟨hal-00739512⟩



Les métriques sont temporairement indisponibles