Skip to main content

Posts

Fast Fourier transform is slow

In the early 90's, when I was still getting my undergraduate computer engineering degree, I took a class in signal processing that I really enjoyed.  One of the major projects we were tasked to do was to implement a 2 dimensional fast fourier transform . The class spent several lectures proving that the number of mathematical for a simple implementation for convolution in the spacial domain required O(n^2) math operations.  On the other hand, if you switched to the frequency domain, you required O(n log(n)) operations to perform the FFT, O(n) to perform a single multiplication per pixel and then another O(n log(n)) to convert it back to the spacial domain. We proved it was better! And then we implemented it, and it was orders of magnitude slower.  Theory and practice didn't match. We showed it was slow! The issue was a boundary we had abstracted away in our performance proofs - memory access was not a uniform cost.  The math operations we were optimizing ...

What's in a name?

Naming things in software engineering is difficult , so I pondered what to call this blog for a long time before naming it.  I came up with boundary waters for a few reasons: I grew up near the Boundary Waters Canoe Area , and I have a lot of great memories visiting that majestic part of Minnesota. Software development has a lot of topic areas that are related to boundaries and it was a common theme in a lot of the initial topic areas I'm planning on writing about. There are a lot of different boundaries at the BWCA that I can use for analogies: The US - Canada border Lakes & islands The water itself The .dev domain became available and it's very unlikely to get confused with  the actual geographic area. I'm starting this blog on the one-year anniversary of changing jobs.  I left a company in the telecommunications industry I had spent over 26 years at to go work at Visa.  I now have a systems architecture role that does not include coding on a regu...