TOTALLY PARALLEL MULTILEVEL ALGORITHMS

作     者：PAUL O. FREDERICKSON 

作者机构：RIACS Ames Research Center Moffett Field CA 94035 

出 版 物：《International Journal of High Speed Computing》 

年 卷 期：1989年第1卷第2期

页      面：233-245页

主　　题：multilevel algorithm multigrid cyclic reduction spectral method 

摘      要：Four totally parallel algorithms for the solution of a sparse linear system have common characteristics which become quite apparent when they are implemented on a highly parallel hypercube such as the CM2. These four algorithms are Parallel Superconvergent Multigrid (PSMG) of Frederickson and McBryan, Robust Multigrid (RMG) of Hackbusch, the FFT based Spectral Algorithm, and Parallel Cyclic Reduction. In fact, all four can be formulated as particular cases of the same totally parallel multilevel algorithm, which we will refer to as TPMA. In certain cases the spectral radius of TPMA is zero, and it is recognized to be a direct algorithm. In many other cases the spectral radius, although not zero, is small enough that a single iteration per timestep keeps the local error within the required tolerance.