Hybrid Dealiased Convolutions

• Author / Creator

  Murasko, Noel

• Efficient algorithms for computing linear convolutions based on the fast Fourier transform are developed. A hybrid approach is described that combines the conventional practice of explicit dealiasing (explicitly padding the input data with zeros) and implicit dealiasing (mathematically accounting for these zero values). The new approach generalizes implicit dealiasing to arbitrary padding ratios and includes explicit dealiasing as a special case. Unlike existing implementations of implicit dealiasing, hybrid dealiasing tailors its subtransform sizes to the convolution geometry. Hybrid dealiasing also extends implicit dealiasing to efficiently compute convolutions with real-valued inputs. Multidimensional convolutions are implemented with hybrid dealiasing by decomposing them into lower-dimensional convolutions. Convolutions of complex-valued, Hermitian symmetric, and real- valued inputs of equal length are illustrated with pseudocode and implemented in the open-source FFTW++ library. Hybrid dealiasing is shown to match or outperform explicit dealiasing in one dimension and greatly outperform explicit dealiasing in two and three dimensions.

• Subjects / Keywords

  • Numerical Methods
  • Hybrid Dealiasing
  • Implicit Dealiasing
  • Convolution
  • Fast Fourier Transform

• Graduation date

  Spring 2024

• Type of Item

  Thesis

• Degree

  Master of Science

• DOI

  https://doi.org/10.7939/r3-zhd1-nm91

• License

  This thesis is made available by the University of Alberta Libraries with permission of the copyright owner solely for non-commercial purposes. This thesis, or any portion thereof, may not otherwise be copied or reproduced without the written consent of the copyright owner, except to the extent permitted by Canadian copyright law.