SNAP - Maple Help

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

SNAP

 DistanceToCommonDivisors
 compute a lower bound on the distance between a pair of univariate polynomials and the set of univariate polynomial pairs with a common root
 DistanceToSingularPolynomials
 compute a lower bound on the distance between a univariate polynomial and the set of univariate polynomials with a double root

 Calling Sequence DistanceToCommonDivisors(a, b, z, tau = eps, out) DistanceToSingularPolynomials(a, z, tau = eps, out)

Parameters

 a, b - univariate numeric polynomials z - name; indeterminate for a and b tau = eps - (optional) equation where eps is of type numeric and non-negative; stability parameter out - (optional) equation of the form output = obj where obj is one of 'LB', 'BC', 'E', 'LAB', 'QGCD', 'RB' or 'UR', or a list containing one or more instances of these names; select result objects to compute

Description

 • The DistanceToCommonDivisors(a, b, z) command returns a lower bound on the distance between (a,b) and the set of univariate complex polynomial pairs in z with degrees that do not exceed those of a and b, and that have at least one common root. Thus, the input polynomials a and b are regarded as polynomials in z.
 This lower bound is a non-negative floating-point number obtained by computing in a weakly stable way the first and the last columns of the inverse of the Sylvester matrix defined by polynomials a and b. More precisely, denoting these two columns by c1 and c2, the lower bound is defined in [1] as the inverse of || [c1, c2] ||.
 Here, the norm || || is based on the classical 1-norm for vectors. If C is an m by n matrix, || C || is the maximum value of the sum sum(abs(C[i, j]), i=1..m) for j=1..n.
 If the problem of computing the columns c1, c2 from the Sylvester matrix S is well-conditioned, the DistanceToCommonDivisors(a, b, z) call returns the above lower bound. Otherwise, FAIL is returned because a numerical answer would be meaningless ("weak stability"). However, the cause of failure can be displayed by setting infolevel[DistanceToCommonDivisors] to 5.
 • The DistanceToSingularPolynomials(a, z) command returns a lower bound on the distance between a univariate numeric polynomial and the set of univariate complex polynomials with a double root. It essentially calls DistanceToSingularPolynomials(a, b, z) with b = diff(a, z).
 • The optional stability parameter tau can be set to any non-negative value eps to control the quality of the output. Decreasing eps yields a more reliable solution. Increasing eps reduces the risk of failure.
 • The output option (out) determines the content of the returned expression sequence.
 As specified by the out option, Maple returns an expression sequence containing one or more of the following quantities:
 * The lower bound LB is a non-negative float or FAIL.
 * The list BC is equal to [v, u], the numeric polynomials in z that satisfy av+bu=1 and $\mathrm{degree}\left(u,z\right)<\mathrm{degree}\left(a,z\right)$ and $\mathrm{degree}\left(v,z\right)<\mathrm{degree}\left(b,z\right)$ (bezout coefficients for coprime polynomials a and b). This list is empty if and only if the algorithm fails to compute a reliable lower bound.
 * The list LAB is equal to [a', b'] where a', b' are the numeric polynomials in z that define the last accepted basis in [2].
 * E can take the following values: the residual error for the computed lower bound (which allows the verification of the numerical quality of the solution). If no reliable lower bound is computed and if an epsilon-GCD g for (a, b) is found, then $E=\mathrm{ϵ}$ and g = a' (that is, the first component of the last accepted basis) when $\mathrm{degree}\left(b,z\right)<\mathrm{degree}\left(a,z\right)$ and g = b' (that is, the second component of the last accepted basis) when $\mathrm{degree}\left(a,z\right)<\mathrm{degree}\left(b,z\right)$. If no epsilon-GCD for (a, b) is found, $E=\mathrm{FAIL}$.
 * QGCD can take the following values: the precision of the quasi-GCD found; in this case, the quasi-GCD is a', the first component of the last accepted basis. When no quasi-GCD is found, $\mathrm{QGCD}=\mathrm{FAIL}$.
 * List RB of the indices of all the bases (see [2]) rejected during the computation.
 * UR contains a 2 by 2 unimodular matrix polynomial U in z such that $\left(a,b\right).U=\left(a',b'\right)$ where (a', b') is the last basis accepted by the algorithm of [2].

Examples

 > $\mathrm{with}\left(\mathrm{SNAP}\right):$
 > $a≔{z}^{2}+3.1z-2$
 ${a}{:=}{{z}}^{{2}}{+}{3.1}{}{z}{-}{2}$ (1)
 > $b≔2{z}^{3}+1.5$
 ${b}{:=}{2}{}{{z}}^{{3}}{+}{1.5}$ (2)
 > $\mathrm{DistanceToCommonDivisors}\left(a,b,z\right)$
 ${0.876183368229130}$ (3)
 > $\mathrm{dist}≔\mathrm{DistanceToCommonDivisors}\left(a,b,z,\mathrm{output}=\left['\mathrm{LB}','\mathrm{BC}'\right]\right)$
 ${\mathrm{dist}}{:=}{0.876183368229130}{,}\left[{-}{0.265488243398524}{}{{z}}^{{2}}{-}{0.124626264127645}{}{z}{-}{0.144635068001349}{,}{0.132744121699262}{}{z}{+}{0.473819909331534}\right]$ (4)
 > $\mathrm{fnormal}\left(\mathrm{expand}\left(a{{\mathrm{dist}}_{2}}_{1}+b{{\mathrm{dist}}_{2}}_{2}\right)\right)$
 ${1.}$ (5)

A call to DistanceToSingularPolynomials(a,z) is essentially a call to DistanceToCommonDivisors(a,diff(a,z),z).

 > $a≔{z}^{2}+3.1z-2$
 ${a}{:=}{{z}}^{{2}}{+}{3.1}{}{z}{-}{2}$ (6)
 > $\mathrm{DistanceToSingularPolynomials}\left(a,z\right)$
 ${0.598572399728076}$ (7)
 > $b≔\frac{\partial }{\partial z}a$
 ${b}{:=}{2}{}{z}{+}{3.1}$ (8)
 > $\mathrm{DistanceToCommonDivisors}\left(a,b,z\right)$
 ${0.598572399728076}$ (9)

References

 Beckermann, B., and Labahn, G. "A fast and numerically stable Euclidean-like algorithm for detecting relativly 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.