Re: how to evaluate the addition of millions of functions dynamically and efficiently?

From: jim green (jjg_at_withheld.org.de)
Date: 08/15/04 

Date: Sun, 15 Aug 2004 13:33:51 GMT

"networm" <networm8848@yahoo.com> writes:

> The shape-defining PSF can be radially symmtric, for a round shaped dot,
> which is the first case you've mentioned, in need of a RBF monopole method;
> or it can be other strange shape, e.g. rectangular, which is the second case
> you've mentioned.
>
> For the first case, I did search google, did find 3590 hits, but did not see
> clearly how they are related to my worry: how to evaluate the value of the
> sum of these shifted functions(need to evaluate millions of time) fast; Can
> you give me some more clearer pointers?
>
> For the second case, though the rectangles are finitesupported, but they can
> be overlapped, how to smartly decide the overlapped neighbors which have
> impact on the point I am evaluating?

OK, since your functions have compact support and are on a regular
grid things get rather easy without resorting to mutipole methods.

We'll assume that the distance between adjacent grid nodes is d, and
that your functions have support in the square of side length x.

Now, suppose we are looking at the (i,j)-th grid point, then the only
non-zero contributions are from neighbours with centres a distance
at most x/2 away. Since the grid node separation is d, we take
k to be the smallest integer such that kd>x/2, then the indicies of
the neighbouring non-zero nodes are (i-k,j-k),...,(i,j-k),...,(i+k,j-k),
...(i-k,j+k),...,(i,j+k),...,(i+k,j+k). In other words you only need
to perform a *local* sum of the (2k)^2 nodes in the square centred on
the (i,j) node. Now do the same for every node.

If N is the number of grid nodes then this trick reduces the complexity
of your evaluation from O(N^2) to O(N(2k)^2)=O(N), which should be
feasible for N ~ 10^6.

This can be easily adapted to the case when the is grid rectangular,
rather than square (or if your functions has support in a rectangle
rather than a square) -- just treat the x- and y-coordinates
seperately. For functions with a circular support, just take the a
square containing the circle.

Hope this helps!

-j

Relevant Pages
Loading