Low-complexity Algorithms to Solve Partial Differential Equations

The Discrete Fourier Transform (DFT) has plethora of applications in mathematics, physics, computer science, and engineering. Fast Fourier transform (FFT) is an algorithm used to efficiently compute DFT and its inverse. In this work, we obtain solutions to fundamental partial differential equations (PDEs) using fast, i.e. FFT-like, algorithms. In particular, solutions to the Heat equation, Wave equation, and Schrödinger equation are explored using low-complexity algorithms in connection to the sparse factorization of matrices. We compare the complexity in solving the PDEs using the standard Fourier transform in continuous domains vs the proposed fast algorithms in discrete domains. We also analyze the accuracy of the solutions and present simulation results based on the proposed algorithms