Software

FINUFFT

FINUFFT is a set of libraries to compute efficiently three types of nonuniform fast Fourier transform (NUFFT) to a specified precision, in one, two, or three dimensions, on a multi-core shared-memory machine. The library has a very simple interface, does not need any precomputation step, is written in C++ (using OpenMP and FFTW), and has wrappers to C, fortran, MATLAB, octave, and python. As an example, given MM arbitrary real numbers \( {x_j} \) and complex numbers \( {c_j} \), with j=1,…,Mj=1,…,M, and a requested integer number of modes NN, the 1D type-1 (aka “adjoint”) transform evaluates the NN numbers.

$${f_k}=\sum_{j=1}^M {c_je^{ikx_{j}}}\textrm{,}\quad\textrm{ for }{k}\in\mathbb{Z}\mathrm{,}\quad-{N}/2\le{k}\le{N}/2-1$$

The \( {x_j} \) can be interpreted as nonuniform source locations, \( {c_j} \) as source strengths, and \( {f_k} \) then as the \( {k} \)th Fourier series coefficient of the distribution \( f(x) = \sum_{j=1}^M c_j \delta(x-x_j) \).
Such exponential sums are needed in many applications in science and engineering, including signal processing, imaging, diffraction, and numerical
partial differential equations. The naive CPU effort to evaluate (1) is O(NM)O(NM). The library approximates (1) to a requested relative precision ϵϵ with nearly linear effort O(Mlog(1/ϵ)+NlogN)O(Mlog⁡(1/ϵ)+Nlog⁡N). Thus the speedup over the naive cost is similar to that achieved by the FFT. This is achieved by spreading onto a regular grid using a carefully chose kernel, followed by an upsampled FFT, then a division (deconvolution) step.

MountainSort/MountainLab

MountainLab is data processing, sharing and visualization software for scientists. It is built around MountainSort, a spike sorting algorithm, but is designed to more generally applicable.

MountainSort is spike sorting software developed by Jeremy Magland, Alex Barnett, and Leslie Greengard at the Center for Computational Biology, Flatiron Institute in close collaboration with Jason Chung and Loren Frank at UCSF department of Physiology. The algorithm was featured in

Chung, Jason E.*, Jeremy F. Magland*, Alex H. Barnett, Vanessa M. Tolosa, Angela C. Tooker, Kye Y. Lee, Kedar G. Shah, Sarah H. Felix, Loren M. Frank, and Leslie F. Greengard. “A Fully Automated Approach to Spike Sorting.” Neuron 95, no. 6 (2017): 1381-1394.

MountainSort is a plugin package to MountainLab, a general framework for scientific data analysis, sharing, and visualization.

ISO-SPLIT

ISO-SPLIT is an efficient clustering algorithm that handles an unknown number of unimodal clusters in low to moderate dimension, without any user-adjustable parameters. It is based on repeated tests for unimodality—using isotonic regression and a modified Hartigan dip test—applied to 1D projections of pairs of putative clusters. It handles well non-Gaussian clusters of widely varying densities and populations, and in such settings has been shown to outperform K-means variants, Gaussian mixture models, and density-based methods.

Fast sinc transform library

Fast sinc transform libraries which compute sums of the sinc and sinc2 kernels between N arbitrary points in 1, 2, or 3 dimensions. This has applications in MRI and band-limited function approximation. The naive cost is O(N2) whereas our algorithm is quasi-linear in N.

Written by our 2017 summer intern Hannah Lawrence.

Advancing Research in Basic Science and MathematicsSubscribe to Flatiron Institute announcements and other foundation updates