What I’m up to this month : Math, travels and programming

Hi all! I thought I would take a break from my vacations to give you a heads up on what I’m up to.

First things first, I’ve studied the theory behind the fast multipole method, an algorithm used to solve N-body problems. The algorithm by itself is pretty complex at first sight. How could we do better than the naive idea, calculating everything with O(N^2) cost? But then, a couple of very bright people present it going from the O(N^2) algorithm, to a straightforward O(N\log(N)) and then to the O(N) one. Cool math too! Instead of using a regular Taylor expansion for the far-field approximation, a multipole expansion (think of it as the generalization of Fourier series in three dimensions, which instead of sine and cosine uses spherical harmonics as the basis functions).

I’ve also added another tool to my problem-solving arsenal. 🙂 I can now use dimensional analysis to find quick estimates of a couple of “hard” integrals. For example,

\int_{1}^{\infty}e^{-ax}dx=f(a),\ a\geq 1

which is not one of the hard integrals I was talking about but this method works for integrals including e^{ax^n} .

Using dimensional analysis, we first just assign to x a dimension, such as length. Let’s denote that with L. Then, dx will have L as dimension (since it’s a little bit of x). Reasoning out that ax must be dimensionless since it’s an exponent, we can see that the dimension of a must be 1/L.  The integral is dimensionless. Thus, since both sides of an equation must have the same dimensions, we suppose that C/a is a good candidate for f(a) (since 1/a has dimensions 1/L. C is a dimensionless constant. Now we just need to find C, which is easy to estimate (or, in this case, find exactly). Just pick a=1 and then,

\int_{1}^{\infty}e^{-x}dx=\frac{1}{e}=C.

Thus,

\int_{1}^{\infty}e^{-xa}dx\simeq\frac{1}{e\cdot a}

Did we get the dimensionless constant right? Yes we did but by calculating the integral, we get

\int_{1}^{\infty}e^{-xa}dx=\frac{1}{e^{a}\cdot a}=\frac{1}{ea}\cdot\frac{1}{e^{a-1}}

Thus we managed to conjure an interesting approximation. Here is a graph of the error between our approximation and the exact solution.

Not bad, right?

And as I mentioned, the same idea seems to apply in the case of more difficult integrals such as those with terms e^{ax^n}.

Still, there are a couple of things that I don’t understand about dimensional analysis (when used in this context and mainly because I don’t have any good references to study from).  That’s why I am writing some notes on my own with what little I can find. Expect more on this in the near future. 😉

I am also trying to learn more about optimization of CUDA codes and how to apply all those ideas to an actual program. I was very lucky to find out about Git, cause now I can try whatever comes in mind without feeling bad or anxious that I might break my code.

It turns out that writing the code and optimizing it are two very different things. I have heard of branch divergence in CUDA but I wasn’t sure how it could affect the performance. Hopefully, I found an answer to that in Stack Overflow.

More news & math soon!

Advertisements

1 Comment

  1. Thank you for keeping us updated. I quite enjoy it and discover all of the info quite useful.

Comments are closed.