Bulk-synchronous parallel multiplication of boolean matrices

1. A. Aggarwal, A. K. Chandra, and M. Snir. Communication complexity of PRAMs. Theoretical Computer Science, 71:3–28, 1990.

   Article  MATH  MathSciNet  Google Scholar 

2. A. V. Aho, J. E. Hopcroft, and J. D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, 1976.

   Google Scholar 

3. N. Alon et al. The algorithmic aspects of the regularity lemma. Journal of Algorithms, 16:80–109, 1994.

   Article  MATH  MathSciNet  Google Scholar 

4. J. Basch, S. Khanna, and R. Motwani. On diameter verification and Boolean matrix multiplication. Technical Report STAN-CS-95-1544, Department of Computer Science, Stanford University, 1995.

   Google Scholar 

5. B. Bollobás. Extremal Graph Theory. Academic Press, 1978.

   Google Scholar 

6. Yu. D. Burago and V. A. Zalgaller. Geometric Inequalities. Number 285 in Grundl. der math. Wissenschaften. Springer-Verlag, 1988.

   Google Scholar 

7. D. Coppersmith and S. Winograd. Matrix multiplication via arithmetic progressions. Journal of Symbolic Computation, 9(3):251–280, March 1990.

   MATH  MathSciNet  Google Scholar 

8. T. H. Cormen, C. E. Leiserson, and R. L. Rivest. Introduction to Algorithms. The MIT Electrical Engineering and Computer Science Series. The MIT Press and McGraw-Hill, 1990.

   Google Scholar 

9. H. Hadwiger. Vorlesungen über Inhalt, Oberfläche und Isoperimetrie. Number 93 in Grundl. der math. Wissenschaften. Springer-Verlag, 1957.

   Google Scholar 

10. J. E. Hopcroft and L. R. Kerr. On minimizing the number of multiplications necessary for matrix multiplication. SI AM Journal of Applied Mathematics, 20(1):30–36, January 1971.

    Article  MATH  MathSciNet  Google Scholar 

11. J. Komlós and M. Simonovits. Szemerédi's Regularity Lemma and its applications in graph theory. Technical Report 96-10, DIMACS, 1996.

    Google Scholar 

12. L. H. Loomis and H. Whitney. An inequality related to the isoperimetrie inequality. Bull. Amer. Math. Soc, 55:961–962, 1949.

    Article  MATH  MathSciNet  Google Scholar 

13. W. F. McColl. General purpose parallel computing. In A. Gibbons and P. Spirakis, editors, Lectures on parallel computation, volume 4 of Cambridge International Series on Parallel Computation, chapter 13, pages 337–391. Cambridge University Press, 1993.

    Google Scholar 

14. W. F. McColl. Scalable computing. In J. van Leeuwen, editor, Computer Science Today: Recent Trends and Developments, volume 1000 of Lecture Notes in Computer Science, pages 46–61. Springer-Verlag, 1995.

    Google Scholar 

15. W. F. McColl. A BSP realisation of Strassen's algorithm. In M. Kara, J. R. Davy, D. Goodeve, and J. Nash, editors, Abstract Machine Models for Parallel and Distributed Computing. IOS Press, 1996.

    Google Scholar 

16. W. F. McColl. Universal computing. In L. Bougé, P. Fraigniaud, A. Mignotte, and Y. Robert, editors, Proceedings of Euro-Par'96-I, volume 1123 of Lecture Notes in Computer Science, pages 25–36. Springer-Verlag, 1996.

    Google Scholar 

17. M. S. Paterson. Complexity of product and closure algorithms for matrices. In Proceedings of the International Congress of Mathematicians, pages 483–489, 1974.

    Google Scholar 

18. M. S. Paterson. Private communication, 1993.

    Google Scholar 

19. L. G. Valiant. A bridging model for parallel computation. Communications of the ACM, 33(8):103–111, August 1990.

    Article  Google Scholar 

20. L. G. Valiant. General purpose parallel architectures. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science, chapter 18, pages 943–971. Elsevier, 1990.

    Google Scholar 

Download references