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. The CAS can also differentiate expressions.

Using this paradigm, what kinds of algorithms are there for solving 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.

• This question is extremely broad. There is a whole field of computer algebra, producing new results continually. Perhaps a trip to the library is in order. Feb 6, 2013 at 7:18
• @DaveClarke Maybe gh403 could use some introductory pointers? A whole library can be daunting.
– Raphael
Feb 6, 2013 at 7:57
• You might find A=B by Petkovsek, Wilf and Zeilberger useful.
– Raphael
Feb 6, 2013 at 7:58
• @Raphael: I was thinking: Computer Algebra section. Feb 6, 2013 at 8:57
• @DaveClarke My library's searchy returns 430 hits for computer algebra. I have a feeling that "start at the top" is not going to be a fruitful strategy.
– Raphael
Feb 6, 2013 at 9:20

I am no specialist, but IMO this problem is even harder than symbolic integration, and I have not heard of a general theorem that would parallel that of Liouville. (https://en.wikipedia.org/wiki/Liouville%27s_theorem_(differential_algebra))

Of course, the case of univariate polynomials was settled by Galois, but only the degrees up to four are "easy" to handle.

Now many equations can be turned to polynomials by clever substitutions, but I have no idea of a general method to achieve that. (E.g. 9^x+3^x=5 can be reduced to quadratic. 9^x+4^x=5 can not.)

For transcendental equations that cannot be reduced to polynomial form, you are completely helpless. Needless to say, the case of systems of equations is even harder.

Now some CAS switch to numerical resolution when they cannot find a symbolic solution. But even this is challenging because though we have excellent root finders, little is said about root separation, i.e. methods that can guarantee that you have found all the roots.

The are some open source JAVA libraies with complete documentation for math/CAS like:

Jasymca, Java Algebra System and many more.

I think a good way is start with them and try to contribute more!

• Hmmm. I will look into this. Any opinions on which documentation is clearest/best? I know that is rather subjective, but I have to start somewhere. Feb 8, 2013 at 7:58
• @gh403: I recommend Jas!
– Reza
Feb 10, 2013 at 0:20

Very long time ago I attempted to do symbolic differentiations. While my code sufficed to help me solve a particular problem, I got thereby the conviction that implementing a good efficient computer algebra system must be at least as hard as writing a good compiler for a programming language. (Think e.g. of doing integrations.)

I have no knowledge to answer your listed concrete questions, like on the other hand to point out that "solving equations" seems to be a too broad issue for getting answers for your questions, there being all sorts of equations (linear, non-linear, differential, integral, etc. etc.) that are to be handled differently.

As to literature references, I suggest that you at least take a look of the following books before proceeding further with your project:

K. O. Geddes et al., Algorithms for Computer Algebra.

J. Gathen and J. Gerhard, Modern Computer Algebra.

I'm sure you'll find some references by taking a look at how Giac works. It is quite extensive so I couldn't do it myself now. Here you will many useful links. I think you might find something related to your question in the 1109 pages of documentation.