Abstract
We investigate the communication complexity of singularity testing in a finite field, where the problem is to determine whether a given square matrixM is singular. We show that, forn×n matrices whose entries are elements of a finite field of sizep, the communication complexity of this problem is Θ(n 2 logp). Our results imply tight bounds for several other problems likedetermining the rank andcomputing the determinant.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
R. C. Agarwal, C. S. Burrus, Fast convolution using Fermat number transforms with application to digital filtering,IEEE Trans. Acoust. Speech Signal Process.,22 (1974), 87–97.
R. P. Brent, H. T. Kung, The chip complexity of binary arithmetic,J. Assoc. Comput. Mech.,28 (1981), 521–534.
B. Chor, O. Goldreich, Unbiased bits from sources of weak randomness and probabilistic communication complexity,Proc. 26th Annual IEEE Symp. on Foundations of Computer Science, 1985, pp. 429–442.
J. I. Chu, G. Schnitger, The communication complexity of several problems in matrix computation,J. Complexity,7 (1991), 395–407.
L. Lovász, M. Saks, Lattices, möbius functions and communication complexity,Proc. 29th Annual IEEE Symp. on Foundations of Computer Science, 1988, pp. 81–90.
A. V. Oppenheim, C. Weinstein, Effects of finite register length in digital filtering and the fast Fourier transform,Proc. IEEE,60 (1972), 957–976.
J. M. Pollard, The fast Fourier transform in a finite field,Math. Comp.,25 (1971), 365–374.
N. S. Szabo, R. I. Tanaka,Residue Arithmetic and Its Applications to Computer Technology, McGraw-Hill, New York, 1967.
C. D. Thompson, Area time complexity for VLSI,Proc. 11th Annual ACM Symp. on Theory of Computing, 1979, pp. 81–88.
J. Vuillemin, A combinatorial limit to the computing power of VLSI circuits,IEEE Trans. Comput.,32 (1983), 294–300.
N. M. Wigley, G. A. Jullien, On modulus replication for residue arithmetic computations of complex inner products,IEEE Trans. Comput.,39 (1990), 1065–1076.
A. C. Yao, Some complexity questions related to distributive computing,Proc. 11th Annual ACM Symp. on Theory of Computing, 1979, pp. 209–213.
A. C. Yao, The entropic limitations of VLSI computation,Proc. 13th Annual ACM Symp. on Theory of Computing, 1981, pp. 308–311.
Author information
Authors and Affiliations
Additional information
This research was supported in part by NSF Grant CCR-8805978 and AFOSR Grant 87-0-400.
Rights and permissions
About this article
Cite this article
Chu, J.I., Schnitger, G. Communication complexity of matrix computation over finite fields. Math. Systems Theory 28, 215–228 (1995). https://doi.org/10.1007/BF01303056
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01303056