Quasi-gcd computations
For univariate polynomials with real or complex coefficients and a given error bound \(\epsilon >0\), h is called a quasi-gcd of f and g, if h is an \(\epsilon\)-approximate divisor of f and of g and if any (exact) common divisor of f, g is an approximate divisor of h. Extended quasi-gcd computation means to find such h and additional cofactors, u, v such that \(| uf+vg-h| <\epsilon | h|\) holds. Suitable pivoting leads to a numerically stable version of Euclid's algorithm for solving this task. Further refinements by a divide-and-conquer technique and by means of fast algorithms for polynomial arithmetic then yield the worst case upper bound \(O(n^ 2lg n(lg(1/\epsilon)+n lg n))\) of pointer time for nth-degree polynomials. In the particular case of integer polynomials, however, an immediate reduction to fast integer gcd computation is recommended, instead.
- A characterization of parenthesis languages
- Euclid's Algorithm for Large Numbers
- Fast computation of continued fraction expansions.
- Fast computation of GCDs
- Fast solution of toeplitz systems of equations and computation of Padé approximants
- scientific article; zbMATH DE number 3856407 (Why is no real title available?)
- scientific article; zbMATH DE number 3936514 (Why is no real title available?)
- scientific article; zbMATH DE number 3750146 (Why is no real title available?)
- On the computational power of pushdown automata
- The Computational Complexity of Continued Fractions
- The general quasi-order algorithm in number theory
- Sequential and parallel complexity of approximate evaluation of polynomial zeros
- Approximate GCD and its application to ill-conditioned algebraic equations
- Partial fraction decomposition in \(\mathbb{C}(z)\) and simultaneous Newton iteration for factorization in \(\mathbb{C}^{[z]}\)
- Feasible real random access machines
- An algorithm for computing certified approximate GCD of n univariate polynomials
- Certified approximate univariate GCDs
- Ten methods to bound multiple roots of polynomials
- Challenges of symbolic computation: My favorite open problems. With an additional open problem by Robert M. Corless and David J. Jeffrey
- Quantified constraints under perturbation
- Survey on the theory and applications of -bases for rational curves and surfaces
- Computation of approximate polynomial GCDs and an extension
- A companion matrix resultant for Bernstein polynomials
- Deterministic improvement of complex polynomial factorization based on the properties of the associated resultant
- Optimal and nearly optimal algorithms for approximating polynomial zeros
- A geometrical approach to finding multivariate approximate LCMs and GCDs
- Toward the best algorithm for approximate GCD of univariate polynomials
- Blind image deconvolution via Hankel based method for computing the GCD of polynomials
- Revisiting approximate polynomial common divisor problem and noisy multipolynomial reconstruction
- On efficiently solvable cases of quantum \(k\)-SAT
- From approximate factorization to root isolation with application to cylindrical algebraic decomposition
- Computing approximate greatest common right divisors of differential polynomials
- On the complexity of the Descartes method when using approximate arithmetic
- Computing the polynomial remainder sequence via Bézout matrices
- Matrix representation of the shifting operation and numerical properties of the ERES method for computing the greatest common divisor of sets of many polynomials
- A quadratically convergent algorithm for structured low-rank approximation
- Regularization and matrix computation in numerical polynomial algebra
- GPGCD: an iterative method for calculating approximate GCD of univariate polynomials
- Fast computation of GCDs
- A heuristic verification of the degree of the approximate GCD of two univariate polynomials
- Overdetermined Weierstrass iteration and the nearest consistent system
- On efficiently solvable cases of quantum k-SAT
- Extended QRGCD algorithm
- Minimum converging precision of the QR-factorization algorithm for real polynomial GCD
- Matrix pencil methodologies for computing the greatest common divisor of polynomials: hybrid algorithms and their performance
- Robust HGCD with no backup steps
- Validated Root Enclosures for Interval Polynomials with Multiplicities
- A deterministic algorithm for isolating real roots of a real polynomial
- SLRA Interpolation for Approximate GCD of Several Multivariate Polynomials
- A subdivision method for computing nearest gcd with certification
- Approximate polynomial GCD over integers
- A general approach to isolating roots of a bitstream polynomial
- Approximate GCD of several multivariate sparse polynomials based on SLRA interpolation
- Univariate polynomials: Nearly optimal algorithms for numerical factorization and root-finding
- Shifted varieties and discrete neighborhoods around varieties
- Relaxed NewtonSLRA for approximate GCD
- Approximate polynomial GCD: small degree and small height perturbations
This page was built for publication: Quasi-gcd computations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1071503)
