Hello everybody, I have been thinking about some improvements for GiNaC that I might want to see implemented and that I might even have a try at myself. No guarantees that I will do anything, but I just might if I find some time. Before doing anyting, however, I would like to know what GiNaCs authors/maintainers think of my "improvements". Which of them would they include in the library, if they were implemented? Well, here they are: (1) Sometimes I find that GiNaC expressions can become so large that I run out of memory. Having a swapping GiNaC running on a computer is terrible. Technically speaking it does not crash the computer, however practically speaking, it is as good as a crash. Typically this happens for expressions that are large sums of which most terms are multiplications. Wouldn't it be nice to have a new class "largeadd" that stores its terms in a file rather then in memory. (If terms are products these would be saved in the file too, but the factors themselves would probably be kept in memory.) For the user, the most sensible way of manipulating a largeadd would be to have a map_function acting on it, performing various tasks at once, so that the terms in the largeadd do not need to be retrieved and stored too often. (2) Introduce a new expand_option that prevents GiNaC from expanding inside powers with exponents that aren't positive integers. For example, a user might want to have (a+b)^2*(1+(x+y)^2)^(-1) expanded into a^2*(1+(x+y)^2)^(-1) + 2*a*b*(1+(x+y)^2)^(-1) + b^2*(1+(x+y)^2)^(-1) instead of having the denominator expanded too. (3) Using so-called schoonschip-notation for indexed objects. The idea is that if an object with one index is contracted with another object, the base-expresion of the one-index-object is put at the position where the index occurs that it is contracted with. Example: A.mu~nu*p~mu --> A(p,~nu) Note that this would require indexed objects to be able to take non-idx expressions as arguments. Also one would want to introduce the notion of an inner product, leading to the automatic simplification rule: p.mu*q~mu --> inp(p,q). The point is that this often greatly reduces the amount of indices thereby allowing further simplifications. Also one no longer needs to call simplify_indexed, which, at times, is a somewhat expensive function. (4) Haven't really looked at this terribly carefully yet, but I suppose the function dirac_trace can be made much more efficient. The idea of expanding gamma5 into eps(i1,i2,i3,i4)*gamma(i1)*...*gamma(i4) (which happens inside the function dirac_trace) really looks like a winner for the award for inefficient algorithms. Also, there could be made a function that takes the trace of all spin-lines at the same time, using the Chisholm identity whenever possible. I would guess that this also makes things much faster. Greetings, Chris Dams
Hi, Thanks a lot for your suggestions! On Wed, 31 Jul 2002, Chris Dams wrote:
I have been thinking about some improvements for GiNaC that I might want to see implemented and that I might even have a try at myself. No guarantees that I will do anything, but I just might if I find some time. Before doing anyting, however, I would like to know what GiNaCs authors/maintainers think of my "improvements". Which of them would they include in the library, if they were implemented?
Well, here they are:
(1) Sometimes I find that GiNaC expressions can become so large that I run out of memory. Having a swapping GiNaC running on a computer is terrible. Technically speaking it does not crash the computer, however practically speaking, it is as good as a crash. Typically this happens for expressions that are large sums of which most terms are multiplications. Wouldn't it be nice to have a new class "largeadd" that stores its terms in a file rather then in memory. (If terms are products these would be saved in the file too, but the factors themselves would probably be kept in memory.) For the user, the most sensible way of manipulating a largeadd would be to have a map_function acting on it, performing various tasks at once, so that the terms in the largeadd do not need to be retrieved and stored too often.
I really don't see any good way out of this, given that any expression may be a highly non-treeish directed acyclic graph in GiNaC. How should such a class largeadd interfere with the normal add class? We do care that it works on platforms with 64 Bit ABI thus ensuring that it still runs fine when you have pervert amounts of RAM, and I repeatedly checked that it scales well there. So, I recommend investing money in memory. I don't want to hold you back if you have any bright idea, but I really don't see many possiblities. A personal piece of Sci-Fi: I don't even believe in hard disks having any future. You probably noticed that IBM backed out of this business a while ago. IMHO, one of the reasons is that they believe in something else, too. They do hold a fair amount of patents on holographic storage (without movable parts) and maybe in five years we'll see hardware where the distinction between RAM and disk is blurred by the presence of huge amounts of fast holographic memory. I would even bet on this. Also, the difference between memory-speed and disk-speed has only been widening during the last three decades.
(2) Introduce a new expand_option that prevents GiNaC from expanding inside powers with exponents that aren't positive integers. For example, a user might want to have (a+b)^2*(1+(x+y)^2)^(-1) expanded into a^2*(1+(x+y)^2)^(-1) + 2*a*b*(1+(x+y)^2)^(-1) + b^2*(1+(x+y)^2)^(-1) instead of having the denominator expanded too.
Oh, if you want such an expand_option, just go ahead and send us a patch! The change should be fairly trivial, indeed.
(3) Using so-called schoonschip-notation for indexed objects. The idea is that if an object with one index is contracted with another object, the base-expresion of the one-index-object is put at the position where the index occurs that it is contracted with.
Example: A.mu~nu*p~mu --> A(p,~nu)
Note that this would require indexed objects to be able to take non-idx expressions as arguments. Also one would want to introduce the notion of an inner product, leading to the automatic simplification rule: p.mu*q~mu --> inp(p,q). The point is that this often greatly reduces the amount of indices thereby allowing further simplifications. Also one no longer needs to call simplify_indexed, which, at times, is a somewhat expensive function.
Doesn't this only boil down to shorter notation? I don't see why this would really reduce the amount of indeces? Aren't they just swept under the rug?
(4) Haven't really looked at this terribly carefully yet, but I suppose the function dirac_trace can be made much more efficient. The idea of expanding gamma5 into eps(i1,i2,i3,i4)*gamma(i1)*...*gamma(i4) (which happens inside the function dirac_trace) really looks like a winner for the award for inefficient algorithms. Also, there could be made a function that takes the trace of all spin-lines at the same time, using the Chisholm identity whenever possible. I would guess that this also makes things much faster.
Hmm, maybe... luck -richy. -- Richard B. Kreckel <Richard.Kreckel@Uni-Mainz.DE> <http://wwwthep.physik.uni-mainz.de/~kreckel/>
Hello, On Thu, 1 Aug 2002, Richard B. Kreckel wrote:
On Wed, 31 Jul 2002, Chris Dams wrote:
(1) Sometimes I find that GiNaC expressions can become so large that I run out of memory. Having a swapping GiNaC running on a computer is terrible. Technically speaking it does not crash the computer, however practically speaking, it is as good as a crash. Typically this happens for expressions that are large sums of which most terms are multiplications. Wouldn't it be nice to have a new class "largeadd" that stores its terms in a file rather then in memory. (If terms are products these would be saved in the file too, but the factors themselves would probably be kept in memory.) For the user, the most sensible way of manipulating a largeadd would be to have a map_function acting on it, performing various tasks at once, so that the terms in the largeadd do not need to be retrieved and stored too often.
I really don't see any good way out of this, given that any expression may be a highly non-treeish directed acyclic graph in GiNaC.
Of course, for any implementation of this it would not be very difficult to think of an example where it would not help at all, but I suppose situations where it is usefull are much more abundant. Think of having a huge polynomial in ten different symbols. The only thing that would be kept in memory are the ten different symbols and all the rest would basically be a great number of pointers to them that can be stored in a file. This is indeed highly non-treeish, since there are not many leaves (only ten). However this makes it especially suited for a largeadd. The point is that situations like this one seem to occur rather often.
How should such a class largeadd interfere with the normal add class?
I suppose it would be a child of the ordinary add having its own versions of the methods an add has, so that it can be used where an add is expected without problems.
We do care that it works on platforms with 64 Bit ABI thus ensuring that it still runs fine when you have pervert amounts of RAM, and I repeatedly checked that it scales well there.
I don't think I really understand this. Is not the only thing that with a 64 Bit ABI that pointers are twice as long? Why would that matter? Of course nobody would forbid you to replace the largeadds in your program by ordinary ones after having bought more memory (or a different computer, or whatever). Also the user would probably be able to control the amount of terms in a largeadd that are loaded into memory during operations on them.
A personal piece of Sci-Fi: I don't even believe in hard disks having any future. You probably noticed that IBM backed out of this business a while ago. IMHO, one of the reasons is that they believe in something else, too. They do hold a fair amount of patents on holographic storage (without movable parts) and maybe in five years we'll see hardware where the distinction between RAM and disk is blurred by the presence of huge amounts of fast holographic memory. I would even bet on this. Also, the difference between memory-speed and disk-speed has only been widening during the last three decades.
Well, I suppose you have a point here.
(3) Using so-called schoonschip-notation for indexed objects. The idea is that if an object with one index is contracted with another object, the base-expresion of the one-index-object is put at the position where the index occurs that it is contracted with.
Example: A.mu~nu*p~mu --> A(p,~nu)
Note that this would require indexed objects to be able to take non-idx expressions as arguments. Also one would want to introduce the notion of an inner product, leading to the automatic simplification rule: p.mu*q~mu --> inp(p,q). The point is that this often greatly reduces the amount of indices thereby allowing further simplifications. Also one no longer needs to call simplify_indexed, which, at times, is a somewhat expensive function.
Doesn't this only boil down to shorter notation? I don't see why this would really reduce the amount of indeces? Aren't they just swept under the rug?
No, this is not the case. Consider the expression a.i*b.i*c.j*d.j - e.k*f.k*g.l*h.l What would simplify_indexed() make from this? Well perhaps something like a.i*b.i*c.j*d.j - e.i*f.i*g.j*h.j or perhaps (who knows) a.i*b.i*c.j*d.j - e.j*f.j*g.i*h.i If I would be interested in the result after doing the subsitution e==a,f==b,g==c,h==d the first result of simplify_indexed would immediatly result in the answer zero, but the second one would only after a new call to simplify_indexed. The point is that an expression like a.i*b.i somewhere contains the information that a symbol "i" is used. However, this is not really information at all and one would rather drop it. Perhaps the index dimensions should be kept, but the occurence of a symbol that does not do anything usefull can only impair on performance. With schoonschip-notation (here it could perhaps be called inner-product notation, but schoonschip-notation does about the same for indexed objects of higher rank contracted with a rank-one indexed), the first expression would be converted to inp(a,b)*inp(c,d) - inp(e,f)*inp(g,h) by automatic evaluation, which would always be zero after the just-mentioned substitution. This inner products-expression would nowhere contain references to the symbol "i" (or any other symbol used for the indices). (Here automatic evaluations might even result in four symbols being deleted from memory altogether, thanks to schoonschip-notation, while in the same circumstances simplify_indexed will delete only two.) Greetings, Chris
Hi there, On Thu, 1 Aug 2002, Chris Dams wrote: [...]
I really don't see any good way out of this, given that any expression may be a highly non-treeish directed acyclic graph in GiNaC.
Of course, for any implementation of this it would not be very difficult to think of an example where it would not help at all, but I suppose situations where it is usefull are much more abundant. Think of having a huge polynomial in ten different symbols. The only thing that would be kept in memory are the ten different symbols and all the rest would basically be a great number of pointers to them that can be stored in a file. This is indeed highly non-treeish, since there are not many leaves (only ten). However this makes it especially suited for a largeadd. The point is that situations like this one seem to occur rather often.
For expanded polynomials, what you say appears to make perfect sense. It would, however, have to be tested in realistic computations.
How should such a class largeadd interfere with the normal add class?
I suppose it would be a child of the ordinary add having its own versions of the methods an add has, so that it can be used where an add is expected without problems.
Hmm, and operator+(const ex&, const ex&) and friends would have to create what? An add or a largeadd? To me, it still appears more to be a replacement for add, instead of an addition to the current scheme.
We do care that it works on platforms with 64 Bit ABI thus ensuring that it still runs fine when you have pervert amounts of RAM, and I repeatedly checked that it scales well there.
I don't think I really understand this. Is not the only thing that with a 64 Bit ABI that pointers are twice as long? Why would that matter? Of course nobody would forbid you to replace the largeadds in your program by ordinary ones after having bought more memory (or a different computer, or whatever). Also the user would probably be able to control the amount of terms in a largeadd that are loaded into memory during operations on them.
I was just referring to the 4GB limit in address space on all 32Bit machines. That is a hard limit and it is approaching quickly. Indeed, some have already crossed it... Regards -richy. -- Richard B. Kreckel <Richard.Kreckel@Uni-Mainz.DE> <http://wwwthep.physik.uni-mainz.de/~kreckel/>
Hi! On Wed, Jul 31, 2002 at 01:47:45PM +0200, Chris Dams wrote:
(3) Using so-called schoonschip-notation for indexed objects. [...] Example: A.mu~nu*p~mu --> A(p,~nu)
I'd rather call this "invariant notation". Well, it would be truly invariant if it was written like A(p,e), where 'e' is an object representing a base... The reason why GiNaC uses a purely indexed notation is that Feynman rules are given with explicit indices and when constructing expressions for graphs, the indices would need to appear anyway. Also, we often need to refer to specific components of indexed expressions. While it is true that the proposed "mixed" notation would eliminate most (all?) dummy indices (which is desirable), I'm not sure whether this would blend in seamlessly with the current notation. Some issues that come to my mind: 1) One must be careful not to lose information about the dimensionality of the dummy indices. We have cases where an expression like A.i.j*p~j could appear with j=0..3 or with j=0..D-1 (D>=4), and where this makes a difference. In the current notation, this is easily expressed with the dummy index dimensions (this is the "subspace" feature of GiNaC 1.0.10). One could argue that the four-dimensional 'A' or 'p' are really different objects from the D-dimensional ones but using the index dimensions for this frees one from having to introduce new classes representing tensors projected into subspaces. The same holds true for inner products (i.e. k.i(4)*l~i(4) different from k.i(D)*l~i(D); GiNaC 1.1 will soon be updated to allow scalar_products to make that distinction). 2) There are spaces in which A.i.j*p~j != A.i~j*p.j (e.g. when i,j are spinidx). How would this be handled in the proposed notation? (Granted, GiNaC also assumes that it can reposition dummy indices unless they are spinidx, which I'm not completely happy with. Maybe the idx class should take a new flag that indicates whether this is possible or not.) 3) What if, for example, you have A.i.j*q~i*p~j where A.i.j is a complex- valued symmetric tensor and the components of p and q are Grassmann quantities? If you write this as A(q,p) it might give the impression that by the symmetry of A, this would be equal to A(p,q), which it isn't. How would you represent the difference between A.i.j*p~j and p~j*A.i.j if the components of A and p do not commute?
Also one would want to introduce the notion of an inner product, leading to the automatic simplification rule: p.mu*q~mu --> inp(p,q).
I don't see how this could be done in the automatic evaluator (within the given complexity constraints). simplify_indexed() can do this transformation for you if you add your own class to represent inner products.
Also one no longer needs to call simplify_indexed, [...]
I do not think so. If I get an expression of the form c1*A.i.j from place A and multiply it with an expression like c2*p~j obtained from place B, I would need to call something similar to simplify_indexed to have this transformed to c1*c2*A.p.i, so there's not much improvement here.
(4) Haven't really looked at this terribly carefully yet, but I suppose the function dirac_trace can be made much more efficient.
I'd be happy to integrate any patches. :-)
The idea of expanding gamma5 into eps(i1,i2,i3,i4)*gamma(i1)*...*gamma(i4) (which happens inside the function dirac_trace)
Although that's the general formula (from hep-ph/9401354, Eq.(18)), also mentioned in the source, that's not exactly what happens in dirac_trace(), at least not in that blunt way. E.g. if you pass a string of gamma5 and 6 other gammas to dirac_trace(), it will not start taking traces of 10-gamma strings and contracting the four dummy indices, but rather loop over all permutations of the existing 6 indices, taking only sub-traces of 2-gamma strings (which evaluate trivially in trace_string()). I do not think there's a more efficient way for the case of arbitrary indices (and within dimensional regularization). Bye, Christian -- / Coding on PowerPC and proud of it \/ http://www.uni-mainz.de/~bauec002/
participants (3)
-
Chris Dams
-
Christian Bauer
-
Richard B. Kreckel