Probabilistic tensors and opportunistic boolean matrix multiplication
Loading...
Access rights
openAccess
URL
Journal Title
Journal ISSN
Volume Title
A4 Artikkeli konferenssijulkaisussa
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
Authors
Karppa, Matti
Kaski, Petteri
Date
2019-01-01
Department
Major/Subject
Mcode
Degree programme
Language
en
Pages
20
496-515
496-515
Series
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms
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 Õ((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.Description
Keywords
Other note
Citation
Karppa, M & Kaski, P 2019, Probabilistic tensors and opportunistic boolean matrix multiplication . in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms . Society for Industrial and Applied Mathematics, pp. 496-515, ACM-SIAM Symposium on Discrete Algorithms, San Diego, California, United States, 06/01/2019 . < https://epubs.siam.org/doi/abs/10.1137/1.9781611975482.31?mobileUi=0& >