# 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.

-
What kind of equations? Algebra? Ordinary Differential Equations? Partial Diff Eq's? Semigroup equivalences? ... every type has its own rules – alancalvitti Feb 6 '13 at 6:01
@alancalvitti, algebraic... The type you'd do in high school. – thirtythreeforty Feb 6 '13 at 6:22
You might want to take a look at the papers describing Yacas: yacas.sourceforge.net/books.html Yacas is an open source CAS. A bit old but well documented. – Axel Kemper Feb 7 '13 at 16:30

## 5 Answers

You might start with linear and quadratic equations, and those that can be reduced to linear and quadratic equations. Next step is factoring polynomials, and that's a big step...

-
The CAS can already do basic factorization; for example, 5x-10x**2 is reduced to 5*x*(1-2*x). But what is the general approach for solving even simple equations? – thirtythreeforty Feb 3 '13 at 23:03

You have to implement differentiation first and then implement with integration which involve factorization of polynomials in order to do solver. There are quite many cases to consider.

dsolve need integration, factorization is mainly for integration, for example dy/dx = x

-
Could you elaborate? I neglected to mention that the CAS can already do differentiation. Why is integration needed to solve equations? – thirtythreeforty Feb 6 '13 at 6:22

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.

-

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).

-