Subject: Re: [Ufl] [Question #212068]: Reducing a fraction

From: Martin Sandve Alnæs<[email-masked]>
Date: Tue, 23 Oct 2012 11:31:01 -0000

Question #212068 on UFL changed:
https://answers.launchpad.net/ufl/+question/212068

    Status: Open => Answered

Martin Sandve Alnæs proposed the following answer:
On 23 October 2012 13:11, Jan Blechta
<[email-masked]> wrote:
> New question #212068 on UFL:
> https://answers.launchpad.net/ufl/+question/212068
>
> Hi,
> is there a way one can manipulate (by some algorithm) UFL expression or form to reduce a term like
>     something * x[0] / x[0]
> to mathematically equivalent
>     something * 1
> which has polynomial degree smaller by two. Moreover it could prevent division by zero.
>
> I'm not asking for a generel algorithm doing a division of rational functions but rather if user can apply some transformation rule locating products with factors x[0] and 1/x[0] and remove it.
>

No, there is no way to do that in ufl without writing additional
algorithms for it.

Such simplification may be feasible for this particular case but
generalized can be a very hard problem.

Martin

> I admit I could do this transformation by hand but consider situation when this expression is result of automatic calculations (e.g. automatic differentiation).
>
> Thanks
> Jan
>
> --
> You received this question notification because you are a member of UFL
> Team, which is an answer contact for UFL.
>
> _______________________________________________
> Mailing list: https://launchpad.net/~ufl
> Post to     : [email-masked]
> Unsubscribe : https://launchpad.net/~ufl
> More help   : https://help.launchpad.net/ListHelp

-- 
You received this question notification because you are a member of UFL
Team, which is an answer contact for UFL.

---

From: Martin Sandve Alnæs<[email-masked]>
Date: Tue, 23 Oct 2012 15:56:08 -0000

Martin Sandve Alnæs proposed the following answer:
Ignoring the non-scalar case, and limiting this to pure "chains" of
Product/Division, is probably fairly easy to implement as an algorithm
you can choose to apply, or that a form compiler can choose to apply.
This should also be safe from a floating point point of view. I
deliberately do not allow such deep simplifications automatic at
construction of expressions however, because they will be O(n) in the
size of the expression tree, and they may also obfuscate otherwise clear
cases of subexpression reuse.

---

From: Kristian B. Ølgaard<[email-masked]>
Date: Wed, 24 Oct 2012 05:51:11 -0000

Kristian B. Ølgaard proposed the following answer:
On 23 October 2012 17:31, Jan Blechta
<[email-masked]> wrote:
> Jan Blechta posted a new comment:
> Good job, Martin. But general cases like (g*f)/f are of my interest. So
> it would need to recognize associative compound of many products and
> divisions which could be transformed to general fraction like
> f1*f2*f3*.../(g1*g2*g3*...) with fi,gi terminals and then to check for
> possible equalities fi==gj for some i,j to reduce the fraction. So it
> would simply set terminals fi=gj=1 and kept original expression in order
> to avoid need for defining additional operator for fraction. What do you
> think about this design? It of course needs thinking over non-scalar
> case (possibly do nothing).

Something similar to this is implemented in FFC for the quadrature
representation (optimisation).
The difference is that it operates on an intermediate representation
of the code which will be generated meaning that all symbols are
scalar valued.
It is an expensive optimisation to perform, so having something
similar which operates at the higher UFL abstraction level could be
expected to improve performace.

Kristian

> I woud try doing something like that sometimes next week (if not anybody
> else:)) but I'm not much familiar with UFL operation so I can't
> promise...
>
> Jan
>
> --