Final words and conclusions¶

Polynomial arithmetics¶

We already said quite a lot about arithmetics of polynomials, also about possible improvements in this area. Improvements that are commonly known the many people, not necessarily interested very much in computer algebra. However, there are other, less familiar algorithms for doing polynomial arithmetics, especially of large sparse multivariate polynomials, which are not limited to integer or rational domains. A nice example are algorithms for polynomial multiplication and division based on heaps [Monagan2007heaps]. Experimental data reveals that this is currently the best approach to compute with sparse polynomials in many variables (which is actually the most important case when computing with polynomials). The algorithm can also be relatively easily parallelized, see [Monagan2009parallel] for detailed discussion.

Power series expansion¶

SymPy implements a very modern algorithm of Gruntz for computing limits symbolically [Gruntz1996limits], thus, as a side effect, SymPy is quite comprehensible in computing truncated power series of elementary and special functions (Taylor and Laurent series). When the algorithms for those two tasks were implemented, polynomials manipulation module was almost non–existent, so everything was implemented using slow symbolic core. This makes any computations concerning limits and power series very slow, because the underlying algorithms are implemented in an inefficient way. Many benchmarks show that SymPy can be enormously slow when computing series expansions of composite functions or when many terms are requested.

It would be beneficial to improve this picture by employing efficient polynomials manipulation algorithms whenever possible, when computing limits and power series. Additional algorithms would have to be added to the module, to allow efficient compositions and reversions of power series [Zippel1976expansions], [Brent1975series], [Brent1978fps]. This would be very advantageous for SymPy, because limits and truncated power series are ubiquitous in other algorithms of symbolic mathematics and are also very useful as standalone tools in many practical problems.

Partial fraction decomposition¶

Decomposition algorithms of rational functions into partial fractions are also very useful tools in symbolic mathematics. In SymPy we currently implement an algorithm of Manuel Bronstein [Bronstein1993partial], which allows to compute full partial fraction decompositions purely formally, without introducing algebraic numbers. This is a spectacular approach, but also a quite inefficient one. It would be beneficial to incorporate modular techniques into partial fraction decomposition algorithms, for example using methods of [Wang1981partial]. This would allow computations of partial fractions efficiently whenever possible and Bronstein’s algorithm would be used as a fallback.

Simplification of expressions¶

Polynomial manipulation algorithms have a natural area of application, which is simplification of expressions [Moses1971simplification]. Currently we already employ algorithms related to polynomials for this task, but we do not utilize their full potential in this case. Expression simplification is ubiquitous in symbolic mathematics systems, thus it must be general on hand but also very efficient on the other. One very interesting case is simplification of rational functions with polynomial side relations (modulo polynomial ideals), which was already studied in detail in literature [Pearce2001relations], [Monagan2006modulo]. This kind of simplification would allow the user to compute efficiently with expressions like trigonometric polynomials, which are an important tool in geometry and robotics.

Cylindrical algebraic decomposition¶

Currently one of big weaknesses of polynomials manipulation module is lack of solvers for multivariate polynomial inequalities and systems of polynomial inequalities. SymPy can solve many kinds of problems related to polynomial equations and systems of polynomial equations, thanks to the Gröbner bases method. It can also handle univariate inequalities via root isolation. However, multivariate inequalities, especially over reals, are currently a no–go for SymPy. The real case is very important, because it is related to the problem of quantifier elimination and theorem proving in algebraic geometry.

A tool that is needed to allow SymPy for handling multivariate inequalities is cylindrical algebraic decomposition [Arnon1984basic], [Jirstrand1995cylindrical], or CAD for short. Given a multivariate polynomial inequality or system of inequalities, CAD decomposes those inequalities to form a system of inequalities that are easier to reason about. This has many applications in, already mentioned, quantifier elimination and algebraic geometry, but also when evaluating multiple integrals and in assumptions engine.

Multiple algebraic extensions¶

In section Algebraic number fields we said that SymPy currently requires to compute a primitive element of a field extension if multiple extensions are provided, when computing with algebraic numbers. We also gave references to articles concerning polynomial factoring algorithms, which can work directly with multiple extensions. There are, however, algorithms for other areas of symbolic mathematics, for example for computing GCDs of polynomials [vanHoeij2002modgcd], that also do not require primitive element computations. Although, it is uncertain if those algorithms are truly advantageous, it might be still worthwhile to experiment with them.

Using modular techniques elsewhere¶

Work on polynomials manipulation module revealed that, so called, modular or p–adic techniques [Yun1976padic], give very encouraging results when concerned about speed of computations. Many classes of algorithms already benefit from this in SymPy, most notable are factorization and resultant algorithms, and other, like polynomial GCD algorithms, will be in future implemented.

Following this success, we should incorporate modular techniques outside polynomials manipulation module. We already pointed out a method for computing partial fraction decomposition, but there are other areas where those methods are applicable. A good examples are algorithms for symbolic summation and integration [Gerhard2006modular]. Modular method limit the range of application of algorithms to integers and rationals, but those are the most commonly used domains in SymPy, so the hassle is definitely worthwhile.