Parallel calculation of a linear mapping on a computer network

AbstractWe are interested in the parallel computation of a linear mapping of n real variables by a network of computers with restricted means of communication between them and without any common memory. Let Mn×n(R) denote the algebra of n×n real matrices, and let G be the graph associated with a binary, reflexive and symmetric relation R over {1,2, …,n}. We define AR = {AϵMn×n(R):aij≠ 0 implies iRj} A matrix M∈Mn×n(R) is said to be realizable on G if it can be expressed as a product of elements of AR. Therefore, every matrix of Mn×n(R) is realizable on G if and only if AR generates Mn×n(R). We show that AR generates M n×n(R) if and only if G is connected