- Membership
- Publications
- Meetings
- Competitions
- Community
- Programs
- Students
- High School Teachers
- Faculty and Departments
- Underrepresented Groups
- MAA Awards
- MAA Grants

- News
- About MAA

Publisher:

Cambridge University Press

Publication Date:

2013

Number of Pages:

795

Format:

Hardcover

Edition:

3

Price:

120.00

ISBN:

9781107039032

Category:

Monograph

[Reviewed by , on ]

Allen Stenger

02/22/2014

This is a polished introduction to algorithms for performing algebraic operations on a computer, now in its third edition. The algorithms cover a number of problems, primarily in the areas of factoring polynomials and integers, primality testing, fast multiplication, and symbolic integration. It has good coverage of underlying techniques such as Gröbner bases and the Lenstra–Lenstra–Lovász (

The book has a number of shorter discussions on more specialized techniques, such as some special methods for sparse matrices. There are also several short chapters and sections on applications of the main techniques. The book is very well organized and has carefully-chosen numerical examples, which helps manage the complexity of the exposition.

The book concentrates on the mainstream results used in computer algebra systems, without attempting to be comprehensive. For example, it has a chapter on symbolic summation, but for hypergeometric functions this is essentially limited to Gosper summation with only a mention of the more comprehensive Wilf–Zeilberger method.

The book is primarily concerned with exact and symbolic operations. It concentrates on the fastest methods rather than the most straightforward, and provides execution-time analyses for all algorithms. It does not deal with numerical analysis or computer arithmetic. It does not cover work on the intersection of numerical and symbolic work, such as integer relation detection and other techniques important in experimental mathematics.

The book is almost as interesting for the advanced mathematics (mostly in ring and ideal theory and in linear algebra) that is needed to develop the algorithms. It assumes familiarity with the fundamentals of these topics, but does include a 25-page appendix summarizing the needed background. It is well-equipped with exercises, ranging from numerical practice to extensions and variants on results in the body.

Allen Stenger is a math hobbyist and retired software developer. He is webmaster and newsletter editor for the MAA Southwestern Section and is an editor of the Missouri Journal of Mathematical Sciences. His mathematical interests are number theory and classical analysis. He volunteers in his spare time at MathNerds.org, a math help site that fosters inquiry learning.

Introduction

1. Cyclohexane, cryptography, codes, and computer algebra

Part I. Euclid:

2. Fundamental algorithms

3. The Euclidean Algorithm

4. Applications of the Euclidean Algorithm

5. Modular algorithms and interpolation

6. The resultant and gcd computation

7. Application: decoding BCH codes

Part II. Newton:

8. Fast multiplication

9. Newton iteration

10. Fast polynomial evaluation and interpolation

11. Fast Euclidean Algorithm

12. Fast linear algebra

13. Fourier Transform and image compression

Part III. Gauß:

14. Factoring polynomials over finite fields

15. Hensel lifting and factoring polynomials

16. Short vectors in lattices

17. Applications of basis reduction

Part IV. Fermat:

18. Primality testing

19. Factoring integers

20. Application: public key cryptography

Part V. Hilbert:

21. Gröbner bases

22. Symbolic integration

23. Symbolic summation

24. Applications

Appendix:

25. Fundamental concepts

Sources of illustrations

Sources of quotations

List of algorithms

List of figures and tables

References

List of notation

Index.

- Log in to post comments