Probabilistic tensors and opportunistic boolean matrix multiplication

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Standard

Probabilistic tensors and opportunistic boolean matrix multiplication. / Karppa, Matti; Kaski, Petteri.

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 2019. p. 496-515.

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Harvard

Karppa, M & Kaski, P 2019, Probabilistic tensors and opportunistic boolean matrix multiplication. in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, pp. 496-515, ACM-SIAM Symposium on Discrete Algorithms, San Diego, United States, 06/01/2019.

APA

Karppa, M., & Kaski, P. (2019). Probabilistic tensors and opportunistic boolean matrix multiplication. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 496-515). SIAM.

Vancouver

Karppa M, Kaski P. Probabilistic tensors and opportunistic boolean matrix multiplication. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM. 2019. p. 496-515

Author

Karppa, Matti ; Kaski, Petteri. / Probabilistic tensors and opportunistic boolean matrix multiplication. Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 2019. pp. 496-515

Bibtex - Download

@inproceedings{58c8e9e30b354b8393937897dc8b49ee,
title = "Probabilistic tensors and opportunistic boolean matrix multiplication",
abstract = "We introduce probabilistic extensions of classical deterministic measures of algebraic complexity of a tensor, such as the rank and the border rank. We show that these probabilistic extensions satisfy various natural and algorithmically serendipitous properties, such as submultiplicativity under taking of Kronecker products. Furthermore, the probabilistic extensions enable improvements over their deterministic counterparts for specific tensors of interest, starting from the tensor h2, 2, 2i that represents 2 × 2 matrix multiplication. While it is well known that the (deterministic) tensor rank and border rank satisfy rk h2, 2, 2i = 7 and rk h2, 2, 2i = 7 [V. Strassen, Numer. Math. 13 (1969); J. E. Hopcroft and L. R. Kerr, SIAM J. Appl. Math. 20 (1971); S. Winograd, Linear Algebra Appl. 4 (1971); J. M. Landsberg, J. AMS 19 (2006)], we show that the probabilistic tensor rank and border rank satisfy rk e h2, 2, 2i ≤ 6 + 67 and rk e h2, 2, 2i ≤ 6 + 23 . By submultiplicativity, this leads immediately to novel randomized algorithm designs, such as algorithms for Boolean matrix multiplication as well as detecting and estimating the number of triangles in graphs. Our algorithms are opportunistic in the sense that their worst-case scaling is essentially governed by the probabilistic rank, yet their result is accumulated through independent repetitions, where the partial result can be inspected at each repeat for possible early termination, and each repeat scales according to the rank of the outcome-tensors. For example, representing h2, 2, 2i probabilistically using an ensemble of tensors of rank 6, we obtain an algorithm that, with high probability, multiplies two 2d × 2d Boolean matrices in {\~O}((6 + 67 )d) operations. This algorithm consists of independent repeats that each run in O(6d) operations and enable inspection of the partial result at each repeat. Analogously, a probabilistic representation of h2, 2, 2i using tensors of border rank 5 gives an algorithm that runs in {\~O}((6 + 23 )d) operations, consisting of repeats that run in {\~O}(5d) operations each. Asymptotically, we use Adleman’s argument to show that, over the complex field, the support rank exponent ωs of matrix multiplication [H. Cohn and C. Umans, SODA’12] gives the lower bound ωs ≤ inf τ : rk e ht, t, ti = O(tτ ) for probabilistic tensor rank. While this enables an approach to obtaining asymptotically faster algorithm designs for matrix multiplication via the Cohn-Umans inequality ω ≤ 32 ωs − 1, the main motivation for the present paper is to enable an approach towards fast practical algorithms using small probabilistic tensors.",
author = "Matti Karppa and Petteri Kaski",
year = "2019",
month = "1",
day = "1",
language = "English",
pages = "496--515",
booktitle = "Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms",
publisher = "SIAM",

}

RIS - Download

TY - GEN

T1 - Probabilistic tensors and opportunistic boolean matrix multiplication

AU - Karppa, Matti

AU - Kaski, Petteri

PY - 2019/1/1

Y1 - 2019/1/1

N2 - We introduce probabilistic extensions of classical deterministic measures of algebraic complexity of a tensor, such as the rank and the border rank. We show that these probabilistic extensions satisfy various natural and algorithmically serendipitous properties, such as submultiplicativity under taking of Kronecker products. Furthermore, the probabilistic extensions enable improvements over their deterministic counterparts for specific tensors of interest, starting from the tensor h2, 2, 2i that represents 2 × 2 matrix multiplication. While it is well known that the (deterministic) tensor rank and border rank satisfy rk h2, 2, 2i = 7 and rk h2, 2, 2i = 7 [V. Strassen, Numer. Math. 13 (1969); J. E. Hopcroft and L. R. Kerr, SIAM J. Appl. Math. 20 (1971); S. Winograd, Linear Algebra Appl. 4 (1971); J. M. Landsberg, J. AMS 19 (2006)], we show that the probabilistic tensor rank and border rank satisfy rk e h2, 2, 2i ≤ 6 + 67 and rk e h2, 2, 2i ≤ 6 + 23 . By submultiplicativity, this leads immediately to novel randomized algorithm designs, such as algorithms for Boolean matrix multiplication as well as detecting and estimating the number of triangles in graphs. Our algorithms are opportunistic in the sense that their worst-case scaling is essentially governed by the probabilistic rank, yet their result is accumulated through independent repetitions, where the partial result can be inspected at each repeat for possible early termination, and each repeat scales according to the rank of the outcome-tensors. For example, representing h2, 2, 2i probabilistically using an ensemble of tensors of rank 6, we obtain an algorithm that, with high probability, multiplies two 2d × 2d Boolean matrices in Õ((6 + 67 )d) operations. This algorithm consists of independent repeats that each run in O(6d) operations and enable inspection of the partial result at each repeat. Analogously, a probabilistic representation of h2, 2, 2i using tensors of border rank 5 gives an algorithm that runs in Õ((6 + 23 )d) operations, consisting of repeats that run in Õ(5d) operations each. Asymptotically, we use Adleman’s argument to show that, over the complex field, the support rank exponent ωs of matrix multiplication [H. Cohn and C. Umans, SODA’12] gives the lower bound ωs ≤ inf τ : rk e ht, t, ti = O(tτ ) for probabilistic tensor rank. While this enables an approach to obtaining asymptotically faster algorithm designs for matrix multiplication via the Cohn-Umans inequality ω ≤ 32 ωs − 1, the main motivation for the present paper is to enable an approach towards fast practical algorithms using small probabilistic tensors.

AB - We introduce probabilistic extensions of classical deterministic measures of algebraic complexity of a tensor, such as the rank and the border rank. We show that these probabilistic extensions satisfy various natural and algorithmically serendipitous properties, such as submultiplicativity under taking of Kronecker products. Furthermore, the probabilistic extensions enable improvements over their deterministic counterparts for specific tensors of interest, starting from the tensor h2, 2, 2i that represents 2 × 2 matrix multiplication. While it is well known that the (deterministic) tensor rank and border rank satisfy rk h2, 2, 2i = 7 and rk h2, 2, 2i = 7 [V. Strassen, Numer. Math. 13 (1969); J. E. Hopcroft and L. R. Kerr, SIAM J. Appl. Math. 20 (1971); S. Winograd, Linear Algebra Appl. 4 (1971); J. M. Landsberg, J. AMS 19 (2006)], we show that the probabilistic tensor rank and border rank satisfy rk e h2, 2, 2i ≤ 6 + 67 and rk e h2, 2, 2i ≤ 6 + 23 . By submultiplicativity, this leads immediately to novel randomized algorithm designs, such as algorithms for Boolean matrix multiplication as well as detecting and estimating the number of triangles in graphs. Our algorithms are opportunistic in the sense that their worst-case scaling is essentially governed by the probabilistic rank, yet their result is accumulated through independent repetitions, where the partial result can be inspected at each repeat for possible early termination, and each repeat scales according to the rank of the outcome-tensors. For example, representing h2, 2, 2i probabilistically using an ensemble of tensors of rank 6, we obtain an algorithm that, with high probability, multiplies two 2d × 2d Boolean matrices in Õ((6 + 67 )d) operations. This algorithm consists of independent repeats that each run in O(6d) operations and enable inspection of the partial result at each repeat. Analogously, a probabilistic representation of h2, 2, 2i using tensors of border rank 5 gives an algorithm that runs in Õ((6 + 23 )d) operations, consisting of repeats that run in Õ(5d) operations each. Asymptotically, we use Adleman’s argument to show that, over the complex field, the support rank exponent ωs of matrix multiplication [H. Cohn and C. Umans, SODA’12] gives the lower bound ωs ≤ inf τ : rk e ht, t, ti = O(tτ ) for probabilistic tensor rank. While this enables an approach to obtaining asymptotically faster algorithm designs for matrix multiplication via the Cohn-Umans inequality ω ≤ 32 ωs − 1, the main motivation for the present paper is to enable an approach towards fast practical algorithms using small probabilistic tensors.

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

M3 - Conference contribution

SP - 496

EP - 515

BT - Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms

PB - SIAM

ER -

ID: 35174144