| We describe a new class of algorithms for the solution of parabolic partial differential equations (PDEs). This class of schemes is based on three principal observations. First, the spatial discretization of parabolic PDEs results in a stiff system of ordinary differential equations (ODEs) in time, and therefore, requires an implicit method for its solution. Spectral Deferred Correction (SDC) methods use repeated iterations of a low-order method (e.g. implicit Euler method) to generate a high-order scheme. As a result, SDC methods of arbitrary order can be constructed with the desired stability properties necessary for the solution of stiff differential equations. Furthermore, for large systems, SDC methods are more computationally efficient than implicit RungeKutta schemes. Second, implicit methods for the solution of a system of linear ODEs yield a linear system that must be solved on each iteration. It is well known that the linear system constructed from the spatial discretization of parabolic PDEs is sparse. In R 1, this linear system can be solved in O( n) where n is the number of spatial discretization nodes. However, in R 2, the straightforward spatial discretization leads to matrices with dimensionality n2 x n2 and bandwidth n. While fast inversions schemes of O(n3) exists, we use alternating direction implicit (ADI) methods to replace the single two-dimensional implicit step with two sub-steps where only one direction is treated implicitly. This approach results in schemes with computational cost O(n2). Likewise, ADI methods in R 3 have computational cost O( n3). While popular ADI methods are low-order, we combine the SDC methods with an ADI method to generate computationally efficient, high-order schemes for the solution of parabolic PDEs in R 2 and R 3. Third, traditional pseudospectral schemes for the representation of the spatial operator in parabolic PDEs yield differentiation operators with eigenvalues that can be excessively large. We improve on the traditional approach by subdividing the entire spatial domain, constructing bases on each subdomain, and combining the obtained discretization with the implicit SDC schemes. The resulting class of schemes are high-order in both time and space and have computational cost O(N · M) where N is the number of spatial discretization nodes and M is the number of temporal nodes. We illustrate the behavior of these schemes with several numerical examples. |
