[GiNaC-list] Term ordering and compiling C++ code

[jros]

Hello,

Although I don't have a solution for your problem, as I'm myself
addressing similar problems
matching common subexpressions to variables, in down top manner, I think
that such a functionality
is implicitly implemented in GiNaC.

If I understand GiNaC internal structure correctly, subexpressions
common to two expresions,
are frequently  shared internally, to save memory.

So it must be possible to write a print algorithm that goes trough
an/some expression/s tree, and that replaces
every shared subexpression (let say sum product) with a variable, that
again is assigned a expression that would be printed
 in the same way using recursion. 

Probably allowing/disallowing some kind automatic simplifications (so
that subexpression sharing expected value increases) can probably help
to obtain improved results.

I wonder what do the developers think about this.

Cheers,

Javier


On Thu, 2010-05-13 at 07:11 -0700, Doug wrote:

> Hi,
> 
> I'm running into a term ordering problem like the one mentioned in
> this post.
> http://permalink.gmane.org/gmane.comp.mathematics.ginac.general/1107
> 
> Relevant details about my application are below, for the curious.  The
> short of it, though, is that the C++ code I am generating with ginac
> is so large (50MB) that the compiler can't handle it, and moreover,
> the values being represented by ginac symbols are array accesses that
> the compiler can't optimize away.  So I need to create temporary
> values and do sub-expression elimination on the C++ code just so the
> compiler can have a chance.  I have successfully done this using
> search-and-replace on the C++ code for other applications, but I guess
> I was just lucky that ginac printed terms in a consistent order.
> 
> Is this a problem other ginac users have confronted?  From the answer
> to the above post, it sounds like I need to write my own print
> function that can ensure expressions are printed in a predictable
> order.  It looks like I can also inspect the expression tree and
> possibly do a proper job of common sub-expression elimination.  But if
> there is an easier approach, I'd be very grateful for a pointer or
> two.
> 
> Thanks,
> Doug Baker
> 
> -------------------
> Background Details
> -------------------
> 
> My application is related to visual odometry.  I am computing the
> gradient and hessian for a function of 10 variables that involves
> converting quaternions to rotation matrices, applying those matrices
> to 3D points and projecting those points onto a 2D plane.
> 
> I am generating code with ginac that is initially 50MB of C++ code.
> (And thank you for ginac being able to handle that monstrosity with
> such grace.)  The input symbols are all array elements (e.g. symbol
> x("state[t+X]")) or function calls (e.g. symbol
> rTi11("rTi.getValue<1,1>()")).
> 
> If I take the printed output from ginac as is, the C++ compiler can't
> properly optimize it because it doesn't know that state[t+X] is a
> constant or that getValue is constant.  Moreover, the expressions have
> huge repeated expressions, and these bog the compiler down, too.
> 
> I've been able to use a simple search-and-replace approach in other
> problems, and on this one that same approach has gotten me from 50MB
> to 6MB or so, but the term ordering issue is biting me now.  For
> example, I have one sum (a+b+c+d) that occurs 232608 times.  But there
> are 4! = 24 permutations of that sum that I'd have to replace.  It's
> worse than that, though, because that's not the only expression like
> it.  Some are bigger, like this: (-2.0*sK/sKSIJ+4.0*sK*sS2/pKSIJ2
> +-4.0*sI*sJ*sS/pKSIJ2). This has something like 72 permutations, not
> even counting the permutations of pKSIJ and pKSIJ2, which are
> themselves expressions like (a+b+c+d).  And not only are there
> variations on this due to term ordering, similar expressions occur
> with different variables (e.g. with sJ instead of sK, etc.)  So when
> all these expressions can be output in various orders, it's no longer
> feasible to generate all the permutations for search-and-replace.
> 
> 
> Support NPR 20 seconds at a time. www.twentysecondsatatime.org
> 
> 
> _______________________________________________
> GiNaC-list mailing list
> GiNaC-list at ginac.de
> https://www.cebix.net/mailman/listinfo/ginac-list
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.cebix.net/pipermail/ginac-list/attachments/20100513/86a0232b/attachment.htm>