A survey of available systems
B. David Saunders · ACM SIGSAM Bulletin · 1980
This lecture aims to cover the theoretical basis of computer algebra: to discuss the objects which computer algebra manipulates and the sort of manipulations it can perform.We will not go into great detail on the algorithms, and we will largely be concerned with questions like "Can X be computed" rather than "How do we compute X efficiently".What might we want to compute with?Integers, Rational numbers give no real problem -use "bignum" arithmetic with no intrinsic limit on the size of integers.Numbers mod p (p normally, but not necessarily, prime) are easy, and very efficient if p is small.Elements of groups (and other abstract algebraic structures) are a somewhat specialised area.Polynomials (univeriate or multivariate, since a multivariate polynomial is just a univariate polynomial whose coefficients are multivariate polynomials in fewer variables.This may not be the most efficient way, however): addition and.multiplication are easy _ g.c.d.s are possible, but factorisation is very difficult.(Note that this contrasts with non-constructive algebra, in which the ability to take g.c.d.s implies unique factorisation, and vice versa.)Rational functions (which require g.c.d.s of polynomials for practically everything) can be very timeconsuming, and there is great scope for "clever" Suggested Reading List