Computation Of Sparse Approximate Greatest Common Divisors Of Univariate Polynomials

The problem of univariate polynomial approximate greatest common divisors (GCD) is a fundamental problem in the field of Symbolic-Numeric hybrid computation, and it is also important in some application fields. Estimation of sparse approximate GCDs of two univariate polynomials is studied in the paper. Although the computation of univariate polynomial approximate GCDs has been studied extensively, there are few articles con-cerning the problem of estimation of sparse approximate GCDs. Two algorithms have been established in the paper. One is a co-factors based sparse optimization algorithm, that is established based on Sylvester subresultant matrix's right null space, and it is a modification of an algorithm in the literature. Another is a Sylvester subresultant matrix's left null space based sparse optimization algorithm. For the algorithm, we have firstly established a Sylvester subresultant matrix's left null space based subspace algorithm to calculate approximate GCDs, and then established a l1-norm sparse optimization problem model to recover approximate GCDs with sparse coefficients by applying the results of our subspace algorithm. We have compared our subspace method for the computation of approximate GCDs with a subspace algorithm based on generalized Sylvester matrix in the literature. Numerical experiments show that our algorithm has better efficiency. Furthermore, we give numerical experiments to demonstrate estimation error of our two algorithms for sparse approximate GCDs.