Quasi-gcd computations

DOI10.1016/0885-064X(85)90024-XzbMath0586.68031MaRDI QIDQ1071503

Arnold Schönhage

Publication date: 1985

Published in: Journal of Complexity (Search for Journal in Brave)

zbMATH Keywords

algebraic complexityunivariate polynomialsapproximate divisornumerically stable version of Euclid's algorithmworst case upper bound

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Polynomials in real and complex fields: factorization (12D05)

Related Items (42)

Shifted varieties and discrete neighborhoods around varieties ⋮ A quadratically convergent algorithm for structured low-rank approximation ⋮ Relaxed NewtonSLRA for approximate GCD ⋮ Sequential and parallel complexity of approximate evaluation of polynomial zeros ⋮ Certified approximate univariate GCDs ⋮ Deterministic improvement of complex polynomial factorization based on the properties of the associated resultant ⋮ Optimal and nearly optimal algorithms for approximating polynomial zeros ⋮ Survey on the theory and applications of \(\mu\)-bases for rational curves and surfaces ⋮ A deterministic algorithm for isolating real roots of a real polynomial ⋮ Revisiting approximate polynomial common divisor problem and noisy multipolynomial reconstruction ⋮ GPGCD: an iterative method for calculating approximate GCD of univariate polynomials ⋮ Validated Root Enclosures for Interval Polynomials with Multiplicities ⋮ SLRA Interpolation for Approximate GCD of Several Multivariate Polynomials ⋮ Ten methods to bound multiple roots of polynomials ⋮ Unnamed Item ⋮ A geometrical approach to finding multivariate approximate LCMs and GCDs ⋮ A subdivision method for computing nearest gcd with certification ⋮ Approximate polynomial GCD over integers ⋮ On the complexity of the Descartes method when using approximate arithmetic ⋮ Computing the polynomial remainder sequence via Bézout matrices ⋮ A heuristic verification of the degree of the approximate GCD of two univariate polynomials ⋮ A general approach to isolating roots of a bitstream polynomial ⋮ On efficiently solvable cases of quantum \(k\)-SAT ⋮ Overdetermined Weierstrass iteration and the nearest consistent system ⋮ Approximate GCD and its application to ill-conditioned algebraic equations ⋮ Toward the best algorithm for approximate GCD of univariate polynomials ⋮ Blind image deconvolution via Hankel based method for computing the GCD of polynomials ⋮ From approximate factorization to root isolation with application to cylindrical algebraic decomposition ⋮ Regularization and Matrix Computation in Numerical Polynomial Algebra ⋮ Univariate polynomials: Nearly optimal algorithms for numerical factorization and root-finding ⋮ Matrix pencil methodologies for computing the greatest common divisor of polynomials: hybrid algorithms and their performance ⋮ GPGCD, an Iterative Method for Calculating Approximate GCD, for Multiple Univariate Polynomials ⋮ Approximate polynomial GCD: small degree and small height perturbations ⋮ Matrix representation of the shifting operation and numerical properties of the ERES method for computing the greatest common divisor of sets of many polynomials ⋮ Computing approximate greatest common right divisors of differential polynomials ⋮ Partial fraction decomposition in \(\mathbb{C}(z)\) and simultaneous Newton iteration for factorization in \(\mathbb{C}^{[z}\)] ⋮ Feasible real random access machines ⋮ Challenges of symbolic computation: My favorite open problems. With an additional open problem by Robert M. Corless and David J. Jeffrey ⋮ An algorithm for computing certified approximate GCD of \(n\) univariate polynomials ⋮ Computation of approximate polynomial GCDs and an extension ⋮ Quantified constraints under perturbation ⋮ A companion matrix resultant for Bernstein polynomials

Uses Software

• GCDHEU

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the computational power of pushdown automata
• Fast computation of continued fraction expansions.
• The Computational Complexity of Continued Fractions
• Fast solution of toeplitz systems of equations and computation of Padé approximants
• Fast computation of GCDs
• A characterization of parenthesis languages
• Euclid's Algorithm for Large Numbers

This page was built for publication: Quasi-gcd computations