Well, that's not surprising. 99% of the time, when sympy hangs (but still
finishes) it is hanging in expand(). This is a place where a slight machine
difference can make a difference, too, because of the way expand works.
Basically, it places all the expansion hints in a dictionary, and then executes
them in whatever order it pops them out in a for loop (see sympy/core/expr.py,
line 895). So if you have a slightly different order for expansion, it can
easily make a difference. For example, consider
(x + 1)*(x + 2)**10.
If you first expand (x + 2)**10 using the expand_multinomial hint you get x + 1
times 11 terms. You then expand the (x + 1) around it using the expand_mul
hint.
But if you instead first expand using the expand_mul hint, you will get x*(x +
2)**10 + (x + 2)**10, and then when you apply the expand_multinomial hint, you
have to expand the (x + 2)**10 part TWICE. (You will actually then have to run
the expand_mul hint again to get the completely expanded expression). You can
see how this can result in different execution times depending on the hint
order.
The solution here, by the way, is to rewrite the expand() system using poly,
which can expand (x + 1)*(x + 2)**10 all at once (i.e., in the most efficient
way possible). It is actually possible to do that now, using the poly()
function. So poly((x + 1)*(x + 2)**10).as_basic() would be the most efficient
way to expand this:
In [1]: poly((x + 1)*(x + 2)**10).as_basic()
Out[1]:
2 3 4 5 6 7
8 9 10 11
1024 + 6144⋅x + 16640⋅x + 26880⋅x + 28800⋅x + 21504⋅x + 11424⋅x + 4320⋅x
+ 1140⋅x + 200⋅x + 21⋅x + x
In [2]: %timeit poly((x + 1)*(x + 2)**10).as_basic()
1000 loops, best of 3: 906 us per loop
In [3]: ((x + 1)*(x + 2)**10).expand()
Out[3]:
2 3 4 5 6 7
8 9 10 11
1024 + 6144⋅x + 16640⋅x + 26880⋅x + 28800⋅x + 21504⋅x + 11424⋅x + 4320⋅x
+ 1140⋅x + 200⋅x + 21⋅x + x
In [4]: %timeit ((x + 1)*(x + 2)**10).expand()
100 loops, best of 3: 7.93 ms per loop
In [5]: expand_multinomial((x + 1)*(x + 2)**10)
Out[5]:
⎛ 2 3 4 5 6
7 8 9 10⎞
(1 + x)⋅⎝1024 + 5120⋅x + 11520⋅x + 15360⋅x + 13440⋅x + 8064⋅x + 3360⋅x +
960⋅x + 180⋅x + 20⋅x + x ⎠
In [6]: expand_mul((x + 1)*(x + 2)**10)
Out[6]:
10 10
(2 + x) + x⋅(2 + x)
In [7]: expand_multinomial(expand_mul((x + 1)*(x + 2)**10))
Out[7]:
⎛ 2 3 4 5
6 7 8 9 10⎞ 2 3 4
5 6 7 8 9
1024 + 5120⋅x + x⋅⎝1024 + 5120⋅x + 11520⋅x + 15360⋅x + 13440⋅x + 8064⋅x +
3360⋅x + 960⋅x + 180⋅x + 20⋅x + x ⎠ + 11520⋅x + 15360⋅x + 13440⋅x +
8064⋅x + 3360⋅x + 960⋅x + 180⋅x + 20⋅x +
10
x
In [8]: expand_mul(expand_multinomial(expand_mul((x + 1)*(x + 2)**10)))
Out[8]:
2 3 4 5 6 7
8 9 10 11
1024 + 6144⋅x + 16640⋅x + 26880⋅x + 28800⋅x + 21504⋅x + 11424⋅x + 4320⋅x
+ 1140⋅x + 200⋅x + 21⋅x + x
In [9]: %timeit expand_mul(expand_multinomial(expand_mul((x + 1)*(x + 2)**10)))
1000 loops, best of 3: 1.69 ms per loop
In [10]: expand_multinomial((x + 1)*(x + 2)**10)
Out[10]:
⎛ 2 3 4 5 6
7 8 9 10⎞
(1 + x)⋅⎝1024 + 5120⋅x + 11520⋅x + 15360⋅x + 13440⋅x + 8064⋅x + 3360⋅x +
960⋅x + 180⋅x + 20⋅x + x ⎠
In [11]: expand_mul(expand_multinomial((x + 1)*(x + 2)**10))
Out[11]:
2 3 4 5 6 7
8 9 10 11
1024 + 6144⋅x + 16640⋅x + 26880⋅x + 28800⋅x + 21504⋅x + 11424⋅x + 4320⋅x
+ 1140⋅x + 200⋅x + 21⋅x + x
In [12]: %timeit expand_mul(expand_multinomial((x + 1)*(x + 2)**10))
1000 loops, best of 3: 1.04 ms per loop
You can see from [4] that there is also a bottle neck from running the
unnecessary hints (though I don't know how that scales).
Aaron Meurer
On Oct 21, 2010, at 7:27 AM, Ryan Krauss wrote:
> So, I was surprised by the results of interrupting the code after
> different execution times. I assumed it was hanging in the matrix
> inverse. It actually completes the inverse in a minute or so and then
> spends the rest of the time trying to use the results of the inverse
> to compute several vectors. The full traceback is below, but it hangs
> on this line:
>
> /home/ryan/git/sympy/sympy/core/power.pyc in _eval_expand_basic(self)
> 258 (a+b+..) ** n -> a**n + n*a**(n-1)*b + .., n is positive
> integer
> 259 """
> --> 260 b = self.base._eval_expand_basic()
> 261 e = self.exp._eval_expand_basic()
> 262
>
>
> The toplevel calculation that is causing the problem is here:
> /home/ryan/git/research/sympy_TMM.pyc in find_base_vector(Uin)
> 310 submati = find_submat_inv(Uin)
> 311 Uc4 = Uin[2:4,4]
> --> 312 MbVb = -1.0*(submati*Uc4)
> 313 z_b = zeros((5,1))
> 314 z_b[2] = MbVb[0]
>
> submati is a 2x2 matrix of fairly complicated terms. Uc4 is a 2x1
> column vector.
>
> Ryan
>
> Full traceback:
>
> In [5]: run symbolic_poles_and_zeros.py
> ^C---------------------------------------------------------------------------
> KeyboardInterrupt Traceback (most recent call last)
>
> /home/ryan/siue/Research/papers/SFLR_2010_paper/python/symbolic_poles_and_zeros.py
> in <module>()
> 6
> 7 mymodel = JVC_model.model_w_bm()
> ----> 8 mymodel.find_symbolic_bodes(save=0)
> 9
> 10
>
> /home/ryan/siue/Research/papers/SFLR_2010_paper/python/JVC_model.pyc
> in find_symbolic_bodes(self, save)
> 740 U6 = beam2.Get_Aug_Mat(s)
> 741 Usys = U6*(U5*(U4*(U3*(U2*(U1*U0)))))
> --> 742 z_b = sympy_TMM.find_base_vector(Usys)
> 743 z_enc = U2*(U1*(U0*z_b))
> 744 enc_gain = 180.0/pi*1024.0/360.0
>
> /home/ryan/git/research/sympy_TMM.pyc in find_base_vector(Uin)
> 310 submati = find_submat_inv(Uin)
> 311 Uc4 = Uin[2:4,4]
> --> 312 MbVb = -1.0*(submati*Uc4)
> 313 z_b = zeros((5,1))
> 314 z_b[2] = MbVb[0]
>
> /home/ryan/git/sympy/sympy/matrices/matrices.pyc in __mul__(self, a)
> 399 def __mul__(self,a):
> 400 if hasattr(a, "__array__"):
> --> 401 return matrix_multiply(self,a)
> 402 out = Matrix(self.lines,self.cols,map(lambda i: i*a,self.mat))
> 403 return out
>
> /home/ryan/git/sympy/sympy/matrices/matrices.pyc in matrix_multiply(A, B)
> 1483 blst = B.T.tolist()
> 1484 alst = A.tolist()
> -> 1485 return Matrix(A.shape[0], B.shape[1], lambda i,j:
> 1486 reduce(lambda k,l: k+l,
> 1487 map(lambda n,m: n*m,
>
> /home/ryan/git/sympy/sympy/matrices/matrices.pyc in __init__(self, *args)
> 87 for i in range(self.lines):
> 88 for j in range(self.cols):
> ---> 89 self.mat.append(sympify(operation(i, j)))
> 90 elif len(args)==3 and isinstance(args[0],int) and \
> 91 isinstance(args[1],int) and
> isinstance(args[2], (list, tuple)):
>
> /home/ryan/git/sympy/sympy/matrices/matrices.pyc in <lambda>(i, j)
> 1487 map(lambda n,m: n*m,
> 1488 alst[i],
> -> 1489 blst[j])).expand())
> 1490 # .expand() is a test
>
> 1491
>
> /home/ryan/git/sympy/sympy/core/basic.pyc in expand(self, **hints)
> 1477 if not 'basic' in hints:
> 1478 if not expr.is_Atom:
> -> 1479 result = expr._eval_expand_basic()
> 1480
> 1481 if result is not None:
>
> /home/ryan/git/sympy/sympy/core/basic.pyc in _eval_expand_basic(self)
> 1403 terms.append(term)
> 1404 else:
> -> 1405 T = term._eval_expand_basic()
> 1406
> 1407 if T is None:
>
> /home/ryan/git/sympy/sympy/core/mul.pyc in _eval_expand_basic(self)
> 396 else:
> 397 if sums:
> --> 398 terms = Mul._expandsums(sums)
> 399
> 400 if isinstance(terms, Basic):
>
> /home/ryan/git/sympy/sympy/core/mul.pyc in _expandsums(sums)
> 363 for a in left:
> 364 for b in right:
> --> 365 terms.append(Mul(a,b).expand())
> 366 added = Add(*terms)
> 367 if added.is_Add:
>
> /home/ryan/git/sympy/sympy/core/basic.pyc in expand(self, **hints)
> 1477 if not 'basic' in hints:
> 1478 if not expr.is_Atom:
> -> 1479 result = expr._eval_expand_basic()
> 1480
> 1481 if result is not None:
>
> /home/ryan/git/sympy/sympy/core/mul.pyc in _eval_expand_basic(self)
> 375
> 376 for factor in self.args:
> --> 377 terms = factor._eval_expand_basic()
> 378
> 379 if terms is not None:
>
> /home/ryan/git/sympy/sympy/core/power.pyc in _eval_expand_basic(self)
> 258 (a+b+..) ** n -> a**n + n*a**(n-1)*b + .., n is positive
> integer
> 259 """
> --> 260 b = self.base._eval_expand_basic()
> 261 e = self.exp._eval_expand_basic()
> 262
>
> /home/ryan/git/sympy/sympy/core/basic.pyc in _eval_expand_basic(self)
> 1403 terms.append(term)
> 1404 else:
> -> 1405 T = term._eval_expand_basic()
> 1406
> 1407 if T is None:
>
> /home/ryan/git/sympy/sympy/core/mul.pyc in _eval_expand_basic(self)
> 375
> 376 for factor in self.args:
> --> 377 terms = factor._eval_expand_basic()
> 378
> 379 if terms is not None:
>
> /home/ryan/git/sympy/sympy/core/power.pyc in _eval_expand_basic(self)
> 258 (a+b+..) ** n -> a**n + n*a**(n-1)*b + .., n is positive
> integer
> 259 """
> --> 260 b = self.base._eval_expand_basic()
> 261 e = self.exp._eval_expand_basic()
> 262
>
> /home/ryan/git/sympy/sympy/core/basic.pyc in _eval_expand_basic(self)
> 1403 terms.append(term)
> 1404 else:
> -> 1405 T = term._eval_expand_basic()
> 1406
> 1407 if T is None:
>
> /home/ryan/git/sympy/sympy/core/mul.pyc in _eval_expand_basic(self)
> 390
> 391 if terms is not None:
> --> 392 rewrite = True
> 393
> 394 if not rewrite:
>
> KeyboardInterrupt:
> WARNING: Failure executing file: <symbolic_poles_and_zeros.py>
>
>
>
> On Thu, Oct 21, 2010 at 7:16 AM, Øyvind Jensen <[email protected]>
> wrote:
>> to., 21.10.2010 kl. 06.43 -0500, skrev Ryan Krauss:
>>> Thanks for the suggestion. I will see if I can find a place to clear
>>> the cache. Ironically, the slower machine has more RAM than the fast
>>> one.
>>
>> Oh, well then maybe the problem is something else. clear_cache is only
>> useful if you are running out of RAM.
>>
>>>
>>> I didn't know what generic-pae meant until I just googled it. I guess
>>> it is a way to allow 32-bit machines to have more than 3 GB of RAM.
>>> The laptop has 4 GB. Does the fact that the kernel is using a generic
>>> processor cause problems?
>>>
>>
>> Sorry, I don't know much about hardware.
>>
>> Sometimes Sympy can behave slightly different on two computers because
>> certain functionalities in Python are platform dependent, like the hash.
>> However, differences should only occur for unimportant things, such as
>> the order of terms in an expression.
>>
>> If there is a specific statement where a hang occurs, it may indicate an
>> issue that is triggered only on certain platforms. Could you see if you
>> get the same traceback every time you kill the hanging script? (or
>> almost the same) In that case, could you post it here?
>>
>> Øyvind
>>
>>> Thanks,
>>>
>>> Ryan
>>>
>>> On Thu, Oct 21, 2010 at 6:37 AM, Øyvind Jensen <[email protected]>
>>> wrote:
>>>>> Any idea what could make this machine so unhappy to run sympy?
>>>>
>>>> In my (limited) experience, memory is the bottle-neck when you see the
>>>> kind of slow down you describe. You may try to clear the cache at some
>>>> point in your calculation.
>>>>
>>>>>>> from sympy.core.cache import clear_cache
>>>>>>> clear_cache()
>>>>
>>>> Øyvind
>>>>
>>>>>
>>>>> Thanks,
>>>>>
>>>>> Ryan
>>>>>
>>>>
>>>> --
>>>> You received this message because you are subscribed to the Google Groups
>>>> "sympy" group.
>>>> To post to this group, send email to [email protected].
>>>> To unsubscribe from this group, send email to
>>>> [email protected].
>>>> For more options, visit this group at
>>>> http://groups.google.com/group/sympy?hl=en.
>>>>
>>>>
>>>
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "sympy" group.
>> To post to this group, send email to [email protected].
>> To unsubscribe from this group, send email to
>> [email protected].
>> For more options, visit this group at
>> http://groups.google.com/group/sympy?hl=en.
>>
>>
>
> --
> You received this message because you are subscribed to the Google Groups
> "sympy" group.
> To post to this group, send email to [email protected].
> To unsubscribe from this group, send email to
> [email protected].
> For more options, visit this group at
> http://groups.google.com/group/sympy?hl=en.
>
--
You received this message because you are subscribed to the Google Groups
"sympy" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sympy?hl=en.
