THE CANONICAL DECOMPOSITION OF CND AND NUMERICAL GRÖBNER AND BORDER BASES∗

Abstract. This article introduces the canonical decomposition of the vector space of multivariate polynomials for a given monomial ordering. Its importance lies in solving multivariate polynomial systems, computing Gröbner bases, and solving the ideal membership problem. An SVD-based algorithm is presented that numerically computes the canonical decomposition. It is then shown how, by introducing the notion of divisibility into this algorithm, a numerical Gröbner basis can also be computed. In addition, we demonstrate how the canonical decomposition can be used to decide whether the affine solution set of a multivariate polynomial system is zero-dimensional and to solve the ideal membership problem numerically. The SVD-based canonical decomposition algorithm is also extended to numerically compute border bases. A tolerance for each of the algorithms is derived using perturbation theory of principal angles. This derivation shows that the condition number of computing the canonical decomposition and numerical Gröbner basis is essentially the condition number of the Macaulay matrix. Numerical experiments with both exact and noisy coefficients are presented and discussed