Fast Stencil Computations using FFT and Gaussian Approximations

Speaker: Rezaul Chowdhury

Date: Wednesday, October 05, 2022

Time: 4:00 PM to 5:00 PM Note: all times are in the Eastern Time Zone

Public: Yes

Location: https://mit.zoom.us/meeting/register/tJMtdOqgrTwsGNV_k0Nk6JjLMk-G6GFzTRyk

Event Type: Seminar

Room Description: https://mit.zoom.us/meeting/register/tJMtdOqgrTwsGNV_k0Nk6JjLMk-G6GFzTRyk

Host: Julian Shun, MIT CSAIL

Contact: Linda Lynch, 715-2459, lindalynch@csail.mit.edu

Relevant URL: http://fast-code.csail.mit.edu/

Speaker URL: https://www3.cs.stonybrook.edu/~rezaul/

Speaker Photo:
None

Reminders to: fast-code-seminar@lists.csail.mit.edu, seminars@csail.mit.edu, pl@csail.mit.edu, commit@lists.csail.mit.edu, toc@csail.mit.edu

Reminder Subject: TALK: Fast Stencil Computations using FFT and Gaussian Approximations

******************IMPORTANT NOTE ABOUT REGISTRATION******************
- The registration link for Fall 2022 is the same as the link from Spring 2022.
- Please save the Zoom link that you receive after you register. This link will stay the same for all subsequent Fast Code seminars.
- Zoom does not recognize a second registration, and will not send out the link a second time. The organizers will not be notified of any second registration.
- If you have any problems with registration, please contact lindalynch@csail.mit.edu by 3pm on the day of the seminar, so that we can try to resolve it before the seminar begins.
*********************************************************************

ABSTRACT: Stencil computations are widely used to simulate the change of state of physical systems across a multidimensional grid over multiple timesteps. I will talk about our recent results on performing general linear stencil computations significantly faster than state-of-the-art algorithms under periodic, aperiodic, and freespace boundary conditions.

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 Gaussian approximations 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 Zafar Ahmad, Rathish Das, Pramod Ganapathi, Aaron Gregory, and Yimin Zhu. Most of the work was done when all authors were affiliated with the Stony Brook University. The results appeared in the proceedings of SPAA’21 and SPAA’22.

BIO: Rezaul Chowdhury is an Associate Professor of Computer Science at Stony Brook University and a core faculty member of the Institute for Advanced Computational Science (IACS). His research interests are in the fields of algorithm design and algorithm engineering and their intersections with other sciences. He is particularly interested in the design and theoretical/practical performance analysis of shared-memory parallel algorithms. His research interests also include computational biology and bioinformatics, particularly protein-protein docking and fast energetics computation.

Research Areas:
Algorithms & Theory, Programming Languages & Software

Impact Areas:
Big Data

This event is not part of a series.

Created by Julian J. Shun at Friday, September 30, 2022 at 4:37 PM.