<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 TRANSITIONAL//EN">
<HTML>
<HEAD>
<META HTTP-EQUIV="Content-Type" CONTENT="text/html; CHARSET=UTF-8">
<META NAME="GENERATOR" CONTENT="GtkHTML/3.26.0">
</HEAD>
<BODY>
Hello,<BR>
<BR>
Although I don't have a solution for your problem, as I'm myself addressing similar problems<BR>
matching common subexpressions to variables, in down top manner, I think that such a functionality<BR>
is implicitly implemented in GiNaC.<BR>
<BR>
If I understand GiNaC internal structure correctly, subexpressions common to two expresions,<BR>
are frequently shared internally, to save memory.<BR>
<BR>
So it must be possible to write a print algorithm that goes trough an/some expression/s tree, and that replaces<BR>
every shared subexpression (let say sum product) with a variable, that again is assigned a expression that would be printed<BR>
in the same way using recursion. <BR>
<BR>
Probably allowing/disallowing some kind automatic simplifications (so that subexpression sharing expected value increases) can probably help to obtain improved results.<BR>
<BR>
I wonder what do the developers think about this.<BR>
<BR>
Cheers,<BR>
<BR>
Javier<BR>
<BR>
<BR>
On Thu, 2010-05-13 at 07:11 -0700, Doug wrote:<BR>
<BLOCKQUOTE TYPE=CITE>
<TABLE CELLSPACING="0" CELLPADDING="0">
<TR>
<TD VALIGN="top">
Hi,<BR>
<BR>
I'm running into a term ordering problem like the one mentioned in this post.<BR>
http://permalink.gmane.org/gmane.comp.mathematics.ginac.general/1107<BR>
<BR>
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.<BR>
<BR>
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.<BR>
<BR>
Thanks,<BR>
Doug Baker<BR>
<BR>
-------------------<BR>
Background Details<BR>
-------------------<BR>
<BR>
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.<BR>
<BR>
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>()")).<BR>
<BR>
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.<BR>
<BR>
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.<BR>
<BR>
<BR>
Support NPR 20 seconds at a time. www.twentysecondsatatime.org
</TD>
</TR>
</TABLE>
<BR>
<PRE>
_______________________________________________
GiNaC-list mailing list
<A HREF="mailto:GiNaC-list@ginac.de">GiNaC-list@ginac.de</A>
<A HREF="https://www.cebix.net/mailman/listinfo/ginac-list">https://www.cebix.net/mailman/listinfo/ginac-list</A>
</PRE>
</BLOCKQUOTE>
</BODY>
</HTML>