The communication complexity of several problems in matrix computation
Jeff I Chu, Georg Schnitger · 1989
The communication complexity of a function f measures the communication capacity any system computing f must provide.In Lqe design of VLSI systems, where savings on the chip area and computation time are desired, this complexity dictates an area x t/me 2 .lowerbound.In this paper, we investigate the communication complexity of singdarity testing, where the problem is to determine whether a given square matrix M is singular.We show that, for n x n matrices of k-bit integers, the communication complexity of this problem is O(knZ).In case the entries of M are elements of a finite field of size p , we also prove the communication complexity of this problem to be O(n21ogp ).Oar results are new and imply fight bounds for a wide variety of other problems in Numerical Linear Algebra.Among those problems are determ/n/ng the rank and computing the determinant, as well as the computation of several matr/x decompositions.Another important corollary concerns the solvability of linear systems.In this problem it has to be decided whether a linear system Ax=b has a solution.When A is an