Computational Algebra Books

I don't have the second edition of this book but did read the first, and the authors do a fine job of introducing the reader to the computational side of algebraic geometry. I will forego a chapter by chapter review therefore, but no doubt the second edition (which I do not own) is as well-written as the first. I would recommend it to anyone interested in the many applications of algebraic geometry and to those who need to understand how to compute things in algebraic geometry. The good thing about this book is that it gives a concrete flavor to a highly abstract subject. Algebraic geometry, through its applications to coding theory, cryptography, and computer graphics, is fast becoming the subject to learn. It is no longer just an esoteric, high-brow subject but one that is taking on major importance in the information age. Even without applications though it is a fascinating subject, and readers will get a taste of this in this book.

This book explains and illustrates the algorithms used by symbolic math packages such as Mathematica, Maple, CoCoA, MatLab, MuPAD,... to solve problems involving polynomials in many variables, and along the way teaches the elements of real algebraic geometry-- most mathematics texts concentrate on the complex-variable version. It is not just for undergraduates; electrical engineers, for instance, should see it. Lots of pictures!

I learned the basics of Groebner bases from this book and its the best introductory book on this topic. Authors have explained all concepts with the help of examples which makes it readable for people from other fields also. It also talks about applications of Groebner bases to other fields. The book gives lot of exercises which help in understanding the contents more. I recommend that if you wish to learn Algebraic Geometry and Groebner bases then this is the book to start with.

This is the easiest introduction to algebraic geometry and commutative algebra, the authors had done a great job in writing a book that assume very little from the readers. To learn some algebraic geometry, you can either start with this book, or you can spend a year to read a lot of background materials in algebra and then go to a Graduate Text like Harris' book. Of course, if you want to be an expert in algebra, you eventually need a lot of background, what this book can help you is to offer you a quick start, much quicker than you would ever imagine.

Having just finished using this text in the course of an undergraduate seminar, I can attest to the fact that the authors' style is outstanding - they are able to synthesize an enormous amount of material in this volume and present it in a manner that is highly accessible to almost all students of mathematics. The presentation of important theorems (for example, Hilbert's Nullstellensatz and Basis Theorem) along with just the right amount of copncrete examples makes for a book of superb quality. All-around, I highly recommend this volume to anyone who has an interest in learning about Algebraic Geometry.

The author writes in the Introduction: "Much of Clifford algebra is quite simple. If this fact were generally recognized, Clifford algebra would be more widely used as a computational tool." However, a few applications discussed in the book may require some physics usually covered in the first year of graduate school.

The author starts by Clifford algebras of the 3-dimensional Euclidean space and the 4-dimensional Minkowski space-time. He discusses the Maxwell equations in flat space, the Dirac equation for the electron, the Dirac operator, spherical harmonics, and curved space-times with Schwarzschild and Kerr metrics. The book ends with matrix representation and classification of Clifford algebras of real non-degenerate quadratic spaces and an appendix on Lorentz transformations.

From a letter to the author. John, I have to write you to tell you what a wonderful book you wrote. I still can't believe how good it is. Yesterday I was waiting for a television show to begin in ten minutes and I picked your book up while I sat front of the TV set. When I finally looked up 45 minutes later, I had missed the show! In 35 years as an algebraic topologist, I have tried to learn various things about Clifford algebras because of their role in K-theory and in the Atiyah- Singer Index theorem, and more recently because of the Seiberg-Witten equations. With only mediocre intensity, mostly browsing, I have had little success. In the month since I met you and bought your book, I have browsed through it while occupied with several other competing projects. In the process I have internalized the classification of Clifford algebras, learned how physicists use Dirac's equation, what they are doing when they talk about gauge theory, understood Hodge duality much better and so the codifferential operator. And I still have only browsed through a small portion of the text. I think we mathematicians should study your book to learn how to improve our own levels of exposition. Sincerely, Daniel Henry Gottlieb

I would rate this book as a gem! To calibrate that let me say that I think Weinreich's Geometrical Vectors and Foster and Nightingale's General Relativity are gems. Chapter 1 gives a beautiful, clear and concise introduction to Clifford Algebra in flat 3-space using Dirac's anti-commuting gamma matrices. If you have ever wondered about off-hand comments that rotations are double reflections and why half angles enter into this business this is the place to get enlightened. In an amusing series of photographs the author illustrates the 4-pi periodicity of certain objects. The object here is a copy of MTW's Gravitation - one of the more imaginative uses of this tome. As an example of the application of the CA results the chapter ends with a treatment of the spinning top without using Euler's equations for rigid body motion. If you have ever struggled through Goldstein's Classical Mechanics treatment of this problem, from Euler angles to infinitessimal rotations to d-Omega which is not a differential of a vector to dyadics to body diferentials and space differentials to Euler's equations, you will really appreciate Snygg's direct solution using CA. Sure, I know Goldstein's has to be a general treatment of solid body motion and thus more complex so he can treat more general problems, but it is good to find a more direct solution that is cristal clear and only a few pages long. This chapter is real little gem. Chapter 2 takes CA to Minkowsky 4-space rotations. Chapters 3 and 4 take you to flat n-dimensional spaces and curved subspaces embedded in them. Again beautiful explanations are presented of the meaning of tangent spaces, parallel transport and how the covariant derivative arises naturally in curved spaces. I had the silly hope that with Clifford numbers and their products all would be well and done. Unfortunately the exterior product wedges its nose under the tent flap and pretty soon the exterior derivative and its side-kick the co-differential operator soon follow it into the tent. All this is explained in Chapter 7. With Chapter 5 the learning curve steepens with the introduction of Fock-Ivanenko 2-vectors and the curvature 2-vector (or 2-form) and finally the curvature tensor. Chapter 6 solves the field equations for the Schwartzchild metric based on the F-I 2-vector approach. Chapter 8 on the Dirac equation is again an approach different than that found in the usual texts. Chapter 9 derives the Kerr metric, something you won't find in MTW published 8 to 10 years after Kerr's papers. Unfortunately the starting point is some obscure problem from an earlier chapter and Snygg does not provide the delightful physical insight of earlier examples. However, there is discussion at the of the chapter. While you might be able to solve the field equations for the Schartzchild metric on your own, once you know it can be done, I certainly would not be able to do so for the Kerr metric. Snygg takes you through step by step, none of them particularly difficult, but the sequence is certainly not something I would have found by myself. Chapter 10 I only skimmed, the index notation, with underscored and bracketed indices, becomes overloaded for my level of sophistication. Chapter 11 organizes all the matrix stuff together, again a beautiful, straightforward and clear presentation. Here is shown how to construct a matrix representation for the gammas. As you might expect, the book is a veritable beehive of sub- and superscripts over bars and carets Greek and Latin indices and full of gamma gymnastics. Even Pauli's less complementary comment on Dirac algebra comes to mind. The text has a few typos but blessedly few in the Clifford number and gamma indices. By the way, if you expect to find out how to do trace computations on gamma expressions you won't find it here. The explicit form of the gamma matrices is hardly ever mentioned until chapter 11 nor is it needed in the present context.

The author is my brother. You may doubt the credibility of my commentary, but check it out for yourself. Based on an early draft, I predict it will be a pedagogical gem. Style and content make anything John Snygg writes a pleasure to read. Snygg is a hidden treasure. As of October 1996, "Clifford Algebra: A Computational Tool for Physicists" was not out.

Snygg's book is a thoroughly delightful introduction to Clifford Algebra and its applications in physics. It is detailed, readable, and at times even humorous... but always clear and educational. Snygg presents Clifford Algebra above all as a practical tool, rather than as the ultimate algebraic representation of spatial geometry. This gives a refreshing alternative to Hestenes' writings which, although quite good, can at times be philosophically pedantic and difficult to connect with standard theory.

The book is excellent for teaching approximation algorithms. The book was new, but I benefit of a reduced price (probably promotional).

This book is a great sequel to Garey and Johnson. The appendix of this book gives a list of all NP optimisation problems together with their current approximability (or inapproximability results) in a Garey Johnson fashion.

Developing approximation algorithms for NP hard problems is now a very active field in Mathematical Programming and Theoretical Computer Science. There have been a number of exciting developments like semidefinite programming , the Goemans Williamson algorithm for max cut et al.

On the other hand, from a theoretical computer science point of view, we now have a proof that many of these problems cannot have polynomial approximation algorithms unless P=NP.

This book provides an excellent introduction to both areas. A worthy supplement to Garey and Johnson, Papadimitriou's books on combinatorial optimisation and computational complexity, Hochbaum's book on approximation algorithms, Alon and Spencer's book on the probabilistic method and finally Motwani and Raghavan's book on randomised algorithms.

This book is a great sequel to Garey and Johnson. The appendix of this book gives a list of all NP optimisation problems together with their current approximability (or inapproximability results) in a Garey Johnson fashion.

Developing approximation algorithms for NP hard problems is now a very active field in Mathematical Programming and Theoretical Computer Science. There have been a number of exciting developments like semidefinite programming , the Goemans Williamson algorithm for max cut et al.

On the other hand, from a theoretical computer science point of view, we now have a proof that many of these problems cannot have polynomial approximation algorithms unless P=NP.

This book provides an excellent introduction to both areas. A worthy supplement to Garey and Johnson, Papadimitriou's books on combinatorial optimisation and computational complexity, Hochbaum's book on approximation algorithms, Alon and Spencer's book on the probabilistic method and finally Motwani and Raghavan's book on randomised algorithms.

I bought this book for the math course I had taken having the same title. This is an excellent book, but only if you are really interested in its content. It's not a casual read, since it's graduate text. Also, a background in number theory will be of great help - being a CS major, I had a little tough time in the beginning, but things turned out just fine. As for content, it has excellent coverage of the subject, and I would highly recommend this as a reference in this subject. Remember, though, that this book deals COMPUTATIONAL aspects, for only number theory, look for other books like Ireland-Rosen.

This book is an excellent compilation of both the theory and pseudo-code for number theoretic algorithms. The author also takes the time to prove some of the major results as background to the algorithms, in addition to sets of exercises at the end of the book. The book is too large to do a chapter by chapter review, so instead I will list the algorithms in the book that I thought were particularly useful:

1. Most of the algorithms on elliptic curves. The author reminds the reader that number-theoretical experiments resulted in the famous Swinnerton-Dyer Conjecture and the Birch Conjecture. (a) the reduction algorithm, which for a given point in the upper half plane, gives the unique point in the half plane equivalent to this point under the action of the special linear group along with the matrix that maps these two points to each other. (b) The computation of the coefficient g2 and g3 of the Weierstrass equation of an elliptic curve. (c) The computation of the Weierstrass function and its derivative. (d) Determination of the periods of an elliptic curve over the real numbers. (e) The determination of the elliptic logarithm. (f) The reduction of a general cubic (f) The Shanks-Mestre algorithm for computing the order of an elliptic curve over a finite field F(p), where p is prime and greater than 457. (g) The reduction of an elliptic curve modulo p for p > 3. (h) The reduction of an elliptic curve modulo 2 or 3. (i) Reduction of an elliptic curve over the rational numbers. (j) Determination of the rational torsion points of an elliptic curve. (k) Computation of the Hilbert class polynomials and thus a determination of the j-function of an elliptic curve.

2. A few of the algorithms on factoring. (a) The Pollard algorithm for finding non-trivial factors of composites. (The author does not give the improved algorithm due to P. Montgomery, but does give references) (b) Shanks Square Form Factorization algorithm for finding a non-trivial factor of an odd integer. (c) Lenstra's Elliptic Curve test for compositeness.

3. Primality tests (a) The Jacobi Sum Primality Test for a positive integer. (b) Goldwasser-Killian elliptic curve test for a positive integer not equal to 1 and coprime to 6.

The author gives an overview of the computer packages used for number theory, including Pari, which was written by him and his collaborators. I have not used this package, but instead use Lydia and Mathematica for most of the number theoretic computations I need to do.

Cohen (the world renowned expert) starts with the most basic of algorithms (i.e. Euclid & Shanks). He moves seamlessly into Linear Algebra & Polynomials (bedrocks of most CAS). Although meant to be concise, he proves, or sketches a proof of the important results. Finally, the meat of the book, C.A.N.T. One important problem is finding the "class number" (has to do with unique factorization, which we are all accustomed to in Z). A detailed description of the continued fraction algorithm (for finding the fundamental unit), and others made it very enlightening. He then deals with primality testing and factoring, two very important problems, the latter because of RSA. First, a description of the algorithm, then the theory behind it. He covered everything, from Trial Division (Dark Ages) to Pollard Rho to NFS (cutting-edge). Also included are some useful tables.

Of course, CAS information from 1993, won't be that helpful (look in his newest, Advanced Topics in C.A.N.T.).

Excellent. Also try Knuth's "Semi-numerical Algorithms" for a more computer oriented approach.

I'm a student digging into the cryptology for an year. The more article I read, the more confusion I encounter because of my poor mathematical background. However, when I get this, I could find answer to my puzzles, and make an more explicit way to settle down my own idea.

This book is a marvel. It is clear and concise yet thorough. The author is obviously a bit of an obsessive compulsive, he has found the shortest paths from the clearest definitions to the most important results, each given with the cleanest, most insight-inducing proofs ... the results (and definitions) he gives are the ones any student (practitioner!) of modern computer science (especially cryptology) *needs* to know -- having this book on your shelves (and its contents in your head) should be a requirement for any degree, at any level, in computer science.
[Caveat: I know the author and have read his book in draft form. I also required my students to get it and read it, in a computer science course I taught.]

This book presents an excellent and thorough introduction and overview of the field. It contains results of 573 papers in the field, but requires few prerequisites beyond basic abstract and linear algebra. It's perfect for independent study.

The key parts of the book for those interested in the matrix multiplication problem, like myself, and related problems are chapters 14-18. Chapter 14 describes the theory of the multiplicative complexity of bilinear maps, of which matrix multiplication is one, in terms of the concept of rank (also tensor rank), especially in the context of matrix algebras. The rank of a bilinear map is essentially a measure of the minimum number of multiplications in a bilinear algorithm for computing the map. Chapter 15 introduces the exponent of matrix multiplication in relation to the asymptotic complexity of the latter, and describes the fundamental relations between these asymptotic and bilinear measures, including the proof of Schonhage's important asymptotic direct sum inequality. Chapter 16 shows the fundamental importance of the exponent because it is found to determine the complexities of other important matrix operations such as inversion, taking of determinants, computing of characteristic polynomials etc. Chapters 17 and 18 describe further extensions, applications and links, including an interesting link between the ranks of finite fields and the minimal distances of linear error-correcting codes.

I will not say this book is an introduction but that its a confusion remover for a serious student of algebraic geometry. This book I consider a part of the much needed revolution happening in algebraic geometry which means that if you browse or spend time reading a book you must learn something. Excellent coverage of a fascinating subject. Enjoy!

This book represents the results of the last 25 years of study of polynomial Identities. The chapter heading of the book describe the major development areas:

Affine PI-algebras
T-Ideals and Relatively Free Algebras
Specht's Problem in the Affine Case
Representation fof Sn and Their Applications
Superidentities and Kemer's Main Theorem
Pi-Algebras in Characteristic p
Recent Structural Results
Poincare-Hilbert Series and Gelfand-Kirillov Dimension
More Representation Theory
Unified Theory of Identities
Trace Identities.

This book would be quitable for a graduate level course

I used this for a course taught by Prof. Sewell and found it stretched me to my limits, but did what it was meant to do. By the time we worked through it, I had a working knowledge of the various methods used to solve massive systems of equations while conserving computing time. It's strongly recommended that you have a prior course in Linear Algebra, and I can see why - I, as it happens, did not (though I've had several courses that touched on linear algebra) and I'm sure that made me struggle all the more... especially with many of the proofs (always my weakest link).

You'll also want to own/use either MATLAB or FORTRAN to work through the programs in this text. Don't skimp here - they're critical for developing a deep understanding of the algorithms discussed!

In all, it was a great book and a great class!

Handbook of Computational Group Theory by Derek F. Holt (Discrete Mathematics and Its Applications: Chapman & Hall/CRC) is about computational group theory, which we shall frequently abbreviate to CGT. The origins of this lively and active branch of mathematics can he traced back to the nineteenth and early twentieth centuries, but it has been flourishing particularly during the past 30 to 40 years. The aim of this book is to provide as complete a treatment as possible of all of the fundamental methods and algorithms in CGT, without straying above a level suitable for a beginning postgraduate student.
The most basic algorithms in CGT tend to be representation specific; that is, there are separate methods for groups given as permutation or matrix groups, groups defined by means of polycyclic presentations, and groups that are defined using a general finite presentation. The author has devoted separate chapters to algorithms that apply to groups in these different types of repre¬sentations, but there are other chapters that cover important methods involving more than one type. For example, Chapter 6 is about finding presentations of permutation groups and the connections between coset enumeration and methods for finding the order of a finite permutation group.
There is also included a chapter (Chapter 11) on the increasing number of precomputed stored libraries and databases of groups, character tables, etc. that are now publicly available. They have been playing a major rôle in CGT in recent years, both as an invaluable resource for the general mathematical public, and as components for use in some advanced algorithms in CGT. The library of all finite groups of order up to 2000 (except for order 1024) has proved to be particularly popular with the wider community.
It is inevitable that our choice of topics and treatment of the individual topics will reflect the authors' personal expertise and preferences to some extent. On the positive side, the final two chapters of the book cover appli¬cations of string-rewriting techniques to CGT (which is, however, treated in much greater detail, and the application of finite state automata to the computation of automatic structures of finitely presented groups. On the other hand, there may be some topics for which our treatment is more superficial than it would ideally be.
One such area is the complexity analysis of the algorithms of CGT. During the 1980s and 1990s some, for the most part friendly and respectful, rivalry developed between those whose research in CGT was principally directed to-wards producing better performance of their code, and those who were more interested in proving theoretical results concerning the complexity of the al¬gorithms. This study of complexity began with the work of Eugene Luks, who established a connection in his 1982 article between permutation group algorithms and the problem of testing two finite graphs for isomorphism. Our emphasis in this book will be more geared towards algorithms that per-form well in practice, rather than those with the best theoretical complexity. Fortunately, Seress' book includes a very thorough treatment of com¬plexity issues, and so we can safely refer the interested reader there. In any case, as machines become faster, computer memories larger, and bigger and bigger groups come within the range of practical computation, it is becom¬ing more and more the case that those algorithms with the more favourable complexity will also run faster when implemented.
The important topic of computational group representation theory and computations with group characters is perhaps not treated as thoroughly as it might be in this book. Some of the basic material is covered in Chapter 7, but there is unfortunately no specialized book on this topic.
One of the most active areas of research in CGT at the present time, both from the viewpoint of complexity and of practical performance, is the development of effective methods for computing with large finite groups of matrices. Much of this material is beyond the scope of this book. It is, in any case, developing and changing too rapidly to make it sensible to attempt to cover it properly here. Some pointers to the literature will of course be provided, mainly in Section 7.8.
Yet another topic that is beyond the scope of this book, but which is of increasing importance in CGT, is computational Lie theory. This includes computations with Coxeter groups, reflection groups, and groups of Lie type and their representations. It also connects with computations in Lie algebras, which is an area of independent importance. The article by Cohen, Murray, and Taylor provides a possible starting point for the interested reader.
The author firmly believes that the correct way to present a mathematical algorithm is by means of pseudocode, since a textual description will generally lack precision, and will usually involve rather vague instructions like "carry on in a similar manner". So we have included pseudocode for all of the most basic algorithms, and it is only for the more advanced procedures that we have occasionally lapsed into sketchy summaries. We are very grateful to Thomas Cormen who has made his LATEX package `clrscode' for displaying algorithms publicly available. This was used by him and his coauthors in the well-known textbook on algorithms.
Although working through all but the most trivial examples with procedures that are intended to be run on a computer can be very tedious, the author attempted to include illustrative examples for as many algorithms as is practical.
At the end of each chapter, or sometimes section, the reader's attention directed to some applications of the techniques developed in that chapter either to other areas of mathematics or to other sciences. It is generally difficult to do this effectively. Although there are many important and interesting applications of CGT around, the most significant of them will typically use methods of CGT as only one of many components, and so it not possible to do them full justice without venturing a long way outside of the main topic of the book.
The author assumes that the reader is familiar with group theory up to an advanced undergraduate level, and has a basic knowledge of other topics in algebra, such as ring and field theory. Chapter 2 includes a more or less complete survey of the required background material in group theory, but we shall assume that at least most of the topics reviewed will be already familiar to readers. Chapter 7 assumes some basic knowledge of group representation theory, such as the equivalence between matrix representations of a group G over a field K and KG-modules, but it is interesting to note that many of the most fundamental algorithms in the area, such as the `Meataxe', use only rather basic linear algebra.