## Algorithms for Computer AlgebraAlgorithms for Computer Algebra is the first comprehensive textbook to be published on the topic of computational symbolic mathematics. The book first develops the foundational material from modern algebra that is required for subsequent topics. It then presents a thorough development of modern computational algorithms for such problems as multivariate polynomial arithmetic and greatest common divisor calculations, factorization of multivariate polynomials, symbolic solution of linear and polynomial systems of equations, and analytic integration of elementary functions. Numerous examples are integrated into the text as an aid to understanding the mathematical development. The algorithms developed for each topic are presented in a Pascal-like computer language. An extensive set of exercises is presented at the end of each chapter. Algorithms for Computer Algebra is suitable for use as a textbook for a course on algebraic algorithms at the third-year, fourth-year, or graduate level. Although the mathematical development uses concepts from modern algebra, the book is self-contained in the sense that a one-term undergraduate course introducing students to rings and fields is the only prerequisite assumed. The book also serves well as a supplementary textbook for a traditional modern algebra course, by presenting concrete applications to motivate the understanding of the theory of rings and fields. |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

1 | |

2 | |

4 | |

11 | |

Exercises | 20 |

Algebra Polynomials Rational Functions and Power Series | 23 |

23 Divisibility and Factorization in Integral Domains | 26 |

24 The Euclidean Algorithm | 32 |

Polynomial GCD Computation | 279 |

72 Polynomial Remainder Sequences | 280 |

73 The Sylvester Matrix and Subresultants | 285 |

74 The Modular GCD Algorithm | 300 |

75 The Sparse Modular GCD | 311 |

The EZGCD Algorithm | 314 |

77 A Heuristic Polynomial GCD Algorithm | 320 |

Exercises | 331 |

25 Univariate Polynomial Domains | 38 |

26 Multivariate Polynomial Domains | 46 |

27 The Primitive Euclidean Algorithm | 52 |

28 Quotient Fields and Rational Functions | 60 |

29 Power Series and Extended Power Series | 63 |

210 Relationships among Domains | 70 |

Exercises | 73 |

Normal Forms and Algebraic Representation | 79 |

33 Normal Form and Canonical Form | 80 |

34 Normal Forms for Polynomials | 84 |

35 Normal Forms for Rational Functions and Power Series | 88 |

36 Data Structures for Multiprecision Integers and Rational Numbers | 93 |

37 Data Structures for Polynomials Rational Functions and Power Series | 96 |

Exercises | 105 |

Arithmetic of Polynomials Rational Functions and Power Series | 110 |

42 Basic Arithmetic Algorithms | 112 |

Karatsubas Algorithm | 118 |

44 Modular Representations | 120 |

45 The Fast Fourier Transform | 123 |

46 The Inverse Fourier Transform | 128 |

47 Fast Polynomial Multiplication | 132 |

48 Computing Primitive Nth Roots of Unity | 133 |

49 Newtons Iteration for Power Series Division | 136 |

Exercises | 145 |

Homomorphisms and Chinese Remainder Algorithms | 151 |

53 Ring Morphisms | 153 |

54 Characterization of Morphisms | 160 |

55 Homomorphic Images | 167 |

56 The Integer Chinese Remainder Algorithm | 174 |

57 The Polynomial Interpolation Algorithm | 183 |

58 Further Discussion of the Two Algorithms | 189 |

Exercises | 196 |

Newtons Iteration and the Hensel Construction | 204 |

63 Newtons Iteration for Fu0 | 214 |

64 Hensels Lemma | 226 |

65 The Univariate Hensel Lifting Algorithm | 232 |

66 Special Techniques for the Nonmonic Case | 240 |

67 The Multivariate Generalization of Hensels Lemma | 250 |

68 The Multivariate Hensel Lifting Algorithm | 260 |

Exercises | 274 |

Polynomial Factorization | 336 |

83 SquareFree Factorization Over Finite Fields | 343 |

84 Berlekamps Factorization Algorithm | 347 |

85 The Big Prime Berlekamp Algorithm | 359 |

86 Distinct Degree Factorization | 368 |

87 Factoring Polynomials over the Rationals | 374 |

88 Factoring Polynomials over Algebraic Number Fields | 378 |

Exercises | 384 |

Solving Systems of Equations | 389 |

92 Linear Equations and Gaussian Elimination | 390 |

93 FractionFree Gaussian Elimination | 393 |

94 Alternative Methods for Solving Linear Equations | 399 |

95 Nonlinear Equations and Resultants | 405 |

Exercises | 422 |

Gröbner Bases for Polynomial Ideals | 429 |

102 Term Orderings and Reduction | 431 |

103 Gröbner Bases and Buchbergers Algorithm | 439 |

104 Improving Buchbergers Algorithm | 447 |

105 Applications of Gröbner Bases | 451 |

106 Additional Applications | 462 |

Exercises | 466 |

Integration of Rational Functions | 473 |

112 Basic Concepts of Differential Algebra | 474 |

Hermites Method | 482 |

Horowitz Method | 488 |

115 Logarithmic Part of the Integral | 492 |

Exercises | 508 |

The Risch Integration Algorithm | 511 |

122 Elementary Functions | 512 |

123 Differentiation of Elementary Functions | 519 |

124 Liouvilles Principle | 523 |

125 The Risch Algorithm for Transcendental Elementary Functions | 529 |

126 The Risch Algorithm for Logarithmic Extensions | 530 |

127 The Risch Algorithm for Exponential Extensions | 547 |

128 Integration of Algebraic Functions | 561 |

Exercises | 569 |

Notation | 574 |

577 | |

### Other editions - View all

Algorithms for Computer Algebra Keith O. Geddes,Stephen R. Czapor,George Labahn Limited preview - 1992 |

Algorithms for Computer Algebra Keith O. Geddes,Stephen R. Czapor,George Labahn No preview available - 2013 |

Algorithms for Computer Algebra Keith O. Geddes,Stephen R. Czapor,George Labahn No preview available - 1992 |

### Common terms and phrases

algebraic extension algebraic number Algorithm 6.1 applied arithmetic calculate Chapter Chinese remainder coefficient domain commutative ring computer algebra systems consider data structure defined Definition degree denominator denotes determine differential division element Euclidean algorithm Euclidean domain evaluation homomorphism evaluation points Example exponential expressed extended Euclidean algorithm field F GCD computation GCD's given Grobner basis hand side hence Hensel construction Hensel's lemma homomorphic image ideal integer integral domain integrand inverse irreducible leading coefficient Lemma Let a(x linear logarithmic matrix method mial mixed radix mod a(x modp modulo monic multiplication multiprecision integers multivariate polynomial Newton's iteration nonzero Note obtain operations p-adic polyno polynomial a(x polynomial domain power series primitive problem Proof quotient field rational function rational numbers recursive reduced relatively prime representation result satisfying sequence solution solving square-free factorization step subresultant symbolic Theorem tion transcendental unique unit normal univariate polynomial variables zero Zp[x