Prev: How Can ZFC/PA do much of Math - it Can't Even Prove PA is Consistent (EASY PROOF)
Next: Both powers?
From: DocJack on 14 Jun 2010 11:47
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!

From: cwldoc on 14 Jun 2010 08:37
> 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!
>
>

Here are some thoughts I have; I don't know if they will be of any value to you:

In the special case that M = N, the desired sum is simply the determinant of the N X N matrix whose N rows are the vectors a_1, a_2, a_3, ..., a_N. One could calculate the value in terms of the cofactors; this procedure would have to be repeated N times.

In the more general case, perhaps there is some way to express the sum in the case of M vectors of length N+1 in terms of the sum in the case of M vectors of length N; if so, then you could start with the determinant in the case of M vectors of length M, and, after N-M iterations, solve for the sum in the case of M vectors of length N.
From: Gerry Myerson on 14 Jun 2010 20:01
In article
<1785417598.332085.1276533506556.JavaMail.root(a)gallium.mathforum.org>,
cwldoc <cwldoc(a)aol.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!
> >
> >
>
> Here are some thoughts I have; I don't know if they will be of any value to
> you:
>
> In the special case that M = N, the desired sum is simply the determinant of
> the N X N matrix whose N rows are the vectors a_1, a_2, a_3, ..., a_N.

Determinants have some minus signs in them, no?
Maybe you're getting the *permanent* of the matrix,
which is much harder to compute than the determinant.

> One
> could calculate the value in terms of the cofactors; this procedure would
> have to be repeated N times.
>
> In the more general case, perhaps there is some way to express the sum in the
> case of M vectors of length N+1 in terms of the sum in the case of M vectors
> of length N; if so, then you could start with the determinant in the case of
> M vectors of length M, and, after N-M iterations, solve for the sum in the
> case of M vectors of length N.

--
Gerry Myerson (gerry(a)maths.mq.edi.ai) (i -> u for email)
From: DocJack on 15 Jun 2010 13:00
On 14 jun, 21:01, Gerry Myerson <ge...(a)maths.mq.edi.ai.i2u4email>
wrote:
> In article
> <1785417598.332085.1276533506556.JavaMail.r...(a)gallium.mathforum.org>,
>
>
>
>
>
>  cwldoc <cwl...(a)aol.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!
>
> > Here are some thoughts I have; I don't know if they will be of any value to
> > you:
>
> > In the special case that M = N, the desired sum is simply the determinant of
> > the N X N matrix whose N rows are the vectors a_1, a_2, a_3, ..., a_N.
>
> Determinants have some minus signs in them, no?
> Maybe you're getting the *permanent* of the matrix,
> which is much harder to compute than the determinant.
>
> > One
> > could calculate the value in terms of the cofactors; this procedure would
> > have to be repeated N times.
>
> > In the more general case, perhaps there is some way to express the sum in the
> > case of M vectors of length N+1 in terms of the sum in the case of M vectors
> > of length N; if so, then you could start with the determinant in the case of
> > M vectors of length M, and, after N-M iterations, solve for the sum in the
> > case of M vectors of length N.
>
> --
> Gerry Myerson (ge...(a)maths.mq.edi.ai) (i -> u for email)- Ocultar texto das mensagens anteriores -
>
> - Mostrar texto das mensagens anteriores -

Thanks!

Indeed, it seems to be related to the permanent of a matrix. However,
the case N=M does not occur to me... I've found this problem trying to
compute the sampling distribution of a linear estimator in a finite
population sampled in two stages (i. e., clusters). So N is the number
of clusters (tipically large) and M is the number of clusters in the
sample. I've found one single article that mentions the "permanent of
a rectangular matrix", but this seems to be a very obscure subject.

I've also found claims that computing the permanent of a rectangular
matrix whose entries are either 0 or 1 in polynomial time implies that
P=NP, a problem whose solution is worth a million dollar prize and a
medal from the Clay Institute...


From: Robert Israel on 15 Jun 2010 15:00
DocJack <docjack666(a)gmail.com> writes:

> On 14 jun, 21:01, Gerry Myerson <ge...(a)maths.mq.edi.ai.i2u4email>
> wrote:
> > In article
> > <1785417598.332085.1276533506556.JavaMail.r...(a)gallium.mathforum.org>,
> >
> >
> >
> >
> >
> > =A0cwldoc <cwl...(a)aol.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=3D3 and N=3D4: The
> > > > parcels are of the
> > > > form:
> >
> > > > a(i)*b(j)*c(k)
> >
> > > > (where a=3Da_1, b=3Da_2 and c=3Da_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 =3D 24 combinations. The wanted
> > > > result is
> >
> > > > sum =3D 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) =3D 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!
> >
> > > Here are some thoughts I have; I don't know if they will be of any
> > > valu=
> e to
> > > you:
> >
> > > In the special case that M =3D N, the desired sum is simply the
> > > determi=
> nant of
> > > the N X N matrix whose N rows are the vectors a_1, a_2, a_3, ..., a_N.
> >
> > Determinants have some minus signs in them, no?
> > Maybe you're getting the *permanent* of the matrix,
> > which is much harder to compute than the determinant.
> >
> > > One
> > > could calculate the value in terms of the cofactors; this procedure
> > > wou=
> ld
> > > have to be repeated N times.
> >
> > > In the more general case, perhaps there is some way to express the sum
> > > =
> in the
> > > case of M vectors of length N+1 in terms of the sum in the case of M
> > > ve=
> ctors
> > > of length N; if so, then you could start with the determinant in the
> > > ca=
> se of
> > > M vectors of length M, and, after N-M iterations, solve for the sum in
> > > =
> the
> > > case of M vectors of length N.
> >
> > --
> > Gerry Myerson (ge...(a)maths.mq.edi.ai) (i -> u for email)- Ocultar texto
> > d=
> as mensagens anteriores -
> >
> > - Mostrar texto das mensagens anteriores -
>
> Thanks!
>
> Indeed, it seems to be related to the permanent of a matrix. However,
> the case N=3DM does not occur to me... I've found this problem trying to
> compute the sampling distribution of a linear estimator in a finite
> population sampled in two stages (i. e., clusters). So N is the number
> of clusters (tipically large) and M is the number of clusters in the
> sample. I've found one single article that mentions the "permanent of
> a rectangular matrix", but this seems to be a very obscure subject.

You can "reduce" it to an N x N permanent: make all entries in the other
(N-M) columns 1, and divide the permanent of this square matrix by (N-M)!.
Of course, in the absence of an efficient way to compute permanents of
square matrices, that may not be helpful.

> I've also found claims that computing the permanent of a rectangular
> matrix whose entries are either 0 or 1 in polynomial time implies that
> P=3DNP, a problem whose solution is worth a million dollar prize and a
> medal from the Clay Institute...

It's even worse than that, apparently: computing the permanent of a matrix of
0's and 1's is #P-complete. However, since your entries are nonnegative, you
may be interested in the following article:

M. Jerrum, A. Sinclair, E. Vigoda: "A polynomial-time approximation algorithm
for the permanent of a matrix with nonnegative entries", Journal of the ACM 51
(2004), 671 - 697
<http://doi.acm.org/10.1145/1008731.1008738>

>
--
Robert Israel israel(a)math.MyUniversitysInitials.ca
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia Vancouver, BC, Canada
 |  Next  |  Last
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?