research diary

The reason it is better to do convolution in fourier space is that, in one dimension, direct convolution is a Θ(n²) operation, while the fast fourier transform is only Θ(n log n). Once in fourier space, convolution is simply an elementwise multiplication, Θ(n). Thus it's asymptotically 'cheaper' to go into fourier space, do the multiplcation, and take the inverse transform, than it is to just do the convolution directly. (c.f. CLR §30).

At 16:30 we had our meeting ("party") with Greta at Charlie's. The other students who have arrived so far and were at the meeting were: Jool (Joel?) from Canada, Adam from USA, Timur from Russia, Toni from Germany, Ira from India, Dogan from Turkey, Marija from Yugoslavia/Serbia, Taylan from Turkey, Arielle from Canada, Yaakov from USA, me, and Ilija from Yugoslavia/Serbia. It seems a little like we all came in pairs from our respective countries. Apparently we've all received the same directions from our parents; officially nearly all of us are restricted to Rehovot or even sequestered to the Institute campus.