Parallel Networks for Multi-Grid Algorithms: Architecture and Complexity
Tony Fan-Cheong Chan, Robert Schreiber · SIAM Journal on Scientific and Statistical Computing · 1985
We describe and analyze a family of highly parallel special purpose computing networks that implement multi-grid algorithms for solving elliptic difference equations. The networks have many of the features and advantages of systolic arrays. We consider the speedup achieved by these designs and how this is affected by the choice of algorithm parameters and the level of parallelism employed. We find, for example, that when there is one processor per grid-point, the designs cannot avoid suffering a loss of efficiency as the grid-size tends to zero.