Polynomials: an algorithmic approach
algebraic complexityalgorithmsBerlekamp's algorithmBerlekamp-Zassenhaus algorithmBezoutiancomplex polynomialscyclotomic polynomialsdiscrete fast Fourier transformeliminationfactorization of polynomials over finite fieldsfactorization of polynomials over the ring of integersfinite fieldsheightinteger polynomialsirreducibility criteriaKronecker's factorization methodlengthLenstra-Lenstra-Lovász algorithmlocation of rootsMahler measureNiederreiter's algorithmnormpolynomial interpolationpolynomial sizespolynomialsresultantupper bounds
Introductory exposition (textbooks, tutorial papers, etc.) pertaining to number theory (11-01) Polynomials in number theory (11C08) Polynomials over finite fields (11T06) Number-theoretic algorithms; complexity (11Y16) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to field theory (12-01) Polynomials in real and complex fields: factorization (12D05) Polynomials in general fields (irreducibility, etc.) (12E05) Formal power series rings (13F25) Zeros of polynomials, rational functions, and other analytic functions of one complex variable (e.g., zeros of functions with bounded Dirichlet integral) (30C15) Symbolic computation and algebraic computation (68W30)
This book is devoted to the study of polynomials and includes several relevant algorithms (some of them classic, others more recent) with detailed analysis of their algebraic complexity. The book is structured in four chapters. The first begins with the formal definition of the ring of polynomials and with two different ways of representing polynomials: dense and sparse form. There is a study of the complexity of polynomial operations using both ways of coding. A few basic definitions and facts on polynomials are exposed (divisibility, Euclidean algorithm, gcd, factorization, roots). Some notions of elimination theory (resultant, Bezoutian) and of polynomial interpolation are given. The chapter ends with some irreducibility criteria in one and several variables. The second chapter is based in the analytic theory of complex polynomials: the authors define different polynomial sizes (norm, Mahler measure, length and height) and give upper bounds for factors of a given polynomial. Then, many interesting results on location of roots in the complex plane are shown and finally these results are applied to integer polynomials. In the third chapter, they present the theory of finite fields and cyclotomic polynomials in order to show how the discrete fast Fourier transform gives a fast algorithm to multiply polynomials. After some results on irreducible polynomials over finite fields, both Berlekamp's algorithm and Niederreiter's algorithm for factorization of polynomials over finite fields are thoroughly discussed. In the last chapter, three algorithms to give the factorization of polynomials over the ring of integers are described: Kronecker's factorization method, the Berlekamp-Zassenhaus algorithm and the Lenstra-Lenstra-Lovász (LLL) algorithm which shows that factorization of polynomials over the ring of integers can be performed in polynomial time. The book is almost self-contained and the exposition is clear but a certain background in algebra is needed. There are many interesting exercises at the end of each section, some of them extracted of recent research papers.
- On the asymptotic and practical complexity of solving bivariate systems over the reals
- Factoring polynomials over global fields
- Generating families of irreducible quartics over \(\mathbb {Q}\)
- Effective results on the Skolem problem for linear recurrence sequences
- Bounds for the moduli of zeros.
- Recent progress in exact geometric computation
- Polynomial algorithms in computer algebra
- On a problem in the theory of polynomials
- Relations and bounds for the zeros of graph polynomials using vertex orbits
- Separation bounds for polynomial systems
- Graph measures with high discrimination power revisited: a random polynomial approach
- Towards detecting structural branching and cyclicity in graphs: a polynomial-based approach
- Computational aspects of irreducible polynomials
- An analytically treatable model of long-term dynamics in a mean motion resonance with coexisting resonant modes
- On the minimum of a positive polynomial over the standard simplex
- Generalized radix representations and dynamical systems. IV
- Highly unique network descriptors based on the roots of the permanental polynomial
- Properties of graph distance measures by means of discrete inequalities
- On the Davenport-Mahler bound
- On the distribution of polynomials with bounded height
- Lifting and recombination techniques for absolute factorization
- Complexity of real root isolation using continued fractions
- Gessel-Stanton's inverse series and a system of \(q\)-polynomials
- Estimations of positive roots of polynomials
- From an approximate to an exact absolute polynomial factorization
- On the complexity of real root isolation using continued fractions
- Theory of computational complexity. Part 9. Transl. from the Russian.
- Algorithms with polynomial interpretation termination proof
- Counting and testing dominant polynomials
- Computational Aspects of a Bound of Lagrange
- The p-deformed generalized Humbert polynomials and their properties
- Generalizations of Gonçalves' inequality
- Algorithms for Symbolic Polynomials
- Algorithmische Methoden
- scientific article; zbMATH DE number 3987032 (Why is no real title available?)
- Bounds on the moduli of polynomial zeros
- scientific article; zbMATH DE number 481965 (Why is no real title available?)
- The black-box Niederreiter algorithm and its implementation over the binary field
- When does a given polynomial with integer coefficients divide another?
- A poly-algorithmic approach to simplifying elementary functions
- scientific article; zbMATH DE number 1929311 (Why is no real title available?)
- A contraction of the Lucas polygon
- Counting degenerate polynomials of fixed degree and bounded height
- Zero-free angular sectors and lens-shaped regions for polynomials, with applications to irreducibility
- NEW FAMILIES OF IRREDUCIBLE TRINOMIALS AND QUADRINOMIALS
- Improvements of Lagrange's bound for polynomial roots
- Algorithmic Polynomials
- Algorithmic polynomials
- Algorithm 960
- Robustness and Randomness
- Variation on Euclid's algorithm for polynomials
- Decomposition and Construction of Neighbourhood Operations Using Linear Algebra
- scientific article; zbMATH DE number 7660832 (Why is no real title available?)
- Polynomials
- An annulus for the zeros of polynomials
- Zero counting for a class of univariate Pfaffian functions
- On the zeros of univariate E-polynomials
- On the height of powers of a polynomial with integer coefficients
- An orthogonal class of p-Legendre polynomials on variable interval
- An Egyptian algorithm for polynomials
This page was built for publication: Polynomials: an algorithmic approach
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4248251)
