Complexity of the pipeline computation of a family of inner products (Q1058291)

We are interested in the minimum time T(S) necessary for computing a family \(S=\{<s_ i,s_ j>:\) \(s_ i,s_ j\in R^ p\), (i,j)\(\in E\}\) of inner products of order p, on a systolic array of order \(p\times 2\). We first prove that the determination of T(S) is equivalent to the partition problem and is thus NP-complete. Then we show that the designing of an algorithm which runs in time \(T(S)+1\) is equivalent to the problem of finding an undirected bipartite eulerian multigraph with the smallest number of edges, which contains a given undirected bipartite graph, and can therefore be solved in polynomial time.