The communication complexity of several problems in matrix computation

AbstractThe communication complexity of a function f measures the communication resources required for computing f. In the design of VLSI systems, where savings on the chip area and computation time are desired, this complexity dictates an area × time2 lower bound. We investigate the communication complexity of singularity testing, where the problem is to determine whether a given square matrix M is singular. We show that, for n × n matrices of k-bit integers, the communication complexity of Singularity Testing is Θ(k n2). Our results imply tight bounds for a wide variety of other problems in numerical linear algebra. Among those problems are determining the rank and computing the determinant, as well as the computation of several matrix decompositions. Another important corollary concerns the solvability of systems of linear equations. This problem is to decide whether a linear system A x = b has a solution. When A is an n × n matrix of k-bit integers and b a vector of n k-bit integers, its communication complexity is Θ(k n2)