Posts Tagged ‘Computer Algebra Systems’

Playing with SymPy

July 5, 2008

I have been playing with SymPy lately. SymPy is, basically, a Python library for Symbolic Mathematics. It’s precisely the kind of CAS I was looking for: simple, lightweight, easy to use, syntactically tasteful, open-source, and free. SymPy just makes sense. Simplicity über alles.

SymPy was started in 2005, by Ondřej Čertík, a Physics student from Czech Republic. Kudos to Ondřej for his initiative! And thanks to all of those who contributed to the SymPy project! Here are some slides on SymPy, by Ondřej:

You can download SymPy from here. If you don’t have Python installed in your computer, you can play with the SymPy online shell (which runs on the Google App Engine).

__________

An example

Let’s consider the system of polynomial equations in \mathbb{R}[x_1, x_2, x_3]

\begin{array}{rl}x_1 + x_2 + x_3 = y_1 + y_2 + y_3 \\x_1^2 + x_2^2 + x_3^2 = y_1^2 + y_2^2 + y_3^2\\x_1^3 + x_2^3 + x_3^3 = y_1^3 + y_2^3 + y_3^3\end{array},

where y = (y_1, y_2, y_3) \in \mathbb{R}^3 is a known vector (whose entries are distinct). We will denote x = (x_1, x_2, x_3). Let function g_k: \mathbb{R}^3 \rightarrow \mathbb{R} be defined as

g_k(z) = \displaystyle\sum_{i=1}^3 z_i^k.

The system of polynomial equations can thus be rewritten as

\begin{array}{rl}p_1(x) = 0\\p_2(x) = 0\\p_3(x) = 0\end{array}

where p_k(x) = g_k(x) - g_k(y) for all k \in \{1,2,3\}. According to my conjecture, this system of equations should have exactly 3! = 6 solutions. Solving the system is not very easy because the equations p_k(x) = 0 are nonlinear in variables x_1, x_2, x_3. A CAS would be useful.

For example, we could implement function g_k: \mathbb{R}^3 \rightarrow \mathbb{R} with the following Python script:

def g(z,k):
    """Computes g_k(z), where z is a list of reals and k is a positive integer"""

    # checks function arguments for errors
    if len(z)==0:
        return "ERROR: First argument must be a non-empty list of symbols!"
    if (type(k) != int) or (k < 1):
        return "ERROR: Second argument must be a positive integer!"

# computes g_k(z) and returns it
acc = 0
for i in range(0,len(z)):
acc += (z[i])**k
return acc

We could then compute the Gröbner basis of the set of polynomials \{p_1(x), p_2(x), p_3(x)\}, and the solutions of the system of polynomial equations for a given y, say, y = (1,2,3):

from sympy import *

# number of equations and symbolic variables
n = 3

# defines set S = {1, 2,..., n}
S = range(1,n+1)

# declares symbolic variables
x = [Symbol('x%d' % i) for i in S]

# initializes y vector
#y = [Symbol('y%d' % i) for i in S]
y = S

# defines system of polynomial equations in variables [x1, x2, x3]
P = [g(x,k) - g(y,k) for k in S]

# computes Groebner basis and solutions of the system of polynomials
GB = groebner(P, order='lex')
Sols = solve_system(P)

# prints results
print "Groebner basis: %s" % GB
print "Solutions: %s" % Sols
print "There are %d solutions." % len(Sols)

The output is:

\begin{array}{l} b_1(x) = -6 + x_1 + x_2 + x_3\\ b_2(x) = 11 - 6 x_2 - 6 x_3 + x_2 x_3 + x_2^2 + x_3^2\\ b_3(x) = -6 + 11 x_3 - 6 x_3^2 + x_3^3\end{array}.

  • Solutions: there are 3! = 6 solutions

\{(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)\}.

As expected, the solutions of the system of polynomial equations are the 3! = 6 permutations of the elements of y = (1,2,3). Of course, this does not prove the conjecture. All it proves is that my conjecture works for the particular case where n=3 and y = (1,2,3).

__________

Related:

Tags:, , , ,
Posted in Python | 4 Comments »

Follow

Get every new post delivered to your Inbox.

Join 84 other followers