infinite loop in simplify_indexed()
I've finally tracked down the source of my troubles in getting the little program I've been working on to run and I'm 99% convinced it's a bug in the library. Please take a look at this brief sample program I wrote that illustrates the problem. #include <iostream> #include <ginac/ginac.h> using namespace std; using namespace GiNaC; int main() { symbol i_sym("i"), j_sym("j"), k_sym("k"), l_sym("l"), m_sym("m"), n_sym("n"); idx i(i_sym, 2), j(j_sym, 2), k(k_sym, 2), l(l_sym, 2), m(m_sym, 2), n(n_sym, 2); symbol alpha_sym("\\alpha"), beta_sym("\\beta"), gamma_sym("\\gamma"); idx Va(alpha_sym, 3), Vb(beta_sym, 3), Vg(gamma_sym, 3); symbol U("U"), v("v"), h("h"); exvector IJKLMNVec; idx IJKLMNIA[] ={i, j, k, l, m, n}; IJKLMNVec.assign (IJKLMNIA,IJKLMNIA+6); ex myEx = (indexed(h, sy_symm(sy_none(0, 1), sy_none(2, 3),sy_none(4, 5)), IJKLMNVec)*indexed(U, i, Va)*indexed(v, j, Va)*indexed(U, k, Vb) *indexed(v, l, Vb)*indexed(U, m, Vg)*indexed(v, n, Vg)).simplify_indexed(); cout << myEx << endl; return 0; } You'll find it never terminates. simplify_indexed() has an infinite loop that was unanticipated caused by some rare forms of indexed expressions. This program will just run and run trapped in implify_indexed() and never print anything out. If a fix is not forthcoming any ideas for a work around? regards peter clark ---------------------------------------------------------------- This message was sent using IMP, the Internet Messaging Program.
Hi, it seems GiNaC tries to loop over all 9! index permutations inside symm() in symmetry.cpp ... is that a good idea?!? Currently, I have no idea what to do about it. Regards, Jens
Hello, On Sun, May 15, 2011 at 10:22:27PM +0200, Jens Vollinga wrote:
it seems GiNaC tries to loop over all 9! index permutations inside symm() in symmetry.cpp ... is that a good idea?!?
I don't think it's a good idea. Still I don't think a sum of 362880 terms is really a big deal.
Currently, I have no idea what to do about it.
The patch below (drastically) improves the run time at the expense of using more RAM in some situations. Please note: it doesn't improve the actual algorithm (iteration over all permutations). diff --git a/ginac/symmetry.cpp b/ginac/symmetry.cpp index 7d1ff97..d93e34c 100644 --- a/ginac/symmetry.cpp +++ b/ginac/symmetry.cpp @@ -22,6 +22,7 @@ #include "symmetry.h" #include "lst.h" +#include "add.h" #include "numeric.h" // for factorial() #include "operators.h" #include "archive.h" @@ -495,7 +496,8 @@ static ex symm(const ex & e, exvector::const_iterator first, exvector::const_ite // Loop over all permutations (the first permutation, which is the // identity, is unrolled) - ex sum = e; + exvector sum_v; + sum_v.push_back(e); while (std::next_permutation(iv, iv + num)) { lst new_lst; for (unsigned i=0; i<num; i++) @@ -505,8 +507,9 @@ static ex symm(const ex & e, exvector::const_iterator first, exvector::const_ite memcpy(iv2, iv, num * sizeof(unsigned)); term *= permutation_sign(iv2, iv2 + num); } - sum += term; + sum_v.push_back(term); } + ex sum = (new add(sum_v))->setflag(status_flags::dynallocated); delete[] iv; delete[] iv2; Best regards, Alexei P.S. The bug has nothing to do with infinite loops.
I can confirm that I was able to successfully compile and run my test code with this patch applied. took about 10 seconds to execute. Thanks for the help guys peter Quoting Alexei Sheplyakov <alexei.sheplyakov@gmail.com>:
The patch below (drastically) improves the run time at the expense of using more RAM in some situations. Please note: it doesn't improve the actual algorithm (iteration over all permutations).
diff --git a/ginac/symmetry.cpp b/ginac/symmetry.cpp index 7d1ff97..d93e34c 100644 --- a/ginac/symmetry.cpp +++ b/ginac/symmetry.cpp @@ -22,6 +22,7 @@
#include "symmetry.h" #include "lst.h" +#include "add.h" #include "numeric.h" // for factorial() #include "operators.h" #include "archive.h" @@ -495,7 +496,8 @@ static ex symm(const ex & e, exvector::const_iterator first, exvector::const_ite
// Loop over all permutations (the first permutation, which is the // identity, is unrolled) - ex sum = e; + exvector sum_v; + sum_v.push_back(e); while (std::next_permutation(iv, iv + num)) { lst new_lst; for (unsigned i=0; i<num; i++) @@ -505,8 +507,9 @@ static ex symm(const ex & e, exvector::const_iterator first, exvector::const_ite memcpy(iv2, iv, num * sizeof(unsigned)); term *= permutation_sign(iv2, iv2 + num); } - sum += term; + sum_v.push_back(term); } + ex sum = (new add(sum_v))->setflag(status_flags::dynallocated);
delete[] iv; delete[] iv2;
Best regards, Alexei
P.S. The bug has nothing to do with infinite loops.
---------------------------------------------------------------- This message was sent using IMP, the Internet Messaging Program.
Actually I still really encourage you to keep working on this one. Now my main program with large expressions gets killed 5 or so minuets in for eating up all the ram. I'll have a look at this symm function and see if I can devise a better algorithm than bruit force for you guys. so it takes a part of an expression and applies every single possible permutation and adds the expressions or subtracting in some cases if asymmetric is called up then divides by the number of terms. Thus enforcing that the new expression with have the desired symmetry by virtue of its form yet be equivalent to the old expression if its assumed to have that symmetry. Presumably you nest these symm calls inside each other some how and construct even more complex sums to ensure compliance with more complex symmetry. But what do you do with it next? add all the bits up and try to cancel things out treating the indexes as static labels? That would be a sure fire way to get a result. But is that all it's used for? If so there'd have been no need for it to be called for the test program where there was no symmetry to consider. Or is it also used to account for pseudo symmetry that may exist due to the equivalence of dummy indexes? So if dummy indexes in a term have the same dimension you treat them as a symmetric permutation and sum over all of them too? There has to be a better way! regards peter clark Quoting PG CLARK <P.G.Clark@Bradford.ac.uk>:
I can confirm that I was able to successfully compile and run my test code with this patch applied. took about 10 seconds to execute.
Thanks for the help guys
peter
---------------------------------------------------------------- This message was sent using IMP, the Internet Messaging Program.
Hi, Am 18.05.2011 00:33, schrieb PG CLARK:
But what do you do with it next? add all the bits up and try to cancel things out treating the indexes as static labels? That would be a sure fire way to get a result. But is that all it's used for? If so there'd have been no need for it to be called for the test program where there was no symmetry to consider. Or is it also used to account for pseudo symmetry that may exist due to the equivalence of dummy indexes? So if dummy indexes in a term have the same dimension you treat them as a symmetric permutation and sum over all of them too?
There has to be a better way!
I think I fixed the problem (and hopefully didn't mess up shortly before the next release ...). simplify_indexed() now doesn't do a complete symmetrization anymore if no non-symmetric indices are involved, since a vanishing expression cannot be expected then. Regards, Jens
participants (3)
-
Alexei Sheplyakov
-
Jens Vollinga
-
PG CLARK