Standard

Bulk-synchronous parallel multiplication of Boolean matrices. / Tiskin, A.

Automata, Languages and Programming (ICALP 1998). 1998. p. 494-506 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1443).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review

Harvard

Tiskin, A 1998, Bulk-synchronous parallel multiplication of Boolean matrices. in Automata, Languages and Programming (ICALP 1998). Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1443, pp. 494-506. https://doi.org/10.1007/bfb0055078

APA

Tiskin, A. (1998). Bulk-synchronous parallel multiplication of Boolean matrices. In Automata, Languages and Programming (ICALP 1998) (pp. 494-506). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1443). https://doi.org/10.1007/bfb0055078

Vancouver

Tiskin A. Bulk-synchronous parallel multiplication of Boolean matrices. In Automata, Languages and Programming (ICALP 1998). 1998. p. 494-506. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/bfb0055078

Author

Tiskin, A. / Bulk-synchronous parallel multiplication of Boolean matrices. Automata, Languages and Programming (ICALP 1998). 1998. pp. 494-506 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@inproceedings{87b4dd1a6cee4f4c84a3d47dc92efb81,
title = "Bulk-synchronous parallel multiplication of Boolean matrices",
abstract = "The model of bulk-synchronous parallel (BSP) computation is an emerging paradigm of general-purpose parallel computing. We study the BSP complexity of subcubic algorithms for Boolean matrix multiplication. The communication cost of a standard Strassen-type algorithm is known to be optimal for general matrices. A natural question is whether it remains optimal when the problem is restricted to Boolean matrices. We give a negative answer to this question, by showing how to achieve a lower asymptotic communication cost for Boolean matrix multiplication. The proof uses a deep result from extremal graph theory, known as Szemer{\'e}di's Regularity Lemma. Despite its theoretical interest, the algorithm is not practical, because it works only on astronomically large matrices and involves huge constant factors.",
author = "A. Tiskin",
year = "1998",
month = jan,
day = "1",
doi = "10.1007/bfb0055078",
language = "English",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Nature",
pages = "494--506",
booktitle = "Automata, Languages and Programming (ICALP 1998)",

}

RIS

TY - GEN

T1 - Bulk-synchronous parallel multiplication of Boolean matrices

AU - Tiskin, A.

PY - 1998/1/1

Y1 - 1998/1/1

N2 - The model of bulk-synchronous parallel (BSP) computation is an emerging paradigm of general-purpose parallel computing. We study the BSP complexity of subcubic algorithms for Boolean matrix multiplication. The communication cost of a standard Strassen-type algorithm is known to be optimal for general matrices. A natural question is whether it remains optimal when the problem is restricted to Boolean matrices. We give a negative answer to this question, by showing how to achieve a lower asymptotic communication cost for Boolean matrix multiplication. The proof uses a deep result from extremal graph theory, known as Szemerédi's Regularity Lemma. Despite its theoretical interest, the algorithm is not practical, because it works only on astronomically large matrices and involves huge constant factors.

AB - The model of bulk-synchronous parallel (BSP) computation is an emerging paradigm of general-purpose parallel computing. We study the BSP complexity of subcubic algorithms for Boolean matrix multiplication. The communication cost of a standard Strassen-type algorithm is known to be optimal for general matrices. A natural question is whether it remains optimal when the problem is restricted to Boolean matrices. We give a negative answer to this question, by showing how to achieve a lower asymptotic communication cost for Boolean matrix multiplication. The proof uses a deep result from extremal graph theory, known as Szemerédi's Regularity Lemma. Despite its theoretical interest, the algorithm is not practical, because it works only on astronomically large matrices and involves huge constant factors.

UR - http://www.scopus.com/inward/record.url?scp=22044455697&partnerID=8YFLogxK

U2 - 10.1007/bfb0055078

DO - 10.1007/bfb0055078

M3 - Conference contribution

AN - SCOPUS:22044455697

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 494

EP - 506

BT - Automata, Languages and Programming (ICALP 1998)

ER -

ID: 127758693