Mv.dual is very slow

[meuns]

Hi,

I was trying this version of galgebra and I found Mv.dual method is very slow for low dimension geometric algebras. I hoped the issue was fixed there (This issue is reproducible with brombo version).

A short snippet :

from galgebra.ga import Ga

GA = Ga('e*1|2|3')
a = GA.mv('a', 'vector')
b = GA.mv('b', 'vector')
c = GA.mv('c', 'vector')

def cross(x, y):
    return (x ^ y).dual()

I only profile :
xx = cross(a, cross(b, c))

cProfile reports :

         16807237 function calls (15373382 primitive calls) in 5.316 seconds

   Ordered by: cumulative time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        2    0.000    0.000    5.316    2.658 /home/sylvain/Documents/pygae/tests/test_dual.py:41(cross)
63300/1661    0.047    0.000    5.200    0.003 /home/sylvain/Documents/pygae/venv/lib/python3.6/site-packages/sympy/core/cache.py:91(wrapper)
        2    0.000    0.000    5.106    2.553 /home/sylvain/Documents/pygae/venv/lib/python3.6/site-packages/galgebra/mv.py:1050(dual)
        2    0.000    0.000    5.039    2.520 /home/sylvain/Documents/pygae/venv/lib/python3.6/site-packages/galgebra/mv.py:506(__mul__)
5864/5592    0.037    0.000    4.517    0.001 /home/sylvain/Documents/pygae/venv/lib/python3.6/site-packages/sympy/core/operations.py:28(__new__)
1789/1582    0.001    0.000    3.483    0.002 /home/sylvain/Documents/pygae/venv/lib/python3.6/site-packages/sympy/core/decorators.py:84(__sympifyit_wrapper)
1602/1579    0.001    0.000    3.481    0.002 /home/sylvain/Documents/pygae/venv/lib/python3.6/site-packages/sympy/core/decorators.py:122(binary_op_wrapper)
       62    0.003    0.000    3.371    0.054 /home/sylvain/Documents/pygae/venv/lib/python3.6/site-packages/galgebra/ga.py:103(nc_subs)
       22    0.000    0.000    3.136    0.143 /home/sylvain/Documents/pygae/venv/lib/python3.6/site-packages/galgebra/ga.py:1137(base_to_blade_rep)
      927    0.001    0.000    3.058    0.003 /home/sylvain/Documents/pygae/venv/lib/python3.6/site-packages/sympy/core/expr.py:117(__add__)
     1045    0.130    0.000    3.054    0.003 /home/sylvain/Documents/pygae/venv/lib/python3.6/site-packages/sympy/core/add.py:78(flatten)
       10    0.000    0.000    2.956    0.296 /home/sylvain/Documents/pygae/venv/lib/python3.6/site-packages/galgebra/mv.py:383(blade_rep)
     5787    0.053    0.000    2.443    0.000 {method 'sort' of 'list' objects}
507395/196716    0.766    0.000    2.390    0.000 /home/sylvain/Documents/pygae/venv/lib/python3.6/site-packages/sympy/core/basic.py:170(compare)
     1046    0.000    0.000    2.091    0.002 /home/sylvain/Documents/pygae/venv/lib/python3.6/site-packages/sympy/core/add.py:19(_addsort)
       82    0.000    0.000    1.722    0.021 /home/sylvain/Documents/pygae/venv/lib/python3.6/site-packages/sympy/core/function.py:1982(expand)
       33    0.001    0.000    1.721    0.052 /home/sylvain/Documents/pygae/venv/lib/python3.6/site-packages/sympy/core/expr.py:3071(expand)
246474/297    0.329    0.000    1.720    0.006 /home/sylvain/Documents/pygae/venv/lib/python3.6/site-packages/sympy/core/expr.py:3041(_expand_hint)
        6    0.000    0.000    1.464    0.244 /home/sylvain/Documents/pygae/venv/lib/python3.6/site-packages/galgebra/mv.py:287(__init__)
        6    0.000    0.000    1.464    0.244 /home/sylvain/Documents/pygae/venv/lib/python3.6/site-packages/galgebra/mv.py:124(characterise_Mv)
     8886    0.025    0.000    1.146    0.000 /home/sylvain/Documents/pygae/venv/lib/python3.6/site-packages/sympy/core/mul.py:854(_eval_expand_mul)
4744/4487    0.126    0.000    1.083    0.000 /home/sylvain/Documents/pygae/venv/lib/python3.6/site-packages/sympy/core/mul.py:97(flatten)
   262792    0.194    0.000    1.050    0.000 /home/sylvain/Documents/pygae/venv/lib/python3.6/site-packages/sympy/core/symbol.py:250(_hashable_content)
   262792    0.363    0.000    0.633    0.000 /home/sylvain/Documents/pygae/venv/lib/python3.6/site-packages/sympy/core/symbol.py:254(assumptions0)
    77094    0.037    0.000    0.621    0.000 /home/sylvain/Documents/pygae/venv/lib/python3.6/site-packages/sympy/core/operations.py:68(_new_rawargs)
    84366    0.154    0.000    0.600    0.000 /home/sylvain/Documents/pygae/venv/lib/python3.6/site-packages/sympy/core/operations.py:54(_from_args)
        4    0.000    0.000    0.502    0.125 /home/sylvain/Documents/pygae/venv/lib/python3.6/site-packages/galgebra/ga.py:66(update_and_substitute)
604605/508233    0.121    0.000    0.444    0.000 /home/sylvain/Documents/pygae/venv/lib/python3.6/site-packages/sympy/core/assumptions.py:242(getit)
  662/646    0.001    0.000    0.421    0.001 /home/sylvain/Documents/pygae/venv/lib/python3.6/site-packages/sympy/core/expr.py:137(__mul__)
        2    0.000    0.000    0.418    0.209 /home/sylvain/Documents/pygae/venv/lib/python3.6/site-packages/galgebra/ga.py:1170(mul)
    72928    0.117    0.000    0.382    0.000 /home/sylvain/Documents/pygae/venv/lib/python3.6/site-packages/sympy/core/logic.py:112(fuzzy_and)
    71594    0.058    0.000    0.374    0.000 /home/sylvain/Documents/pygae/venv/lib/python3.6/site-packages/sympy/core/mul.py:768(as_coeff_Mul)
  211/133    0.000    0.000    0.365    0.003 /home/sylvain/Documents/pygae/venv/lib/python3.6/site-packages/sympy/core/mul.py:835(_expandsums)
        8    0.001    0.000    0.360    0.045 /home/sylvain/Documents/pygae/venv/lib/python3.6/site-packages/galgebra/metric.py:42(linear_expand)
     4737    0.002    0.000    0.354    0.000 /home/sylvain/Documents/pygae/venv/lib/python3.6/site-packages/sympy/core/mul.py:32(_mulsort)
17861/654    0.051    0.000    0.342    0.001 /home/sylvain/Documents/pygae/venv/lib/python3.6/site-packages/sympy/core/assumptions.py:254(_ask)
     5796    0.104    0.000    0.303    0.000 /home/sylvain/Documents/pygae/venv/lib/python3.6/site-packages/sympy/core/basic.py:1695(_exec_constructor_postprocessors)
       39    0.001    0.000    0.273    0.007 /home/sylvain/Documents/pygae/venv/lib/python3.6/site-packages/sympy/core/mul.py:850(<listcomp>)
   648176    0.188    0.000    0.269    0.000 /home/sylvain/Documents/pygae/venv/lib/python3.6/site-packages/sympy/core/core.py:73(__cmp__)
  2338243    0.261    0.000    0.261    0.000 {built-in method builtins.isinstance}
  1732062    0.251    0.000    0.251    0.000 /home/sylvain/Documents/pygae/venv/lib/python3.6/site-packages/sympy/core/symbol.py:256(<genexpr>)
     8886    0.038    0.000    0.250    0.000 /home/sylvain/Documents/pygae/venv/lib/python3.6/site-packages/sympy/simplify/radsimp.py:930(fraction)
1018718/360300    0.130    0.000    0.238    0.000 /home/sylvain/Documents/pygae/venv/lib/python3.6/site-packages/sympy/core/basic.py:121(__hash__)
       28    0.000    0.000    0.231    0.008 /home/sylvain/Documents/pygae/venv/lib/python3.6/site-packages/galgebra/ga.py:1145(blade_to_base_rep)
        4    0.000    0.000    0.228    0.057 /home/sylvain/Documents/pygae/venv/lib/python3.6/site-packages/galgebra/mv.py:375(base_rep)
   324088    0.081    0.000    0.224    0.000 /home/sylvain/Documents/pygae/venv/lib/python3.6/site-packages/sympy/core/core.py:101(__gt__)
     9486    0.073    0.000    0.212    0.000 /home/sylvain/Documents/pygae/venv/lib/python3.6/site-packages/sympy/core/mul.py:380(_gather)
        2    0.000    0.000    0.210    0.105 /home/sylvain/Documents/pygae/venv/lib/python3.6/site-packages/galgebra/mv.py:769(__xor__)
   262825    0.205    0.000    0.205    0.000 {built-in method builtins.sorted}
 1052/902    0.001    0.000    0.200    0.000 /home/sylvain/Documents/pygae/venv/lib/python3.6/site-packages/sympy/core/mul.py:1160(_eval_is_integer)
   324088    0.073    0.000    0.199    0.000 /home/sylvain/Documents/pygae/venv/lib/python3.6/site-packages/sympy/core/core.py:96(__lt__)
   647160    0.105    0.000    0.179    0.000 /home/sylvain/Documents/pygae/venv/lib/python3.6/site-packages/sympy/core/operations.py:64(<genexpr>)
        4    0.000    0.000    0.167    0.042 /home/sylvain/Documents/pygae/venv/lib/python3.6/site-packages/galgebra/mv.py:922(is_scalar)
        4    0.000    0.000    0.167    0.042 /home/sylvain/Documents/pygae/venv/lib/python3.6/site-packages/galgebra/ga.py:1333(grades)
    15832    0.052    0.000    0.159    0.000 /usr/lib/python3.6/random.py:263(shuffle)

Regards

[utensil]

Thanks for report this, I'll do a profiling ASAP.

[ghost]

Are you sure you wanted to calculate it for a completely general metric and not g=[1,1,1] and use GA = Ga('e*1|2|3',g=[1,1,1]).

[meuns]

If an exercise doesn't require a metric (like an euclidean one), I don't provide one. The exercise using the snippet is about proving bac cab formula. Maybe providing a metric is general enough. Even if Mv.dual is slow, I'm able to derive bac cab which is nice.

Anyways, this seems very expensive. I was able to find an expression string of 20k characters when I tried to debug the Mv.dual method.

[ghost]

The problem is the normalized I for a general metric. Look at following code and output which executes rapidly -

crosscross.py.pdf

crosscross.pdf

You don't have xtex available in your version of galgebra yet. Use what you would for LaTeX output.

[meuns]

I tried to remove the normalization of I but timings doesn't change much.

[utensil]

Sorry for the late reply, I finally get to do a profiling at https://nbviewer.jupyter.org/github/utensil/julia-playground/blob/master/py/profile_mv_dual.ipynb with reproducible steps if you're also on a Mac.

I think the reason is irrelevant to the normalized I since I also tried set norm=False explicitly and when I tried to set norm=True the error of !!!!Basis normalization only implemented for orthogonal basis!!!! reminded me further that this is not the case.

As shown in the call graph, most of the time is spent on constructing 1k of SymPy objects in base_to_blade_rep. And I need to investigate this further for the root cause.

[ghost]

When I say normalization in this case I mean how I is expressed that is
I not equal to e1^e2^e3. In the case of the general metric there is a scale factor that is a complicated square root. Evaluate the following in a general metric and see how long it takes -

Let J = e1^e2^e3 then evaluate -

J*(a^(J*(b^c))

and see how long it takes. I think any expression with a square root really slows down sympy.simplify

[ghost]

Here is my code and output. Takes about 3 sec to run -

`
from galgebra.ga import Ga
from galgebra.printer import Format, xtex

def cross(x, y):
return (x ^ y).dual()

Format()
GA = Ga('e*1|2|3')
print('g =',GA.g)
a = GA.mv('a', 'vector')
b = GA.mv('b', 'vector')
c = GA.mv('c', 'vector')
(e1,e2,e3) = GA.mv()
print('a =',a)
print('b =',b)
print('c =',c)

print('I =',GA.i)
E = e1^e2^e3
print(r'(e_1\W e_2\W e_3)^2 =',EE)
bc = E(b^c)
print(r'(e_1\W e_2\W e_3)(b\W c) =',bc.Fmt(3))
abc = a^bc
print(r'a\W ((e_1\W e_2\W e_3)(b\W c)) =',abc.Fmt(3))
Eabc = E*(abc)
print(r'(e_1\W e_2\W e_3)(a\W ((e_1\W e_2\W e_3)(b\W c))) =',Eabc.Fmt(3))

xtex(paper=(30,11))
`
Here is output
crosscross.pdf

[meuns]

Yes, it took around 3 seconds on my workstation too.

[meuns]

We can close this issue. galgebra isn't designed to make geometric proof but calculus. If I want to achieve some kind of proofs, I need to reduce the expression lenght myself by fixing things, ignoring norms if useless, using the right basis... :)