# Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

Compute an approximate GCD to a pair of polynomials with approximate coefficients

Contributed by:
Daniel Lichtblau

ResourceFunction["ApproximatePolynomialGCD"][ computes a polynomial that is, to reasonable approximation, a largest-degree divisor of both |

ResourceFunction["ApproximatePolynomialGCD"] uses numeric substitutions with complex values. This can lead to results where all input coefficients are real-valued and yet imaginary parts appear. In such cases these imaginary parts are removed.

The tolerance is used primarily to remove terms that are too small to be considered relevant.

ResourceFunction["ApproximatePolynomialGCD"] handles the univariate case using singular value decompositions on Sylvester matrices. A secondary use of the Tolerance option is to determine which singular values to regard as zero.

The multivariate case is handled by iteratively solving linear overdetermined least-squares systems to compute cofactors and partial greatest common divisors, lifting one variable at a time.

Examples are from user questions in forums and benchmarks from the literature on approximate polynomial GCDs.

Compute the approximate GCD of a pair of univariate polynomials:

In[1]:= |

Out[3]= |

Compare to the GCD from rounding the coefficients of these polynomials:

In[4]:= |

Out[5]= |

They are very close up to a constant multiple:

In[6]:= |

Out[6]= |

Compute the approximate GCD of a pair of bivariate polynomials:

In[7]:= |

Out[8]= |

Perturb a factor to create a pair of bivariate polynomials with an approximate factor in common:

In[9]:= |

Some of zero contours are quite similar:

In[10]:= |

Out[10]= |

Recover the approximate GCD:

In[11]:= |

Out[11]= |

Check that the result, suitably normalized, is close to the known approximate common factor:

In[12]:= |

Out[12]= |

The zero contour of the approximate GCD is similar to the similar contours from the inputs:

In[13]:= |

Out[13]= |

In[14]:= |

Compute the approximate GCD:

In[15]:= |

Out[15]= |

Find the GCD of the unnoised polynomials:

In[16]:= |

Out[16]= |

Normalize and check that the difference is close to zero:

In[17]:= |

Out[17]= |

Create a system with a known GCD and add a large noise term in y^{2} to the second polynomial along with several smaller noise terms:

In[18]:= |

A large tolerance can allow an approximate GCD to have terms of excessive degree:

In[19]:= |

Out[19]= |

With a tighter tolerance these disappear:

In[20]:= |

Out[20]= |

Wolfram Language 13.0 (December 2021) or above

- 1.0.0 – 08 July 2024

This work is licensed under a Creative Commons Attribution 4.0 International License