Effective Polynomial ComputationEffective 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. |
Contents
I | 1 |
II | 3 |
III | 6 |
IV | 8 |
V | 9 |
VI | 11 |
VII | 12 |
VIII | 16 |
LX | 171 |
LXI | 173 |
LXII | 174 |
LXIII | 175 |
LXIV | 180 |
LXV | 181 |
LXVI | 182 |
LXVII | 189 |
IX | 18 |
X | 19 |
XI | 30 |
XII | 34 |
XIII | 41 |
XIV | 42 |
XV | 45 |
XVI | 50 |
XVII | 51 |
XVIII | 57 |
XIX | 58 |
XX | 64 |
XXI | 66 |
XXII | 71 |
XXIII | 73 |
XXIV | 77 |
XXV | 80 |
XXVI | 81 |
XXVII | 85 |
XXVIII | 86 |
XXIX | 88 |
XXX | 90 |
XXXI | 92 |
XXXII | 96 |
XXXIII | 98 |
XXXIV | 101 |
XXXV | 104 |
XXXVI | 107 |
XXXVII | 108 |
XXXVIII | 110 |
XXXIX | 113 |
XL | 116 |
XLI | 120 |
XLII | 123 |
XLIII | 125 |
XLIV | 126 |
XLV | 127 |
XLVI | 128 |
XLVII | 130 |
XLVIII | 132 |
XLIX | 134 |
L | 137 |
LI | 138 |
LII | 141 |
LIII | 149 |
LIV | 151 |
LV | 157 |
LVI | 158 |
LVII | 161 |
LVIII | 165 |
LIX | 167 |
LXVIII | 191 |
LXIX | 195 |
LXX | 203 |
LXXI | 207 |
LXXII | 208 |
LXXIII | 214 |
LXXIV | 215 |
LXXV | 218 |
LXXVI | 226 |
LXXVII | 231 |
LXXVIII | 232 |
LXXIX | 233 |
LXXX | 242 |
LXXXI | 243 |
LXXXII | 247 |
LXXXIII | 248 |
LXXXIV | 251 |
LXXXV | 254 |
LXXXVI | 261 |
LXXXVII | 262 |
LXXXVIII | 264 |
LXXXIX | 270 |
XC | 275 |
XCI | 278 |
XCII | 281 |
XCIII | 285 |
XCIV | 287 |
XCV | 289 |
XCVI | 293 |
XCVII | 294 |
XCVIII | 296 |
XCIX | 297 |
C | 299 |
CI | 303 |
CII | 304 |
CIII | 307 |
CIV | 309 |
CV | 312 |
CVI | 321 |
CVII | 322 |
CIX | 324 |
CX | 329 |
CXI | 330 |
CXII | 332 |
CXIII | 334 |
CXIV | 338 |
CXV | 339 |
CXVI | 341 |
| 343 | |
| 357 | |
Other editions - View all
Common terms and phrases
a₁ algebraic approach approximation arithmetic assume black box Chinese remainder Chinese remainder theorem common divisor continued fraction expansion convergents defined denote determine deterministic diophantine equations discussed in Section divides elements Euclidean algorithm evaluation points exponent F and G factorization of F finite field following proposition formal power series functions GCD algorithm GCD's gives Hensel Hensel's lemma integral domain interpolation interpolation algorithm inverse irreducible polynomial iteration Jacobian lattice leading coefficient loop Mathematics matrix modulo monic polynomial monomials multiplication multivariate polynomials nomial non-zero terms O(n² orthogonal p-adic P₁ partial quotients polynomial of degree prime number primitive probabilistic problem Proof quadratic rational integers rational number recursive reduced relatively prime representation result resx ring solution solved sparse interpolation square free square free decomposition subresultant Sylvester matrix system of equations techniques univariate polynomial values Vandermonde variable vector
Popular passages
Page 344 - M. Ben-Or and P. Tiwari. A Deterministic Algorithm For Sparse Multivariate Polynomial Interpolation.