Computer Algebra: Algorithms for solving equations symbolically

As a hobby, I have written a basic computer algebra system. My CAS handles expressions as trees. I have advanced it to the point where it can simplify expressions symbolically (i.e., sin(pi/2) returns 1), and all expressions can be reduced to a canonical form. It can also do differentiation.

Using this paradigm, what kinds of algorithms are there for solving algebraic equations? An equation in my model would be represented as an (=) tree with two subtrees that are the left and right expressions. I know there is no "magic bullet" for solving all equations, but are there algorithms out there that are designed to symbolically solve an equation? If there aren't, what would be the general approach? What kind of classes can equations be split into (so that I might be able to implement an algorithm for each kind)? I don't want to use naive methods and then paint myself into a metaphorical corner.

That does not answer really the question, but I don't think that computer algebra is really about solving equations. For most kind of equations I can think about (polynomial equations, ordinary differential equations, etc), a closed-form solution using predefined primitives usually does not exist, and when it does it is less useful than the equation itself. For example, consider univariate polynomial equations. It is not always possible to solve these equations using nth-roots, and when it is, it is smarter to represent a solution of such an equation by the equation itself. With this representation you can perform addition and multiplication easily.

I my opinion, computer algebra is more about manipulating the equations themselves. For example, you have two univariate polynomial equations, virtually defining two algebraic numbers, and you want to compute the equation satisfied by the sum of these two numbers. Most of time you want the equality to be decidable. You have to delimit carefully the class of objects you are working with because if the class is too wide the equality decision problem may quickly become unsolvable, see Richardson's theorem

Of course there is numerous situations in computer algebra where one want to solve an equation. Of fundamental importance, there are linear equations, they are ubiquitous. I think also of polynomial system. In the domain of ordinary differential equations, I think of rational resolution: given an ODE, you want to find all rational solutions; or power series resolution.

To answer more precisely your question, I think you should implement first the resolution of linear system of equations. You may use Gauss' elimination. When efficiency will become an issue, you may have a look at Bareiss' algorithm. After that there is a whole bunch of various and specialised algorithms to consider.

After that, all depends on what you are interested in. You could implement algebraic numbers, polynomial factorization. You might also be interested in numerical computation, fancy linear algebra, arbitrary precision computation, etc.

There is an excellent (but old) paper describing a general method for solving equation found at http://www.research.ed.ac.uk/portal/files/413486/Solving_Symbolic_Equations_%20with_PRESS.pdf. There isn't any code but they do explain the method very clearly and thoroughly.

There are a number of books and articles on computer algebra (CA) and symbolic computation (SC) algorithms.

Note that although CA and SC sometimes are taken as meaning the same thing, CA usualy is more algebraic while SC is more symbolic (see a related presentation).

Here is Computer Algebra, Algorithms, Systems and Applications, 1999 (pdf)