Computer Algebra is the field of study that encompasses theorems, algorithms, data structures, and software design that make it possible for a computer to do symbolic calculations. As such, it overlaps with mathematics and computer science. The words 'algebra' and 'symbolic' are used to suggest that the computer can and does solve for x and is not limited to numeric computations.
The notion of simplification is the intuitive one: given an expression, determine a simpler equivalent form. Thus x + x becomes 2x. Unfortunately, intuition only goes so far. When trying to formalize the notion of 'simple' one must pick a single form, which may not always be the desired simplification. Even with univariate polynomials it can be difficult to pick a 'simplified' form. For example, which is simpler: (x + 1)^{100} or x^{100} + ... + 1? If allowing multivariate polynomials, which is simpler: x + y or y + x? If allowing trigonometric functions, which of the following is the simplest equivalent form[ILC2005] of 1 -(1/4)sin^{2}(2x)-sin^{2}(2y)-cos^{4}(x): sin(x + y)sin(x-y) or (1/2)(cos(2y)-cos(2x))?
Often polynomial expansion is a useful simplified form. Computer algebra systems typically have a command to find this form; however, there are usually other simplification commands as well. A variation might involve expanding everything but sums raised to powers as in the first simplification example. Concerning the question what variable should come first, it is simple to pick an ordering, such as alphabetical order. However, again there are subtle issues. It seems that the Groebner basis computation is less efficient when using some orderings. Once trigonometric functions are introduced, pattern matching is the best approach.
A good place to start when solving an algebraic equation in one variable is to reduce to standard form and plug in to a formula. (Reduction to standard form is a kind of simplification, where left hand side of the equation is expanded and the right hand side is zero.) A simple equation solver based on this approach can be found here; more details of its implementation can be found in my paper Ideas Behind Computer Algebra and Their Use in the Classroom. However, when the degree of the left hand side is five or more there no longer exist formulas that involve only arithmetic and the extraction of roots. If numerical approximations are desired, there are fairly good iterative techniques that can be used to find the solutions. If exact solutions are desired, it may be possible to reduce the degree of the left hand side by searching for squared forms. Further, if the coefficients are rational numbers, there may be rational solutions, so it is worthwhile trying to factor the left hand side over the integers.
Gaussian elimination is pretty good for solving systems of linear equations. For special cases such as sparse matrices or particularly dense matrices, other techniques may have an advantage.
For non-linear systems, computing the Groebner basis yields an alternate equivalent system akin to what Gaussian elimination achieves for linear systems.
Algorithmic differentiation is not that difficult. The rules from introductory calculus can be directly translated into a program to compute the derivative of an expression. The difficult part is simplification. For example, one would like to avoid seeing 1•x + 1•x + 0 as the derivative of x•x + 5. Pattern matching can eliminate one times and zero plus, but may miss some simplifications. Polynomial representations can generate nicely simplified expressions with the caveat that they may do undesired expansion. The heuristic approach described above seems to be a good compromise for differentiation.
Algorithmic integration is difficult. Heuristic methods can often quickly find an anti-derivative given a simple expression. However, for complex expressions heuristic methods, such as those taught in first year calculus, can fail even when an anti-derivative exists. The starting point is the class of rational functions for which integration algorithms have existed for some time. An expression is then viewed as a function in an appropriate extension of the field of rational functions. Recursively integrating in successively smaller fields can determine whether an anti-derivative exists.
Abelson, Sussman. Structure and Interpretation of Computer Programs
This book is a wonderful introduction to computer science. It
provides various practical techniques for managing the complexity of
computer programs. There are many case studies including two computer
algebra related programs: differentiation and polynomial arithmetic.
Baader, Nipkow. Term Rewriting and All That
Although computer algebra systems often use algebraic techniques,
sometimes term rewriting is the best way to simplify an expression.
This book focuses on the details of term rewriting and clearly
discusses the issues of termination and confluence. Knuth-Bendix
completion is discussed as is its connection Buchberger's algorithm
for computing Groebner bases.
Bronstein. Symbolic Integration I: Transcendental Functions
This is the book for a detailed discussion of the theory and practice
of algorithmic integration of transcendental functions.
Cox, Little, O'Shea. Ideals, Varieties, and Algorithms: An
Introduction to Computational Algebraic Geometry and Commutative
Algebra
This book is simply an introduction to algebra. However, instead of
the usual treatment, the focus is on multivariate polynomials and
ideals. Thus Groebner bases are explained in only the second chapter.
Davenport, Siret, Tournier. Computer Algebra: Systems and Algorithms for Algebraic Computation
This book is a broad introduction to computer algebra as the title
suggests; however, it is short and can be quite terse. Interestingly,
the brevity often works in its favor; the authors often manage to
explain a subtle concept in a single sentence. A broad range of
topics is discussed: the representation of various mathematical
objects, simplification of polynomial systems, advanced methods for
GCDs (little space is given to elementary methods), algorithmic
integration, and techniques for solving ordinary differential
equations.
Geddes, Czapor, Labahn. Algorithms for Computer Algebra
This book is a solid introduction to computer algebra. It introduces
the ideas of polynomial representation and polynomial algebra and goes
on to discuss the issues involved in computing the GCD. It then goes
on to discuss solutions of systems of linear and non-linear polynomial
equations, and algorithmic integration. All of these discussions are
methodical and to-the-point.
Graham, Knuth, Patashnik. Concrete Mathematics
This book is an alternative to the usual discrete math text. It
includes a nice introduction to summation and goes on to describe a
more advanced summation algorithm.
Knuth. The Art of Computer Programming Vol. 2: Seminumerical Algorithms
A classic computer science text. It includes algorithms and
discussion concerning multi-precision integer arithmetic. It also
includes an introduction to GCD computation and power series
manipulation.
Norvig. Paradigms of Artificial Intelligence Programming: Case Studies in Common LISP
Although he is generally interested in artificial intelligence
techniques, two of his case studies concern computer algebra. It is
instructive to contrast the pattern-matching approach with the
polynomial approach.
Petkovsek, Wilf, Zeilberger. A=B
The authors discuss the general question of how to decide if two terms
are equal. They go on to focus on the various approaches to symbolic
summation. The book concludes with a powerful algorithm to compute
sums.
von zur Gathen, Gerhard. Modern Computer Algebra
This book is a general introduction to the subject. It also includes
applications of computer algebra. The order of the material is
unusual; it is grouped by the great mathematicians. Although the text
is fairly thick, integration and summation do not receive a full
treatment.
Zippel. Effective Polynomial Computation
Polynomial algorithms are crucial for computer algebra. This book
focuses on that subject. It includes discussion of elementary notions
of arithmetic on polynomials, as well as advanced algorithms for GCD
and factoring.