Computer Algebra: Algorithms for solving equations symbolically

Question

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.

Answer 1

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.

Answer 2

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!

Answer 3

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.

Answer 4

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.