The Canonical Decomposition of $\mathcal{C}^n_d$ and Numerical Gröbner and Border Bases

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 Grobner 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 Grobner 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 Grobner...