Terms and Conditions:
Chee Keng Yap wrote:This preliminary version may be freely copied, in part or wholly, and distributed for private or class use, provided this copyright page is kept intact with each copy.
These notes were first written for a course on Algebraic Computing: Solving Systems of Polynomial Equations, given at the Free University of Berlin
. They were thoroughly revised following a similar course at the Courant Institute
. Prerequisites are an undergraduate course in algebra and a graduate course in algorithmics.
These notes should be regarded as an introduction to computer algebra
which uses quite distinct techniques, and satisfies requirements distinct from that in numerical analysis
. In many areas of computer application (robotics, computer aided design. geometric modeling, etc) computer algebra is now recognized as an essential tool. This is partly driven by the wide-spread availability of powerful computer work-stations, and the rise of a new generation of computer algebra systems
such as Mathematica
to take advantage of this computing power.
The book consists of a selection of topics that are appropriate for bringing a student or researcher up to date on a spectrum of optimal-complexity algorithms. After some preliminary material, the tasks discussed range from fast integer multiplication using the fast Fourier transform, through greatest common divisor, subresultants, polynomial root isolation, factoring, linear and nonlinear elimination (Grbner bases), and polynomial ideal theory, to continued fractions.
The style of the book has been kept close to the lecture form in which this material originally existed. Of course, the lecture material is considerably expanded. This mainly consisted of the filling in of mathematical background; a well-equipped student may skip this.
:idea: Richard Fateman
, Computing Reviews
"I see it as a sequel to a course in modern algebra for students interested in complexity aspects of constructive mathematics. For graduate students and researchers, it is an excellent review of the chosen topics with contemporary references."
:idea: Arjeh M. Cohen
, Mathematics of Computation
"... it is an almost self-contained treatment of the most basic topics in computer algebra, well presented, and with good attention to complexity issues."