ABSTRACT: A stencil is a pattern used to compute the value of a cell in a spatial grid at some time step from the values of nearby cells at prior time steps. A stencil computation applies a given stencil to the cells in a spatial grid for some given number of time steps. Such computations arise in many areas of scientific computing, including the simulation of physical systems, traffic flows, meteorology, stochastic and fractional differential equations, chemistry, modeling of erosion, fluid dynamics, quantitative finance, and even cellular automata.
In this talk I will give an overview of our recent results on performing general linear stencil computations significantly faster than state-of-the-art algorithms under periodic, aperiodic, and freespace boundary conditions. I will also briefly discuss if and how our techniques can be used to speed up nonlinear stencil applications.
Our algorithm for periodic grids is based on the Fast Fourier Transform (FFT), and our aperiodic-grid algorithm uses our periodic solver repeatedly in a recursive divide-and-conquer framework. Our freespace algorithm, on the other hand, uses a different approach based on random walks and n-body computations. All our algorithms have asymptotically lower computational complexity than all existing algorithms for general linear stencils, and are highly parallelizable. While implementations of all our algorithms run faster than the fastest known linear stencil codes, our periodic and freespace solvers run orders of magnitude faster than the state of the art.
This talk presents joint work with (alphabetically by last name) Zafar Ahmad, Rathish Das, Pramod Ganapathi, Aaron Gregory, and Yimin Zhu. Most of the work was done when all authors were affiliated with Stony Brook University. The results appeared in the proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures'' (SPAA) in 2021 and 2022.
Mathematical or computational techniques used in Prof. Chowdhury's research: Fast Fourier Transform (FFT), Fast Multipole Method (FMM), Recursive Divide and Conquer
Disciplines outside of computer science that contribute to this research: Applied Mathematics, Applied Physics, Mechanical Engineering, Quantitative Finance, Meteorology, etc.
Join Zoom Meeting
https://stonybrook.zoom.us/j/98190951053?pwd=a21vUExtU1FlaFo1MHphcm1CN3AzZz09
Meeting ID: 981 9095 1053
Passcode: 366466
