compute Schoenhage's quasi-GCD for a pair of univariate numeric polynomials
QuasiGCD(a, b, z, tau = eta)
univariate numeric polynomials
name; indeterminate for a and b
tau = eta
(optional) equation where eta is of type numeric and non-negative; stability parameter
The QuasiGCD(a, b, z) command returns a univariate numeric polynomial g with a positive float eta such that g is a quasi-GCD with precision eta for the input polynomials (a,b). (See [3,2] for a definition of a quasi-GCD in the sense of Schoenhage.)
This quasi-GCD g is derived from the stable algorithm of  as follows. The algorithm of  computes a numerical pseudo remainder sequence (ai,bi) for (a,b) in a weakly stable way, accepting only the pairs that are well-conditioned (because the others produce instability). The maximum index i for which (ai,bi) is accepted yields the quasi-GCD g=ai provided the 1-norm of bi is small enough in a sense precised in . The value of eta depends in particular on the value of bi and on the 1-norm of the residual error at the last accepted step.
If the problem is poorly conditioned, the QuasiGCD(a, b, z) command may return FAIL (rather than a meaningless answer). Here, ill-conditioning is a function of the parameter tau. Its default value is the cubic root of the current value of the Digits variable. Decreasing the value of tau yields a more reliable solution. Increasing the value of tau reduces the risk of failure.
a ≔ −0.2313432836⁢z4+0.003500000000⁢z3−0.1753694030⁢z2−0.3397276119⁢z−0.0003395522388
b ≔ −0.2313432836⁢z3+0.003731343284⁢z2−0.1753731343⁢z−0.3395522388
a ≔ z2+3.1⁢z−2
b ≔ 2⁢z3+1.5
Beckermann, B., and Labahn, G. "A fast and numerically stable Euclidean-like algorithm for detecting relatively prime numerical polynomials." Journal of Symbolic Computation. Vol. 26, (1998): 691-714.
Beckermann, B., and Labahn, G. "When are two numerical polynomials relatively prime?" Journal of Symbolic Computation. Vol. 26, (1998): 677-689.
Schoenhage, A. "Quasi-GCD computations" Journal of Complexity. Vol. 1, (1985): 118-137.
Download Help Document