Algorithm(s) for rearranging simple symbolic algebraic expressions

Question

I would like to know if there is a straightforward algorithm for rearranging simple symbolic algebraic expressions. Ideally I would like to be able to rewrite any such expression with one variable alone on the left hand side. For example, given the input:

m = (x + y) / 2

... I would like to be able to ask about x in terms of m and y, or y in terms of x and m, and get these:

x = 2*m - y
y = 2*m - x

Of course we've all done this algorithm on paper for years. But I was wondering if there was a name for it. It seems simple enough but if somebody has already cataloged the various "gotchas" it would make life easier.

For my purposes I won't need it to handle quadratics.

(And yes, CAS systems do this, and yes I know I could just use them as a library. I would like to avoid such a dependency in my application. I really would just like to know if there are named algorithms for approaching this problem.)

Answer 1

What you want is equation solving algorithm(s). But i bet that this is huge topic. In general case, there may be:

• system of equations
• equations may be non-linear, thus additional algorithms such as equation factorization needed.
• knowledge how to reverse functions is needed,- for example => sin(x) + 10 = z, solving for x we reverse sin(), which is arcsin(). (Not all functions may be reversible !)
• finally some equations may be hard-solvable even for CAS, such as sin(x)+x=y, solve for x.

Hard answer is - your best bet is to take source code of some CAS,- for example you can take a look at MAXIMA CAS source code which is written in LISP. And find code which is responsible for equation solving.

Easy answer - if all that you need is solving equation which is linear and is composed only from basic operators +-*/. Then you know answer already - use old good paper method - think of what rules we used on paper, and just re-write these rules as symbolic algorithm which manipulates equation string.

good luck !

Answer 2

It seems like what you're interested in doing is maintaining a system of linear equations and then, at any time, being able to solve for one variable in terms of all the others. If you encode the relationships as a matrix, it seems like you could then reduce the matrix to some nice form (for example, reduced row echelon form) to get the "simplest" dependencies amongst the variables (for some nice definition of "simplest.") Once you have the data like this, you should be able to read off all the dependencies by just looking at some row that has a nonzero entry for the variable in question, then normalizing it so that the variable has coefficient one.

A note - in general, you won't always get a unique solution for each variable. For example, given the trivial equations

x = y
x = z

Then solving for z could yield either "z = x" or "z = y," depending on how much simplification you want. Or alternatively, in a setup like

x = 2y + 3w
x = 9z

Returning a value for x could hand back either expression, or their sum over two, or a whole bunch of other things that are all technically true but not necessarily useful. I'm not sure how you'd handle this, but depending on the form of your equations you can probably find a way to handle it.

Answer 3

Convert your expression into a data structure (tree) in reverse Polish notation. Your tree is made up of nodes, each node has an operation, a left and a right. Each of the left and right can be a symbol (eg: "x") or another node. For example:

(x + (a + b))

Would become:

(+ x (+ a b))

Or in JSON:

["+", "x", ["+", "a", "b"]]

Your original expression m = (x + y) / 2 would look like this:

m = ["/", ["+", "x", "y"], "2"]

One of your desired expressions (solving for x) looks like this:

x = ["-", ["*", "m", "2"], "y"]

Can you see that the tree of expressions has been turned inside out and each operator has been reversed? The "-" is the reverse of the "+" and now wraps the "*" which is a reverse of the "/". The:

["+", "x", "y"]

Becomes:

["-", (something), "y"]

Where (something) is a reversal of the outer expression recursively. To try to explain the process: a) recursively descend the expression tree until you find the node containing the symbol you want to solve for, b) make a new node containing a reverse of this nodes operation, c) replace the symbol you want to solve for with the reversed outer expression, recursively doing this as you progress back outwards.