The communication complexity of several problems in matrix computation

✍ Scribed by Jeff I Chu; Georg Schnitger

• Publisher: Elsevier Science
• Year: 1991
• Tongue: English
• Weight: 747 KB
• Volume: 7
• Category: Article
• ISSN: 0885-064X
• DOI: 10.1016/0885-064x(91)90027-u

✦ Synopsis

The communication complexity of a function f measures the communication resources required for computingf. In the design of VLSI systems, where savings on the chip area and computation time are desired, this complexity dictates an area x time* 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 x n matrices of k-bit integers, the communication complexity of Singularity Testing is O(k n*). 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 x n matrix of k-bit integers and b a vector of n k-bit integers, its communication complexity is O(k n*).