Path: news.mathworks.com!not-for-mail
From: "John D'Errico" <woodchips@rochester.rr.com>
Newsgroups: comp.soft-sys.matlab
Subject: Re: Summation and its condition
Date: Mon, 16 Feb 2009 14:24:01 +0000 (UTC)
Organization: John D'Errico (1-3LEW5R)
Lines: 84
Message-ID: <gnbsu1$5p9$1@fred.mathworks.com>
References: <gnbahb$4id$1@fred.mathworks.com>
Reply-To: "John D'Errico" <woodchips@rochester.rr.com>
NNTP-Posting-Host: webapp-02-blr.mathworks.com
Content-Type: text/plain; charset="ISO-8859-1"
Content-Transfer-Encoding: 8bit
X-Trace: fred.mathworks.com 1234794241 5929 172.30.248.37 (16 Feb 2009 14:24:01 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Mon, 16 Feb 2009 14:24:01 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 869215
Xref: news.mathworks.com comp.soft-sys.matlab:518580

"akihiro mizutani" <aki.mizutani@gmail.com> wrote in message <gnbahb$4id$1@fred.mathworks.com>...
> Hello.
> 
> I&#8217;ve just started to use matlab.
> And I&#8217;m stacked in the problem on summation condition.
> 
> Now I&#8217;m writing a code to get the result of following summation
> 
> Sum[(Aj*Ak-Bj*Bk)(Am*An-Bm*Bn)]
> 
> Where An and Bn are arrays respectively and length(An)=length(Bn)=N.
> And the summation should be carried out only for those combinations of indices j, k, m, n that satisfy following conditions;
> 
> J+k=m+n, j<k, m<n, j<m.
> 
> At this, the indices may take any integer value but from 1 to N only.
> 
> Does anyone know how to define such conditions and carry out the summation for all combinations which satisfy the conditions?
> I would be grateful if someone gave me a tip for solving the problem.
> 
> Thanks
> Akihro

Ok, if you must solve this, I'll show you a way.
It is surely not the only way, nor even the best
way, but it will work reasonably for reasonable
problems. With N as large as 2000, it might fall
short, but that is a big number.

I'll pick some random vectors A and B to test
this on.

  N = 250;
  A = rand(1,N);
  B = rand(1,N);

Now for the algorithm. We will look at the
sum of j+k, fixing that sum to reduce your
problem, and then loop over the various
possible values of that index sum. Thus

% L = j + k = m + n
finalsum = 0;
for L = 2:(2*N)
  % L can be no smaller than 2, and no
  % larger than 2*N.
  % The possible values of j and k (as well
  % as m and n) given L = j + k
  j = 1:N;
  k = L - j;
  ind = (j>0) & (j<=N) & (k>0) & (k<=N) & (j < k);
  j = j(ind);
  k = k(ind);
  
  % now choose the corresponding m and n
  ind = 1:length(j);
  [indjk,indmn] = meshgrid(ind);
  indjk = indjk(:);
  indmn = indmn(:);
  
  % toss those out where j >= m
  ind = j(indjk) >= j(indmn);
  indjk(ind) = [];
  indmn(ind) = [];
  
  finalsum = finalsum + sum(...
     (A(j(indjk)).*A(k(indjk)) - B(j(indjk)).*B(k(indjk))).* ...
     (A(j(indmn)).*A(k(indmn)) - B(j(indmn)).*B(k(indmn))));
end

finalsum
finalsum =
    -0.065462

I don't know if this is correct, since I'd need
to carefully check the result and I don't have the
time right now. I did try it for N = 250, and the
time was reasonable. Even better, it looks like
I was off in my original O(N^4) estimate. This 
should take something like O(2*N^3) operations
which is doable for N = 2024.

HTH,
John