Prev: How Can ZFC/PA do much of Math - it Can't Even Prove PA is Consistent (EASY PROOF)
Next: Both powers?
From: achille on 15 Jun 2010 19:01
On Jun 14, 11:47 pm, DocJack <docjack...(a)gmail.com> wrote:
> Hello!
>
> I have a problem regarding addition of a large number of parcels, as
> follows:
>
> Let a_1, a_2, a_3, ..., a_M be vectors of N components each. All
> components are real numbers between 0 and 1. We have a total of M*N
> numbers. I need to evaluate the sum of all possible products of the
> form:
>
> a_1(i_1)*a_2(i_2)*...*a_M(i_M)
>
> where i_1, i_2, ..., i_M are integers between 1 and N such that NO
> repetition of indices occur.
>
> Just to make things clearer: Let M=3 and N=4: The parcels are of the
> form:
>
> a(i)*b(j)*c(k)
>
> (where a=a_1, b=a_2 and c=a_3, to make notation easier)
>
> The possible combination of indices are:
>
> i, j, k:
> 1, 2, 3
> 1, 2, 4
> 1, 3, 2
> 1, 3, 4
> 1, 4, 2
> 1, 4, 3
> 2, 1, 3
> ...
> 4, 3, 2
>
> Total being 4*3*2 = 24 combinations. The wanted result is
>
> sum = a(1)*b(2)*c(3) + a(1)*b(2)*c(4) + ... + a(4)*b(3)*c(2).
>
> The problem is that this gets computationally unfeasible for large N,
> as the number of parcels is given by N*(N-1)*(N-2)*...*(N-M+1).
>
> Does anyone knows of a clever way to do this sum? Perhaps adding some
> of the components before multiplying?
>
> I have solved the same problem when repetition of the indices is
> allowed: The sum of all combinations of the form
> a_1(i_1)*a_2(i_2)*...*a_M(i_M) when the indices i_1, ..., i_M can have
> any value between 1 an N can be written as:
>
> sum(a_1) * sum(a_2) * ... * sum(a_M)
>
> where sum(x) = x(1) + x(2) + ... + x(N).
>
> So that the initial sum with N^M parcels is computed with N*M
> additions and M products. But, restricting no non-reapeating
> combinations makes the problem much harder.
>
> Any help will be appreciated.
>
> Thanks!

How big is M? When M is very small, it seems to me
one can compute your number with an algorithm of
complexity O(3*2^(M-1)*M*N).
From: DocJack on 17 Jun 2010 09:12
On 15 jun, 20:01, achille <achille_...(a)yahoo.com.hk> wrote:
> On Jun 14, 11:47 pm, DocJack <docjack...(a)gmail.com> wrote:
>
>
>
>
>
> > Hello!
>
> > I have a problem regarding addition of a large number of parcels, as
> > follows:
>
> > Let a_1, a_2, a_3, ..., a_M be vectors of N components each. All
> > components are real numbers between 0 and 1. We have a total of M*N
> > numbers. I need to evaluate the sum of all possible products of the
> > form:
>
> > a_1(i_1)*a_2(i_2)*...*a_M(i_M)
>
> > where i_1, i_2, ..., i_M are integers between 1 and N such that NO
> > repetition of indices occur.
>
> > Just to make things clearer: Let M=3 and N=4: The parcels are of the
> > form:
>
> > a(i)*b(j)*c(k)
>
> > (where a=a_1, b=a_2 and c=a_3, to make notation easier)
>
> > The possible combination of indices are:
>
> > i, j, k:
> > 1, 2, 3
> > 1, 2, 4
> > 1, 3, 2
> > 1, 3, 4
> > 1, 4, 2
> > 1, 4, 3
> > 2, 1, 3
> > ...
> > 4, 3, 2
>
> > Total being 4*3*2 = 24 combinations. The wanted result is
>
> > sum = a(1)*b(2)*c(3) + a(1)*b(2)*c(4) + ... + a(4)*b(3)*c(2).
>
> > The problem is that this gets computationally unfeasible for large N,
> > as the number of parcels is given by N*(N-1)*(N-2)*...*(N-M+1).
>
> > Does anyone knows of a clever way to do this sum? Perhaps adding some
> > of the components before multiplying?
>
> > I have solved the same problem when repetition of the indices is
> > allowed: The sum of all combinations of the form
> > a_1(i_1)*a_2(i_2)*...*a_M(i_M) when the indices i_1, ..., i_M can have
> > any value between 1 an N can be written as:
>
> > sum(a_1) * sum(a_2) * ... * sum(a_M)
>
> > where sum(x) = x(1) + x(2) + ... + x(N).
>
> > So that the initial sum with N^M parcels is computed with N*M
> > additions and M products. But, restricting no non-reapeating
> > combinations makes the problem much harder.
>
> > Any help will be appreciated.
>
> > Thanks!
>
> How big is M? When M is very small, it seems to me
> one can compute your number with an algorithm of
> complexity O(3*2^(M-1)*M*N).- Ocultar texto das mensagens anteriores -
>
> - Mostrar texto das mensagens anteriores -

Thanks again. The article suggest by prof. Israel seems very
intersting, I'll take a look. Unfortunately, M ~ 20 an N ~ 1000, so we
get ~ 30 giga flops for the exact computation, which is unacceptable,
considering that I need to evaluate this sum a lot of times...

The sum in question is proportional to the probability of obtaining a
particular vector (k_1, ..., k_M) (in R^M) of observations of a finite
population divided in N clusters, provided that a_i(j) is the
probability of obtaining the i-th component (k_i) from the subsampling
in the j-th cluster.

I had in mind computing the aforementioned probability for a large set
of observation vectors, in order to decide for rejection or not of a
given set of parameters. And it gets even worst, as a large set of
parameters needs to be tested!

Now I believe a completelly different approach is required. I'll try
to put the parcels in increasing order, so that the addition stops as
soon as the result gets larger than the significance level.

Thanks again. If you have any more links on these subjects, it will be
much appreciated.

First  |  Prev  | 
Pages: 1 2
Prev: How Can ZFC/PA do much of Math - it Can't Even Prove PA is Consistent (EASY PROOF)
Next: Both powers?