PARALLEL ALGORITHMS BASED ON TWO-DIMENSIONAL SPLITTING SCHEMES FOR MULTIDIMENSIONAL PARABOLIC EQUATIONS

摘要

The family of finite difference schemes for p-dimensional parabolic (p ≥ 3) equations in Cartesian coordinates and also for parabolic equations in cylindrical, spherical, thorical coordinates (p = 3) is described. These type of schemes is based upon idea of splitting multidimensional problem in sequence of two-one-dimensional tasks. Two-dimensional schemes (TDS's) have better accuracy in comparison of "classic" one-dimensional schemes (ODS's) and (or) TDS's may be used for boundary value problems in regions, which have more arbitrary forms. In many cases T'DS 's may been realized by means of fast direct methods - cyclic reduction (CR), Fourier analysis (FA), methods of FACR-type etc. Finally TDS's require letter total time solution, which includes time for arithmetic processing and data transfer time between processors on multiprocessor systems. Nowadays we are observing progress in multiprocessor systems (MPS), especially, in communication technique. For example, it is relatively easy to build PC-clusters with 4-64 processors and various communications structure. From point of total efficiency view we have at least four possibilities: 1) to increase PC performance; 2) to increase total number of PC; 3) to improve processor communication structure; 4) to improve communication channel performance. We propose performance theoretical analysis TDS's in comparison of ODS's for various connection structures -"linear", "matrix", "cubic" and "universal" type and for various processor number p, number of grid points in each coordinate direction N, and also in depend on ratio k = t_t/t_a. Here t_t- is the value of time transfer for one machine word between two neighboring processors, t_a- is typical time for one arithmetic operation. This analysis gives us possibility from the one side to choice best algorithm and from the other side well-balanced multiprocessor system for given task class. Further it will be used domain decomposition method for fast direct methods parallelization.