Algorithm to rearrange equations/comparison predicates

Question

Say you have an equation like x1 + c1 * x2 + c2 / (y1 + c3) = y2 - x3

My goal is to rearrange it so that all x's are on one side of the equation, and all y's are on the other, f(x1, x2, ..., xi) = g(y1, y2, ..., yj) (so, for my example, x1 + c1 * x2 + x3 = y2 - c2 / (y1 + c3) is a solution)

First of all, is there a name for this transformation?

I'm looking for existing algorithms that can do this (doesn't need to cover all cases, some simple ones would be a good start) or return that it cannot. It's pretty simple if you only allow +/-, but gets more complicated when multiplication/division or other operators are allowed...

Answer 1

Where to look for these kind of problems ?

The computer science / mathematics field "symbolic computation" is a discipline (not a family of algorithms) that aims to find solutions and algorithms to solve these kind of problems.

More precisely, a category of software called "Computer algebra system (CAS)" deals with symbolic manipulation applied to algebra. To simplify, these kind of systems need a parser and their core is an engine for equation solving and equation rearranging.

(Very simplified) anatomy of a CAS

The parser will apply grammar rules in order to analyze the terms in an equation, and the grouping of terms using grammar rules

The engine implement very elaborated term rewriting systems, the kind of algorithms that applies a set of "simplification rules" or "rewriting rules", in order to reach a goal (e.g. all the x on one side, all the y on the other).

This article gives a quick introduction to this family of algorithms.

For example one rule could be

 A + expression1 = expression2 ==> expression = expression2 - (A)

But there would be hundreds of rules like this.

In addition, a term rewriting system must have a guiding logic, to choose the most promising rewritings (e.g. rearrangement). You can imagine this as a kind of path-finding algorithm that looks for an optimal path in a graph of possible rewritings, a little bit like your GPS-system is looking for an optimized path in the streets. And in this logic, you need to add some strategies, that make the TRS prefer putting groups of symbols on one side or on the other of the equal sign.

It's not a piece of cake !

Needless to say, these a very complex systems. It's more the thing for a research lab. Fortunately there are some of them available, even some open source you could start with.

Answer 2

The name for the transformation you are looking for is "Algebraic Simplification". The superset of algorithms and code you want to have a look in is called "Symbolic Computation."

• Newtopian: have a look here for some pointers math.stackexchange.com/questions/21305/…