Many problems in polynomial algebra can be formulated for polynomials which are given with inexact coefficients. When considered numerically many of these algebraic problems are illposed. For example, very small random changes to a factorizatable multivariate polynomial typically result in an irreducible polynomial. Other examples of problems of this type are polynomial division and GCD computation.
It is possible to find reasonable partial solutions for a number of problems in approximate algebra by linearizing and using heuristics for finding nearest structured low rank matrices. If the problem can be restated as a problem of computing null vectors of a given matrix, then we typically can do two things: first, given a polynomial without a given property, we can find a lower bound on the distance to the nearest polynomial with the property and second, we can compute a "nearby" polynomial which has the given property.
In this talk we will outline several general stuctured low rank matrix finding techniques (including a naive application of the SVD, the Riemannian SVD, and an heuristic for structured total least norm), with specific details for the GCD, and factorization problems.