Ebook: Effective Polynomial Computation

Effective Polynomial Computation is an introduction to the algorithms of computer algebra. It discusses the basic algorithms for manipulating polynomials including factoring polynomials. These algorithms are discussed from both a theoretical and practical perspective. Those cases where theoretically optimal algorithms are inappropriate are discussed and the practical alternatives are explained.
Effective Polynomial Computation provides much of the mathematical motivation of the algorithms discussed to help the reader appreciate the mathematical mechanisms underlying the algorithms, and so that the algorithms will not appear to be constructed out of whole cloth.
Preparatory to the discussion of algorithms for polynomials, the first third of this book discusses related issues in elementary number theory. These results are either used in later algorithms (e.g. the discussion of lattices and Diophantine approximation), or analogs of the number theoretic algorithms are used for polynomial problems (e.g. Euclidean algorithm and p-adic numbers).
Among the unique features of Effective Polynomial Computation is the detailed material on greatest common divisor and factoring algorithms for sparse multivariate polynomials. In addition, both deterministic and probabilistic algorithms for irreducibility testing of polynomials are discussed.

---

Effective Polynomial Computation is an introduction to the algorithms of computer algebra. It discusses the basic algorithms for manipulating polynomials including factoring polynomials. These algorithms are discussed from both a theoretical and practical perspective. Those cases where theoretically optimal algorithms are inappropriate are discussed and the practical alternatives are explained.
Effective Polynomial Computation provides much of the mathematical motivation of the algorithms discussed to help the reader appreciate the mathematical mechanisms underlying the algorithms, and so that the algorithms will not appear to be constructed out of whole cloth.
Preparatory to the discussion of algorithms for polynomials, the first third of this book discusses related issues in elementary number theory. These results are either used in later algorithms (e.g. the discussion of lattices and Diophantine approximation), or analogs of the number theoretic algorithms are used for polynomial problems (e.g. Euclidean algorithm and p-adic numbers).
Among the unique features of Effective Polynomial Computation is the detailed material on greatest common divisor and factoring algorithms for sparse multivariate polynomials. In addition, both deterministic and probabilistic algorithms for irreducibility testing of polynomials are discussed.

---

Effective Polynomial Computation is an introduction to the algorithms of computer algebra. It discusses the basic algorithms for manipulating polynomials including factoring polynomials. These algorithms are discussed from both a theoretical and practical perspective. Those cases where theoretically optimal algorithms are inappropriate are discussed and the practical alternatives are explained.
Effective Polynomial Computation provides much of the mathematical motivation of the algorithms discussed to help the reader appreciate the mathematical mechanisms underlying the algorithms, and so that the algorithms will not appear to be constructed out of whole cloth.
Preparatory to the discussion of algorithms for polynomials, the first third of this book discusses related issues in elementary number theory. These results are either used in later algorithms (e.g. the discussion of lattices and Diophantine approximation), or analogs of the number theoretic algorithms are used for polynomial problems (e.g. Euclidean algorithm and p-adic numbers).
Among the unique features of Effective Polynomial Computation is the detailed material on greatest common divisor and factoring algorithms for sparse multivariate polynomials. In addition, both deterministic and probabilistic algorithms for irreducibility testing of polynomials are discussed.

Content:
Front Matter....Pages i-xi
Euclid’s Algorithm....Pages 1-10
Continued Fractions....Pages 11-39
Diophantine Equations....Pages 41-55
Lattice Techniques....Pages 57-72
Arithmetic Functions....Pages 73-84
Residue Rings....Pages 85-106
Polynomial Arithmetic....Pages 107-124
Polynomial GCD’s Classical Algorithms....Pages 125-136
Polynomial Elimination....Pages 137-156
Formal Power Series....Pages 157-172
Bounds on Polynomials....Pages 173-187
Zero Equivalence Testing....Pages 189-206
Univariate Interpolation....Pages 207-229
Multivariate Interpolation....Pages 231-246
Polynomial GCD’s Interpolation Algorithms....Pages 247-259
Hensel Algorithms....Pages 261-283
Sparse Hensel Algorithms....Pages 285-291
Factoring over Finite Fields....Pages 293-302
Irreducibility of Polynomials....Pages 303-319
Univariate Factorization....Pages 321-327
Back Matter....Pages 341-363
Multivariate Factorization....Pages 329-340

---

Effective Polynomial Computation is an introduction to the algorithms of computer algebra. It discusses the basic algorithms for manipulating polynomials including factoring polynomials. These algorithms are discussed from both a theoretical and practical perspective. Those cases where theoretically optimal algorithms are inappropriate are discussed and the practical alternatives are explained.
Effective Polynomial Computation provides much of the mathematical motivation of the algorithms discussed to help the reader appreciate the mathematical mechanisms underlying the algorithms, and so that the algorithms will not appear to be constructed out of whole cloth.
Preparatory to the discussion of algorithms for polynomials, the first third of this book discusses related issues in elementary number theory. These results are either used in later algorithms (e.g. the discussion of lattices and Diophantine approximation), or analogs of the number theoretic algorithms are used for polynomial problems (e.g. Euclidean algorithm and p-adic numbers).
Among the unique features of Effective Polynomial Computation is the detailed material on greatest common divisor and factoring algorithms for sparse multivariate polynomials. In addition, both deterministic and probabilistic algorithms for irreducibility testing of polynomials are discussed.

Content:
Front Matter....Pages i-xi
Euclid’s Algorithm....Pages 1-10
Continued Fractions....Pages 11-39
Diophantine Equations....Pages 41-55
Lattice Techniques....Pages 57-72
Arithmetic Functions....Pages 73-84
Residue Rings....Pages 85-106
Polynomial Arithmetic....Pages 107-124
Polynomial GCD’s Classical Algorithms....Pages 125-136
Polynomial Elimination....Pages 137-156
Formal Power Series....Pages 157-172
Bounds on Polynomials....Pages 173-187
Zero Equivalence Testing....Pages 189-206
Univariate Interpolation....Pages 207-229
Multivariate Interpolation....Pages 231-246
Polynomial GCD’s Interpolation Algorithms....Pages 247-259
Hensel Algorithms....Pages 261-283
Sparse Hensel Algorithms....Pages 285-291
Factoring over Finite Fields....Pages 293-302
Irreducibility of Polynomials....Pages 303-319
Univariate Factorization....Pages 321-327
Back Matter....Pages 341-363
Multivariate Factorization....Pages 329-340
....