Proto for Boost mailing list page: Re: [proto] Precomputing common matrix products in an expression

Subject: Re: [proto] Precomputing common matrix products in an expression
From: Eric Niebler (eric_at_[hidden])
Date: 2012-07-13 17:55:52

On 7/13/2012 12:51 PM, Bart Janssens wrote:
> Hi guys,
> 
> I've been thinking about a feature for our DSEL, where lots of matrix
> products can occur in an expression. Part of an expression might be:
> nu_eff * transpose(nabla(u)) * nabla(u) + transpose(N(u) +
> coeffs.tau_su*u_adv*nabla(u)) * u_adv*nabla(u)
> 
> Here, u_adv*nabla(u) is a vector-matrix product that occurs twice, so
> it would be beneficial to calculate it only once. I was wondering if
> it would be doable to construct a fusion map, with as keys the type of
> each product occurring in an expression, and evaluate each member of
> the map before evaluating the actual expression. When the expression
> is evaluated, matrix products would then be looked up in the map.
> 
> Does this sound like something that's doable? I'm assuming the fold
> transform can help me in the construction of the fusion map. Note also
> that each matrix has a compile-time size, so any stored temporary
> would need to have its type computed.

This is an instance of the larger "common subexpression elimination"
problem. The problem is complicated by the fact that it can't be solved
with type information alone. u_adv*nable(u) might have the same type as
u_adv*nable(v) but different values. A hybrid solution is needed where
you cache a set of results indexed both by type information and the
identities (addresses) of the constituents of the subexpressions. This
is hard, and nobody has attempted it yet. I can give you encouragement,
but not guidance. If you find a general and elegant solution, it would
certainly be worth putting in Proto, since lots of folks would benefit.

-- 
Eric Niebler
BoostPro Computing
http://www.boostpro.com