Re: asking suggestions on the algorithm in compution.Thanks.

From: Paul A. Rubin (rubin_at_msu.edu)
Date: 10/29/04 

Date: Fri, 29 Oct 2004 17:57:58 -0400

ZHANG Yan wrote:
> Thank you very much for your comments. I am very sorry that I have not
> stated the questions very clearly. Hope that the following is more
> clear.
>
> //////////////////////////////////////////////////////////////////////
> Input: k,A,b
> //k is integer; A is integer; b is integer
> Output:X
>
> X = 0.0
> for k = 1..A

You're contradicting yourself here. Either k is an input or k is a loop
index; it cannot be both. I'll assume you meant it to be a loop index.

> for all possible set (m_1,m_2,...,m_k) satisfying m_1+m_2+...+m_k =
> b
> X = X + f_1(m_1) * f_2(m_2) * ... * f_k(m_k)
> end
> end
>
> //in this algorithm, f_i(m_i) is a function with m_i as input.
>
>
> The difficulty lies in the fact that there are too many possible
> combination of set (m_1,m_2,...,m_k) satisfying m_1+m_2+...+m_k = b.
> So, the number of cycle is ver high.
>
> Can you plz give some suggestions in reduce the computation time and
> complexity? Thank you very much.
> --
> Y.ZHANG

I assume that you want the m_j to be either positive or nonnegative
integers as well (?).

The first thing to do is to tabulate f_1(x) for x=0,...,b and save that,
then tabulate f_2(x) for x=0,...,b, etc. That way you won't be wasting
time recomputing them each time they are used. (This assumes you have
enough memory to retain the tables.)

To do the summation, use recursion. Define a function g(bb,kk) (where
bb is the right hand side of the constraint, and kk is the index of the
last f function being used), as follows:

g(bb,kk) = sum {x=0...bb} f_kk(x)*g(bb-x,kk-1)

g(bb,1) = f_1(bb)

Your k-th sum then should be g(b,k). To get additional speed reductions
(at the cost of increased memory use), you can put each computed value
of g in a table, so that you can look it up if/when it is used again later.

How much total work is this? We have A*(b+1) function evaluations
f_j(x) up front. After that, we tabulate g(bb,kk) for bb=0...b and
kk=2...A, so we compute (A-1)(b+1) values of g(). Computing g(bb,kk)
involves bb+1 multiplications, bb+1 additions (assuming you initialized
the running total to 0), and 2*(bb+1) lookups. So the total work for
g(bb,kk) is proportional to bb+1, which means the work to tabulate
g(bb,kk) for all bb=0...b is O(b^2), and so the work to tabulate all
values of g is O(A*b^2).

-- Paul

******************************************************************************************
Paul A. Rubin Phone:
    (517) 432-3509
Department of Management Fax: (517)
432-1111
The Eli Broad Graduate School of Management E-mail: rubin@msu.edu
Michigan State University
http://www.msu.edu/~rubin/
East Lansing, MI 48824-1122 (USA)
******************************************************************************************
Mathematicians are like Frenchmen: whenever you say something to them,
they translate it into their own language, and at once it is something
entirely different. J. W. v. GOETHE

Relevant Pages