+612 9045 4394
Algorithms for Computer Algebra - Keith O. Geddes


Published: 30th September 1992
Ships: 7 to 10 business days
7 to 10 business days
RRP $498.99
or 4 easy payments of $86.38 with Learn more

Algorithms 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.

`The Computer Algebra community has been waiting for years for this book to appear. ...the book is a masterpiece and can be recommended to everyone interested in the algorithms for computer algebra, either as a reference for further research or just to give the casual user an idea why things work as good (or as bad) as they do in computer algebra packages. ...the recommendation would be clear: Buy this book! As it stands now my only advice is to stay away from this book, because you might be tempted to buy it anyway (at least I was).' Computer Algebra Nederland Newsletter, June 1993

Introduction to Computer Algebra
Symbolic versus Numeric Computationp. 2
A Brief Historical Sketchp. 4
An Example of a Computer Algebra System: MAPLEp. 11
Algebra of Polynomials, Rational Functions, and Power Series
Rings and Fieldsp. 23
Divisibility and Factorization in Integral Domainsp. 26
The Euclidean Algorithmp. 32
Univariate Polynomial Domainsp. 38
Multivariate Polynomial Domainsp. 46
The Primitive Euclidean Algorithmp. 52
Quotient Fields and Rational Functionsp. 60
Power Series and Extended Power Seriesp. 63
Relationships among Domainsp. 70
Normal Forms and Algebraic Representations
Levels of Abstractionp. 79
Normal Form and Canonical Formp. 80
Normal Forms for Polynomialsp. 84
Normal Forms for Rational Functions and Power Seriesp. 88
Data Structures for Multiprecision Integers and Rational Numbersp. 93
Data Structures for Polynomials, Rational Functions, and Power Seriesp. 96
Arithmetic of Polynomials, Rational Functions, and Power Series
Basic Arithmetic Algorithmsp. 112
Fast Arithmetic Algorithms: Karatsuba's Algorithmp. 118
Modular Representationsp. 120
The Fast Fourier Transformp. 123
The Inverse Fourier Transformp. 128
Fast Polynomial Multiplicationp. 132
Computing Primitive N-th Roots of Unityp. 133
Newton's Iteration for Power Series Divisionp. 136
Homomorphisms and Chinese Remainder Algorithms
Intermediate Expression Swell: An Examplep. 151
Ring Morphismsp. 153
Characterization of Morphismsp. 160
Homomorphic Imagesp. 167
The Integer Chinese Remainder Algorithmp. 174
The Polynomial Interpolation Algorithmp. 183
Further Discussion of the Two Algorithmsp. 189
Newton's Iteration and the Hensel Construction
P-adic and Ideal-adic Representationsp. 205
Newton's Iteration for F(u)=0p. 214
Hensel's Lemmap. 226
The Univariate Hensel Lifting Algorithmp. 232
Special Techniques for the Non-monic Casep. 240
The Multivariate Generalization of Hensel's Lemmap. 250
The Multivariate Hensel Lifting Algorithmp. 260
Polynomial GCD Computation
Polynomial Remainder Sequencesp. 280
The Sylvester Matrix and Subresultantsp. 285
The Modular GCD Algorithmp. 300
The Sparse Modular GCD Algorithmp. 311
GCD's using Hensel Lifting: The EZ-GCD Algorithmp. 314
A Heuristic Polynomial GCD Algorithmp. 320
Polynomial Factorization
Square-Free Factorizationp. 337
Square-Free Factorization Over Finite Fieldsp. 343
Berlekamp's Factorization Algorithmp. 347
The Big Prime Berlekamp Algorithmp. 359
Distinct Degree Factorizationp. 368
Factoring Polynomials over the Rationalsp. 374
Factoring Polynomials over Algebraic Number Fieldsp. 378
Solving Systems of Equations
Linear Equations and Gaussian Eliminationp. 390
Fraction-Free Gaussian Eliminationp. 393
Alternative Methods for Solving Linear Equationsp. 399
Nonlinear Equations and Resultantsp. 405
Grobner Bases for Polynomial Ideals
Term Orderings and Reductionp. 431
Grobner Bases and Buchberger's Algorithmp. 439
Improving Buchberger's Algorithmp. 447
Applications of Grobner Basesp. 451
Additional Applicationsp. 462
Integration of Rational Functions
Basic Concepts of Differential Algebrap. 474
Rational Part of the Integral: Hermite's Methodp. 482
Rational Part of the Integral: Horowitz' Methodp. 488
Logarithmic Part of the Integralp. 492
The Risch Integration Algorithm
Elementary Functionsp. 512
Differentiation of Elementary Functionsp. 519
Liouville's Principlep. 523
The Risch Algorithm for Transcendental Elementary Functionsp. 529
The Risch Algorithm for Logarithmic Extensionsp. 530
The Risch Algorithm for Exponential Extensionsp. 547
Integration of Algebraic Functionsp. 561
Notationp. 575
Indexp. 577
Table of Contents provided by Blackwell. All Rights Reserved.

ISBN: 9780792392590
ISBN-10: 0792392590
Audience: Professional
Format: Hardcover
Language: English
Number Of Pages: 586
Published: 30th September 1992
Publisher: Springer
Country of Publication: NL
Dimensions (cm): 24.77 x 16.51  x 3.18
Weight (kg): 1.04