SNAP - Maple Help

Home : Support : Online Help : Mathematics : Numerical Computations : SNAP Package : SNAP/QuasiGCD

SNAP

 QuasiGCD
 compute Schoenhage's quasi-GCD for a pair of univariate numeric polynomials

 Calling Sequence QuasiGCD(a, b, z, tau = eta)

Parameters

 a, b - univariate numeric polynomials z - name; indeterminate for a and b tau = eta - (optional) equation where eta is of type numeric and non-negative; stability parameter

Description

 • 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 [2] as follows. The algorithm of [2] 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 [2]. 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.

Examples

 > $\mathrm{with}\left(\mathrm{SNAP}\right):$
 > $a≔-0.2313432836{z}^{4}+0.003500000000{z}^{3}-0.1753694030{z}^{2}-0.3397276119z-0.0003395522388$
 ${a}{:=}{-}{0.2313432836}{}{{z}}^{{4}}{+}{0.003500000000}{}{{z}}^{{3}}{-}{0.1753694030}{}{{z}}^{{2}}{-}{0.3397276119}{}{z}{-}{0.0003395522388}$ (1)
 > $b≔-0.2313432836{z}^{3}+0.003731343284{z}^{2}-0.1753731343z-0.3395522388$
 ${b}{:=}{-}{0.2313432836}{}{{z}}^{{3}}{+}{0.003731343284}{}{{z}}^{{2}}{-}{0.1753731343}{}{z}{-}{0.3395522388}$ (2)
 > $\mathrm{QuasiGCD}\left(a,b,z\right)$
 ${0.125000000000000}{}{{z}}^{{3}}{-}{0.00201612903232778}{}{{z}}^{{2}}{+}{0.0947580644934703}{}{z}{+}{0.183467741918054}{,}{1.84297753606800}{}{{10}}^{{-9}}$ (3)
 > $a≔{z}^{2}+3.1z-2$
 ${a}{:=}{{z}}^{{2}}{+}{3.1}{}{z}{-}{2}$ (4)
 > $b≔2{z}^{3}+1.5$
 ${b}{:=}{2}{}{{z}}^{{3}}{+}{1.5}$ (5)
 > $\mathrm{QuasiGCD}\left(a,b,z\right)$
 ${\mathrm{FAIL}}$ (6)

References

 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.