Back to Search
Start Over
A Fast Version of the Schur–Cohn Algorithm
- Source :
- Journal of Complexity. 16:54-69
- Publication Year :
- 2000
- Publisher :
- Elsevier BV, 2000.
-
Abstract
- In this paper we describe a fast algorithm for counting the number of roots of complex polynomials in the open unit disk, classically called the Schur–Cohn problem. For degree d polynomials our bound is of order d log 2 d in terms of field operations and comparisons, but our approach nicely allow us to integrate the bit size as a further complexity parameter as well. For bit size σ of input polynomials of Z [ X ] our running time is of order d 2 σ ·log( dσ )·log log( dσ )·log( d ) in the multi-tape Turing machine model, thus improving all previously proposed approaches.
- Subjects :
- Statistics and Probability
Numerical Analysis
Control and Optimization
Algebra and Number Theory
Degree (graph theory)
Applied Mathematics
General Mathematics
Field (mathematics)
Unit disk
Fast algorithm
Running time
Combinatorics
Turing machine
symbols.namesake
symbols
Order (group theory)
Complex quadratic polynomial
Algorithm
Mathematics
Subjects
Details
- ISSN :
- 0885064X
- Volume :
- 16
- Database :
- OpenAIRE
- Journal :
- Journal of Complexity
- Accession number :
- edsair.doi.dedup.....ae2d1baa059951f46bccdbe0e35b3dfe