Time Parallel Algorithms for Solution of Linear Parabolic PDEs

In this paper, fast time- and space-parallel algorithms for solution of parabolic PDEs are developed. It is shown that the seemingly strictly serial time-stepping procedures for solution of problem can be completely decoupled. This is achieved by developing time-parallel algorithms which allow the solution for all time steps to be computed in parallel. The time-parallel algorithms have a highly decoupled structure and hence can be efficiently implemented on emerging massively parallel MIMD architectures with minimum communication and synchronization overhead.