| In parallel computing systems the tasks of computation are shared among a number of active elements. Thus the computation time can be reduced significantly. However, the requirement of communication among these active elements demands additional computational resources. The communication complexity of a function f measures the communication capacity any system computing f must have. In the design of VLSI systems, where savings on the chip area and computation time are desired, this complexity dictates an area x time{dollar}sp2{dollar} 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 when M is an n x n matrix of {dollar}k{dollar}-bit integers, the communication complexity of this problem if {dollar}Theta (knsp2){dollar}. 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 {dollar}Theta (nsp2{dollar}log{dollar}sb2p){dollar}.; Our results are new and imply tight bounds for a wide variety of other problems in Numerical Linear Algebra. This includes problems like determining rank and computing the determinant, as well as the computation of several matrix decompositions. We also simplify and unify existing results on the communication complexity of matrix multiplication, matrix inversion and integer multiplication. |
