Where to start with a CAS?

Question

This maybe flagged as too broad or not too independent or maybe somebody else already answered it,but can you point me to a direction where I can start learning about how to solve symbolic equations with a programming language,and I know there are many existing packages(for example sympy for python) but I would like to develop my own version ,where can I start with that?I want to be able to solve equations(polynomial and else) , simplify them maybe do differentiation and some statistics.

Answer 1

" I would like to develop my own version "

IMHO, there are ingredients that are necessary, and not necessarily... sufficient:

• you must have made your apprenticeship on a good CAS, like Mathematica, and have seen also some others,

• you must have a very good level as computer scientist, because the necessary data structures are complex, some of them very specific to CAS. The same for some very specific algorithms (see for example "Fundamental Problems of Algorithmic Algebra" by Chee Keng Yap, Oxford Univ. press, 2000).

• you have to master special maths, in particular, in algebra, the so-called Groebner bases, that you meet very early, for example in the fundamental factorization operation.

  Nevertheless, here are some subparts of a CAS that you can begin with:

• a multiprecision package for computing with integer and rationals of any size.

• a differentiation package. At its roots, it's something that is rather independent from the rest.

Answer 2

First thing is to choose an appropriate representation for the symbolic expressions, such as a syntax tree.

You will also have to deal with expression input and output, possibly using some textual syntax (programming-like, LaTeX ?), though you can already start playing with syntax trees built from scratch.

Then develop simple operations such as deparenthesing/full parenthesing, grouping of like terms and simplification, development of products and integer powers, and maybe some simple cases of factoring (?). A useful function is expression normalization, i.e. defining a preferred order of the terms, so that equivalent expressions are turned to the same form.

Differentiation is quite accessible, as every node in the syntax tree is transformed by a corresponding differentiation rule.

Many other operations, including roots of algebraic equations, factorization and decomposition in simple fractions may require some numerical algorithms, which can be difficult.

Integration, except if done by pattern recognition with a library, is probably out of reach.

---

You can also limit yourself to the handling of polynomials (of one or more variables). In this case the representation simplifies to a sum of terms with numerical (integer or rational) coefficients and powers, and normalization is straightforward.

Implementation of the basic operations, including derivation and integration, is quite straightforward.

A big piece is factorization (i.e. root solving). For the low degrees, there are analytical formulas, though they can't be expressed in a polynomial form, and for higher degrees numerical computation is required, so there is a kind of a dead-end there. (A workaround is to give the roots a symbolic name, but this is only possible with constant coefficients.)