UFL

Avoid simplifying 0*v*dx -> 0*dx by annotating Zero with Argument

Registered by Martin Sandve Alnæs

We need to be able to represent forms that are zero valued but with arity,
e.g. with arguments such as a(u,v) = 0. Since arguments are stored implicitly
as Argument objects within the integrand expression, we cannot simplify
the last 0*v*dx -> 0*dx. However, we cannot skip simplifying 0*v->0 everywhere,
as that will have major performance and memory penalties and large parts
of UFL depends on this behaviour. Additionally, each simplification step needs
to be local, i.e. without analysing potentially deep subexpressions, to preserve
overall algorithm orders everywhere.

We want to preserve argument (v) dependency by annotating Zero with Arguments:
  0*v -> 0[v]
but still simplify e.g. coefficients (f):
  0*f -> 0
and handle properly combinations such as:
  0*v + f*v -> f*v
  0*v + 0*(f*v) -> 0[v]
  0*v + 0*(f*v) -> 0[v]
as we cannot skip these simplifications without significant performance and memory issues.

Luckily, nonlinear operators cannot have v-dependent arguments,
so we don't need to worry about e.g. sin(0*v).

We want to remove 0*v in a sum when the other term also depends on v, but this is not an O(1) operation:
  0[v] + f*v -> f*v
however we get into the original trouble if we simplify a mixed-arity form of zeros:
  0*u*v + 0*v -> 0*v # no longer mixed arity, same issue as we started with
so we only want to remove an argument-annotated zero in a sum with another term that includes the same arity. The alternative would be to disallow mixed-arity forms, but this is now in widespread use (e.g. using lhs, rhs, system).

We also need to cover situations where v dependency is deep in a subexpression multiplied with 0:
  0*((f+g)*v) -> 0[v]
which means we need an O(1) operation to get the arguments that an arbitrary expression depends on.

The only way to implement an O(1) operation to get the arguments that an arbitrary expression depends on, is to annotate _all_ expressions with their argument dependencies. Because mixed arity expressions are allowed, a tuple of argument tuples seems the most efficient way. Non-Argument Terminals and nonlinear Operators can skip this additional storage cost. Reuse of argument tuples will be crucial to keep the memory cost down, so the amortized memory cost here should be limited to a reference per subexpression object.

This might have been easier if we delayed simplifications to some analysis stage, but that would require a fairly deep redesign and carry other ramifications.

Blueprint information

Status:
Complete
Approver:
None
Priority:
Medium
Drafter:
None
Direction:
Needs approval
Assignee:
None
Definition:
Obsolete
Series goal:
None
Implementation:
Unknown
Milestone target:
None
Completed by
Martin Sandve Alnæs

Related branches

Sprints

Whiteboard

(?)

Work Items

This blueprint contains Public information 
Everyone can see this information.

Subscribers

No subscribers.