Adding many `conditional` terms causes RecursionErrors

[Patrick Farrell]

Consider the following code:

from dolfin import *

E = 0

for i in range(1000):
    E += conditional(ge(i, 0), i, 0) # fails
    #E += i # if this line is uncommented, it works

Running this yields

[pefarrell@aoibheann:/tmp]$ python3 recursionerror.py 
Traceback (most recent call last):
  File "recursionerror.py", line 6, in <module>
    E += conditional(ge(i, 0), i, 0) # fails
  File "/home/pefarrell/local/dolfin/fenics-stb-2017.2.0-3.6/lib/python3.6/site-packages/fenics_ufl-2017.2.0-py3.6.egg/ufl/exproperators.py", line 212, in _add
  File "/home/pefarrell/local/dolfin/fenics-stb-2017.2.0-3.6/lib/python3.6/site-packages/fenics_ufl-2017.2.0-py3.6.egg/ufl/algebra.py", line 49, in __new__
  File "/home/pefarrell/local/dolfin/fenics-stb-2017.2.0-3.6/lib/python3.6/site-packages/fenics_ufl-2017.2.0-py3.6.egg/ufl/core/ufl_type.py", line 214, in _inherited_ufl_shape
  File "/home/pefarrell/local/dolfin/fenics-stb-2017.2.0-3.6/lib/python3.6/site-packages/fenics_ufl-2017.2.0-py3.6.egg/ufl/core/ufl_type.py", line 214, in _inherited_ufl_shape
  File "/home/pefarrell/local/dolfin/fenics-stb-2017.2.0-3.6/lib/python3.6/site-packages/fenics_ufl-2017.2.0-py3.6.egg/ufl/core/ufl_type.py", line 214, in _inherited_ufl_shape
  [Previous line repeated 492 more times]
RecursionError: maximum recursion depth exceeded
Aborted

Now I admit this is a bit pathological, but the problem is actually arising with a user who's trying to do some bifurcation analysis of crystals with defcon.

If I uncomment the extra line, it works, for some reason.

This may not be a bug in UFL: is there another way to express the sum that does not trigger a RecursionError?

[Jan Blechta]

I suppose that this is a limitation of binary Python + binary operators. You can circumvent this by using UFL sum of over index:

from ufl import *
from ufl.indexsum import IndexSum, MultiIndex

v = as_vector([conditional(ge(i, 0), i, 0) for i in range(1000)])
i = Index()
E = IndexSum(v[i], MultiIndex((i,)))

(I'm not saying that a fix for your example is not possible.)

[Lawrence Mitchell]

You making a linear summation tree, rather than a log tree. If you have control over the summation of all the terms, just do a binary fanout. Then the recursion is only O(log terms).

[Lawrence Mitchell]

Something like (untested):

def make_sum(terms):
      shape, = set(t.ufl_shape for t in terms)
      n = len(terms)
      if n == 0:
          return ufl.zero(shape)
      if n == 1:
          return terms[0]
      return make_sum(terms[:n//2]) + make_sum(terms[n//2:])

[Patrick Farrell]

Great, that works, thanks.

[Patrick Farrell]

Worked around by Lawrence's logarithmic summation tree.