computer algebra soft to minimize the number of operations in a set of polynomials

Question

I have systems of polynomials, fairly simple polynomial expressions but rather long to optimize my hand. Expressions are grouped in sets, and in a given set there are common terms in several variables.

I would like to know if there is a computer algebra system, such as Mathematica, Matlab, or sympy, which can optimize multiple polynomials with common terms to minimize number of operations. It would be also great if such system can minimize the number of intermediate terms to reduce number of registers.

If such system is not existing, I am going to do my own, using Python symbolic algebra Sympy. If you are working on such package or are interested in developing or using one, please let me know.

here is a made-up example

x0 = ((t - q*A)*x + B)*y
y0 = ((t - q*A)*y + B)*z
z0 = ((t - q*A)*z + B)*x

so you can obviously factor the (t - qA) term. Now if you make number of terms very large with various combinations of common terms it becomes difficult to do by hand. The equations I have involve up to 40 terms and the size of set is around 20. Hope that helps

Thank you

Answer 1

Is sympy what you're looking for? I do believe it has support for polynomials although I don't know if it supports all the features you may desire (still, tweaking it to add what you think it might be missing has to be easier than writing your own from scratch;-).

Answer 2

I'm late to the party, but anyway there is a function optimize in Maxima (https://maxima.sourceforge.io) which identifies common subexpressions and emits a blob of code which can be evaluated. For the example shown in the problem statement, I get:

(%i11) optimize ([x0 = ((t-A*q)*x+B)*y,
                  y0 = ((t-A*q)*y+B)*z,
                  z0 = x*((t-A*q)*z+B)]);

(%o11) block([%1], 
             %1 : t - A q, 
             [x0 = (%1 x + B) y, 
              y0 = (%1 y + B) z,
              z0 = x (%1 z + B)])

As you can see, t - A*q was pulled out and assigned to a made-up variable %1 (percent sign being an allowed character for symbols in Maxima) which is then reused to compute other results.

? optimize at the input prompt shows some documentation about it.

Answer 3

Have you considered Maxima?

It is an impressive symbolical computation package that is free, open source, and has a strong and active community that provides valuable assistance when dealing with non-obvious formulations. It is readily availability for all three major operating systems, and has a precompiled Windows binary.

You have a variety of algebraic manipulation commands available for expressions and for systems of equations (such as yours): expand, factor, simplify, ratsimp, linsolve, etc.

This page (Maxima for Symbolic Computation)should get you started — downloading, installing, a few examples, and then pointing out additional resources to guide you on your way, including a quick command reference / cheat sheet, and some guidlines for writing your own scripts.

Answer 4

Well Mathematica can certainly do all sorts of transformations on sets of polynomial equations such as yours, and some of those transformations could be to reduce the number of terms. Whether that is the right answer for you is open to question, as you don't seem to have a copy available. I expect that the same is true for Maple and for most of the other CAS out there.

But your mention of

reduce number of registers

suggests that you are actually trying to do some data-flow analysis for compilation. You might want to look at the literature on that topic too. Some of that literature does indeed refer to computer-algebra-like transformations on expressions.