A BSP Bareiss algorithm for Toeplitz systems

In this paper, a BSP (bulk synchronous parallel) Bareiss algorithm for Toep litz system is described. We investigate various data distribution and sche duling strategies for mapping a typical class of systolic array algorithms onto BSP machines. Load balance, both in communication and computation, as well as linear speedup have been achieved for the Toeplitz system solver an d at the same time the minimum memory requirement is achieved. An implement ation has been tested on Sun workstations, an SGI Power Challenge, and an I BM SP?, using the Oxford BSPlib (Hill et al., 1997. (C) 1999 Academic Press .