Algorithms are the art of efficient computation: it is by the power of algorithms that solving problems becomes feasible, and that we may harness the power of computing machinery. Efficient algorithms translate directly to savings in resources, such as time, storage space, and electricity, and thus money. With the end of the exponential increase in the computational power of hardware, the value of efficient algorithms may be greater than ever. This thesis presents advancements in multiple fields of algorithms, related through the application of bilinear techniques. Functions that map elements from a pair of vector spaces to a third vector space with the property that they are linear in their arguments, or bilinear maps, are a ubiquitous and fundamental mathematical tool, the canonical example being the matrix multiplication. We address both the applications that make use of bilinear maps and the computation of the bilinear maps itself, Boolean matrix multiplication in particular. In the field of similarity search, we improve on Valiant's randomized algorithm [FOCS 2012; J. ACM 2015] for finding correlated vectors by (i) presenting an improved sampling scheme that enables faster processing by using fast matrix multiplication, and (ii) derandomizing Valiant's algorithm. These results are mostly of theoretical nature since they rely on fast matrix multiplication. We also present (iii) an adaptive prefix-assignment method for symmetry breaking. An instantiation of McKay's canonical extension framework [J. Algorithms 1998], the method produces a set of partial assignments with respect to a sequence of a prefix of variables in a system of constraints, such that all generated assignments are pairwise nonisomorphic. The method breaks the symmetries completely with respect to the prefix sequence, and can benefit from an auxiliary representation of symmetries in the form of a colored graph. We also provide an implementation that works as a preprocessor for Boolean satisfiability solvers, and show experimentally that the method is also of practical value and parallelizes well in a distributed computer cluster setting.We address matrix multiplication by (iv) introducing a probabilistic extension of the notions of rank and border rank, and show that, under this notion, the structural tensor for 2×2 matrix multiplication has strictly lower probabilistic tensor rank and border rank than the deterministic rank. We use this fact to derive a randomized algorithm for multiplying two Boolean matrices that is asymptotically faster than Strassen's algorithm [Numer. Math. 1969]. Finally, (v) using the recent result of Karstadt and Schwartz [SPAA 2017], we implement Strassen's multiplication over the binary field in an alternative basis for a multiple-GPU shared-memory system. We evaluate the implementation with one-tebibit input, and show that it exceeds the theoretical peak performance of the elementary algorithm in terms of bit operations, and also offers substantial savings in energy consumption.
|Translated title of the contribution||On Bilinear Techniques for Similarity Search and Boolean Matrix Multiplication|
|Publication status||Published - 2020|
|MoE publication type||G5 Doctoral dissertation (article)|
- bilinear algorithms
- matrix multiplication
- similarity search
- symmetry breaking