Fast practical algorithms for the Boolean-product-witness-matrix problem

ABSTRACT

Given two n × n Boolean matrices A and B, their Boolean Product Witness Matrix (BPWM) is an n × n integer matrix W with wij = some k such that aik = bkj = 1, (1 ≤ i, j, k ≤ n) and wij = 0 if no such k exists. The best known algorithms to date for solving the BPWM problem have a worst-case complexity of O(n&ohgr; log n), where O(n&ohgr;) is the time required to multiply two n × n integer matrices. The theoretically best known value of &ohgr; is 2.376, but is higher for algorithms that are practical to implement for reasonable problem sizes. In this paper, we present a relatively simple and practical randomized algorithm for solving the BPWM problem. The expected completion time of our algorithms is O(n2 log n) for a large class of Boolean matrices, including but not limited to all mutually-independent matrices. We show that the probability of the algorithm requiring more than O(n2 log n) is vanishingly small for most input Boolean matrices, irrespective of the density of 1's or 0's in them.

REFERENCES

• 1: K. Abrahamson. A time-space tradeoff for Boolean matrix multiplication. In Proceedings of 30th Annual Symposium on Foundations of Computer Science, pages 412-419, 1990.
• 2: L. Adleman, K. Booth, F. Preprata, and W. Ruzzo. Improved time and space bounds for Boolean matrix multiplication. Acta Informatica Complexity, 11:61-75, 1978.
• 3: N. Alon, Z. Galil, O. Margalit, and M. Naor. Witnesses for Boolean matrix multiplication and for shortest paths. In Proceedings of 32nd Annual Symposium on Foundations of Computer Science, pages 417-426, 1992.
• 4: N. Alon and M. Naor. Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions. Algorithmica, 16:434-449, 1996.
• 5: M. D. Atkinson , N. Santoro, A practical algorithm for Boolean matrix multiplication, Information Processing Letters, v.29 n.1, p.37-38, Sept. 15, 1988 [doi>10.1016/0020-0190(88)90130-5]
• 6: H. Chernoff. A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. Annals of Mathematical Statistics, 23:493-509, 1952.
• 7: E. Chu, A. George, J. W.-H. Liu, and E. G.-Y. Ng. Users guide for SPARSPAK-A: Waterloo sparse linear equations package. Technical Report CS-84-36, University of Waterloo, Waterloo, IA, 1984.
• 8: Edith Cohen , David D. Lewis, Approximating matrix multiplication for pattern recognition tasks, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.682-691, January 05-07, 1997, New Orleans, Louisiana, United States
• 9: Don Coppersmith , Shmuel Winograd, Matrix multiplication via arithmetic progressions, Journal of Symbolic Computation, v.9 n.3, p.251-280, March 1990 [doi>10.1016/S0747-7171(08)80013-2]
• 10: Zvi Galil , Oded Margalit, Witnesses for Boolean matrix multiplication and for transitive closure, Journal of Complexity, v.9 n.2, p.201-221, June 1993 [doi>10.1006/jcom.1993.1014]
• 11: A. Gupta, P. Rohatgi, and R. Agarwal. Fast practical algorithms for the Boolean-product-witness-matrix problem. Technical Report RC 21224 (94793), IBM T. J. Watson Research Center, Yorktown Heights, NY, July 1998. (Available at ftp ://ftp. cs. umn. edu/users/kumar f anshul fbmm.ps) .
• 12: C. A. R. Hoare. Quicksort. Computer Journal, 5(1):10 15, 1962.
• 13: W. Hoeffding. Probability inequalities for sums of bounded random variables. American Statistical Association Journal, 58:13-30, 1963.
• 14: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 15: P. E. O'Neil and E. J. O'Neil. A fast expected time algorithm for Boolean matrix multiplication and transitive closure. Information and Control, 22:132-138, 1973.
• 16: Alessandro Panconesi , Aravind Srinivasan, Fast randomized algorithms for distributed edge coloring, Proceedings of the eleventh annual ACM symposium on Principles of distributed computing, p.251-262, August 10-12, 1992, Vancouver, British Columbia, Canada [doi>10.1145/135419.135465]
• 17: Raimund Seidel, On the all-pairs-shortest-path problem, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.745-749, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129784]
• 18: J. Vyskoc. A note on Boolean matrix multiplication. Information Processing Letters, 19:249-251, September 1984.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Algebraic algorithms

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on matrices

General Terms:
Algorithms, Performance, Theory, Verification