Take the 2-minute tour ×

I'm trying to sample a lot of points efficiently. I'm wondering if the following method is possible.

I sample points of a function (evaluate the function) mod $n$. I.e. I calculate f(element one), f(element 2)...f(element n). I do this for all of the points in a ring. Now I take a second ring (mod $m$, for instance) and calculate the points of a function for all elements of this ring.

So my idea is this: I've sampled only $n+m$ points, but the combinations of these sample points number $n \cdot m$. I'd like to calculate the sum of (evaluations of) this larger set of points efficiently. I'm wondering if this is possible.

I'd like to know as much about this idea as possible. I'd like to know related ideas, what's possible, or just general ideas on how to do this. Any pointers would constitute an acceptable answer to me, and an actual method would be absolutely wonderful.

I realize that this may be more of a numerical method than mathematics, but I'm hoping that everyone will accept this question, since it may allow new methods of integration as a result.

share|improve this question
As far as I know, numerical methods are a part of mathematics. But I'm confused by your question. What are the domain and codomain of your function $f$? –  Rahul Oct 26 '10 at 22:48
I tried to simplify the question. I want to sample $f$, whose domain and codomain are both complex. However, I can represent this by $\mathbb{C} /n \mathbb{R}$ if I have my terminology correct. However, I'd be satisfied with an example that uses only rings of integers. I'd also be satisfied with an example function whose domain and codomain are also integers or naturals. –  Matt Groff Oct 26 '10 at 22:57
"new methods of integration" - I presume you've looked at the literature on "adaptive quadrature"? –  Guess who it is. Oct 27 '10 at 14:07
I haven't. I just got really excited and wrote that. I'll learned a lesson from this, and hope to be more scientific in the future. Again, I'd like to know about everything related - "adaptive quadrature" articles seem promising. –  Matt Groff Oct 27 '10 at 16:02

1 Answer 1

up vote 2 down vote accepted

I recommend chapters 3 and 5 of Numerical Recipes. It sounds like you have a function f which is hard/expensive to evaluate. You can evaluate it wherever you like, just not too many times. You then use those values to model f in some way that is much easier to compute and use that model to get values at other points. What do you know about f? If you know it is a ninth-degree polynomial (just not which one) you can evaluate it at ten points, do a fit, and have exact values anywhere else (ignoring important issues of numeric accuracy). If you know it is a finite sum of trig functions, the Nyquist theorem tells you that proper sampling can also give you perfect accuracy on extrapolation. If you know it is multiplicative, evaluate it at a set of primes. If you don't know, maybe the best you can do is evaluate it on a grid and use splines.

An important question is what you will use the values at other points for. If you need an integral over some region, the formulas will tell you where to evaluate it to get high accuracy as long as your functional model is correct. For this, you wouldn't need the value at any other points. If you need derivatives, numeric differentiation is a noise amplifier and dangerous.

If your f is not in the class of functions you think, things can go badly wrong. NR has a classic example where poles off the real line can cause problems, even for fitting a real function.

It is important to remember that although you can get approximate values at other points, evaluating these values teaches you nothing about f. They teach you about g, which is the function within the class you selected to approximate f.

share|improve this answer

Your Answer


