IMPLICIT-EXPLICIT PARALLEL ASYNCHRONOUS SOLVER OF PARABOLIC PDES

This paper presents a method for the solution of parabolic PDEs on par allel computers, which is a combination of implicit and explicit finit e difference schemes based on a domain decomposition (DD) strategy. Mo reover, this method is asynchronous (i.e., no explicit synchronization is required among processors). We determine the values at subdomains' boundaries by our new high-order asynchronous explicit schemes. Then, any known high-order implicit finite difference scheme can be applied within each subdomain. We present a technique for derivation of appro priate asynchronous-explicit schemes based on Green's functions. Synch ronous versions of these schemes are obtained as special cases. The ap plicability of this method is also demonstrated for a family of nonlin ear problems. Our new explicit schemes are of high order and yet stabl e for a large time step, as established in our analysis of their numer ical properties. Moreover, these schemes provide attractive properties for parallel implementation. Being asynchronous, they allow local tim e stepping, thus eliminating the need for a global synchronized time s tep. Moreover, our asynchronous computation is time stabilizing, in th e sense that the calculation implicitly prevents a growing time gap be tween neighboring subdomains. The locality property, due to the expone ntial decay of Green's functions, implies that communication is needed only between neighboring processors. Hence, this method which is desi gned to minimize the overhead associated with the synchronization of t he multiple processors is specifically suitable for parallel computers having a high synchronization cost or highly varying load, even in ca ses in which some processors have persistent speed differences. Furthe rmore, the implementation of different resolution in each subdomain (e .g., irregular or unstructured grid) makes it valuable as an adaptive algorithm. The above schemes were implemented and tested on the shared -memory multi-user Cray J90 and Sequent Balance machines. These implem entations prove high accuracy and high degree of parallelism. This wor k is complementary to our previous work on asynchronous schemes [Compu t. Math. Appl., 24 (1992), pp. 33-53; Appl. Numer. Math., 12 (1993), p p. 27-45; Numer. Algorithms,6 (1994), pp. 275-296; Numer. Algorithms, 12 (1996), pp. 159-192].