An O(n log ^3 n) Algorithm for the Real Root Problem

Given a univariate complex polynomial f(x) of degree n with rational coefficients expressed as a ratio of two integers >

Authors

• John H. Reif

Keywords

• Eigenvalues and eigenfunctions
• Polynomials
• Arithmetic
• Symmetric matrices
• Read-write memory
• Contracts
• Algebra
• Computational modeling
• Postal services
• Computer science
• Real Problems
• Algorithm For Problem
• Real Roots
• Root Of The Problem
• Arithmetic Operations
• Roots Of Polynomial
• Univariate Polynomial
• Rational Coefficients
• Deflation
• Symmetric Matrix
• Sparse Matrix
• Newton Method
• Polynomial Of Degree
• Problem Of Finding
• Complex Integration
• Complex Plane
• Characteristic Polynomial
• Class Of Matrices
• Sum Of Power
• N Log N
• Root-finding
• Monic Polynomial
• Real Coefficients
• Quadratic Time
• Distinct Roots
• Complex Roots
• Triangular Systems
• Indeterminism
• Linear System