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

From: networm (networm8848_at_yahoo.com)
Date: 08/16/04 

Date: Sun, 15 Aug 2004 18:57:33 -0700

"jim green" <jjg@withheld.org.de> wrote in message
news:874qn4wmo3.fsf@turbot.fishnet...
> "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

Hi Jim

I am also interested in the "RBF monopole" you've mentioned in your
previous post.

Do you think it will give me a drastic performance improvement? If so, I am
going to dive into it and learn how to make my program a lot faster...

Thank you very much,

-N

Relevant Pages