"Roger Stafford" wrote in message <ilsaus$4cg$1@ginger.mathworks.com>...
> "David Holdaway" <ddhwy@hotmail.com> wrote in message <ilqi9p$s4f$1@ginger.mathworks.com>...
> > I was wondering if there is any clever memory usage ways to store symmetric arrays. I.e. I might have some tensor f_[abcd] = f_[bacd] = .. etc i.e. with total permutational symmetry of the indicies. Storing every single element will require N! times the data that's actually included in the tensor, which with N=4 is already 24.
> > My current "solution" is to only populate the array for a <= b <= c <= d etc and put zeros for the rest and simply sort the arguments when I look up an element in this array. It is however not possible to have "sparse" arrays so these zeros, I assume, still take up some space in the memory.
> > I'm wondering if anyone has a clever solution to my problem?
> >
> > Many thanks
>           
> There is a way you can accomplish the "compression" of your Ndimensional symmetric arrays, David. For example for N = 4 with an n by n by n by n symmetric array the total number of index combinations where i4 <= i3 <= i2 <= i1 is m = n*(n+1)*(n+2)*(n+3)/24. The following formula defines a onetoone mapping from all such ordered index combinations onto the successive integers 1:m.
>
> k = i1 + ...
> (i21)*(2*ni2)/2 + ...
> (i31)*(3*n*(n+1)(3*n+2)*i3+i3^2)/6 + ...
> (i41)*(4*n*(n+1)*(n+2)(6*n^2+14*n+6)*i4+(4*n+5)*i4^2i4^3)/24;
>
> If you leave off the last line, the formula applies to the N = 3 case with ordered i3, i2, i1, and if the last two lines are omitted, it applies to the N = 2 case with just i2 and i1. Using such a formula is a little like using matlab's 'sub2ind' function except that it is more complicated.
>
> The procedure for accessing an element with indices p, q, r, s would be to first sort them, as you have described, to a set i4<=i3<=i2<=i1 and then compute k as above, and then access the kth element of a onedimensional vector. One and only one value of k will be associated with each possible set of ordered indices. As you have pointed out, there is a saving with N = 4 of almost a factor of 24 to 1.
>
> Admittedly as N gets larger the amount of computation increases for this transformation, but that seems to be the price one must pay for such a compression.
>
> I have only worked this out up to N = 4. I perceive a pattern to this formula but it does not appear easy as yet to fully generalize it for an arbitrary N. One thing is clear  the expression is going to increase in complexity approximately as the square of N as N increases.
>
> Roger Stafford
        
David, by a simple rearrangement of the mapping I described yesterday, the transformation takes on a much simpler form. The formula below is for N = 8. It is now obvious how this can be generalized to any N. Notice that the value n, the size of each of the N dimensions, does not appear in the formula. It remains a bijective (onetoone) mapping.
k = i1 + ...
(i21)*i2/2 + ...
(i31)*i3*(i3+1)/6 + ...
(i41)*i4*(i4+1)*(i4+2)/24 + ...
(i51)*i5*(i5+1)*(i5+2)*(i5+3)/120 + ...
(i61)*i6*(i6+1)*(i6+2)*(i6+3)*(i6+4)/720 + ...
(i71)*i7*(i7+1)*(i7+2)*(i7+3)*(i7+4)*(i7+5)/5040 + ...
(i81)*i8*(i8+1)*(i8+2)*(i8+3)*(i8+4)*(i8+5)*(i8+6)/40320;
It is understood here that i1<=i2<=i3<=i4<=i5<=i6<=i7<=i8.
Bruno, in this simpler form it is now clear that the problem of performing the inverse of this mapping is dependent on finding the inverse of polynomial functions of the form (x1)*x*(x+1)*(x+2)*(x+3)*... For x >= 1 the inverse is unique. I wonder if anyone has ever worked out a good algorithm for this that would be practical in this problem. I suppose one could use 'roots' and always select the real root greater than or equal to 1.
Roger Stafford
