On Bilinear Techniques for Similarity Search and Boolean Matrix Multiplication
Loading...
URL
Journal Title
Journal ISSN
Volume Title
School of Science |
Doctoral thesis (article-based)
| Defence date: 2020-01-24
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.
Authors
Date
Major/Subject
Mcode
Degree programme
Language
en
Pages
126 + app. 147
Series
Aalto University publication series DOCTORAL DISSERTATIONS, 9/2020
Abstract
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.Tässä väitöskirjassa esitetään tutkimustuloksia useilta algoritmiikan eri osa-alueilta. Näitä tuloksia yhdistävät bilineaaritekniikoiden soveltaminen. Funktiot, jotka kuvaavat alkioita vektoriavaruuspareilta kolmansille vektoriavaruuksille siten, että ne ovat lineaarisia argumenttiensa suhteen, eli bilineaarikuvaukset, ovat läsnä kaikkialla ja keskeisiä matemaattisia työkaluja. Kanoninen esimerkki bilineaarikuvauksesta on matriisikertolasku. Tässä työssä käsitellään sekä sovelluksia, jotka hyödyntävät bilineaarikuvauksia että bilineaarikuvauksien itsensä laskemista, erityisesti Boolen matriisikertolaskun tapauksessa. Samankaltaisuushaun osalta parannetaan Valiantin satunnaistettua korreloituneiden vektoreiden hakualgoritmia [FOCS 2012; J. ACM 2015] (i) esittämällä parannetun näytteistysjärjestelyn, joka mahdollistaa nopeamman käsittelyn nopean matriisikertolaskun avulla ja (ii) poistamalla Valiantin algoritmin satunnaisuuden. Nämä tulokset ovat lähinnä teoreettisia, koska ne nojaavat nopeaan matriisikertolaskuun. Työssä esitetään myös (iii) adaptiivinen prefiksinsijoitusmenetelmä symmetrian särkemiseen. Kyseessä on McKayn kanonisen laajennuksen menetelmän [J. Algorithms 1998] sovellus, joka tuottaa joukon osittaissijoituksia rajoitejärjestelmän muuttujaprefiksisekvenssin suhteen siten, että kaikki generoidut sijoitukset ovat pareittain epäisomorfisia. Menetelmä särkee symmetriat täydellisesti prefiksisekvenssin suhteen ja pystyy hyödyntämään väritetyn graafin muodossa annetusta symmetrioiden apuesityksestä. Menetelmästä on tehty myös implementaatio, joka toimii Boolen toteutuvuusratkaisijoiden esikäsittelijänä, ja työssä osoitetaan kokeellisesti, että menetelmä on sovellettavissa käytännössä ja rinnakkaistuu hyvin hajautetussa laskentaklusterissa. Työssä käsitellään matriisikertolaskua (iv) esittelemällä probabilistinen laajennus rankin ja border rankin käsitteille ja osoittamalla, että 2×2-matriisikertolaskutensorilla on aidosti pienempi probabilistinen rank ja border rank kuin deterministinen rank. Tämän tiedon avulla johdetaan kahden Boolen matriisin kertolaskuun satunnaistettu algoritmi, joka on asymptoottisesti nopeampi kuin Strassenin algoritmi [Numer. Math. 1969]. Lopuksi (v) hyödyntämällä Karstadtin ja Schwartzin tulosta [SPAA 2017] työssä implementoidaan Strassenin kertolasku binäärikunnan yli vaihtoehtoisessa kannassa usean GPU:n jaetun muistin järjestelmässä. Implementaation toimintaa arvioidaan yhden tebibitin syötteellä ja osoitetaan kokeellisesti, että se ylittää naiivin algoritmin teoreettisen huippusuorituskyvyn bittioperaatioiden suhteen ja tarjoaa myös merkittäviä säästöjä energiankulutuksen suhteen.Description
Supervising professor
Kaski, Petteri, Prof., Aalto University, Department of Computer Science, FinlandOther note
Parts
-
[Publication 1]: Matti Karppa, Petteri Kaski, and Jukka Kohonen. A Faster Subquadratic Algorithm for Finding Outlier Correlations. ACM Transactions on Algorithms, 14(3), Article 31, June 2018. Preliminary version published in ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, 1288–1305, January 2016.
DOI: 10.1145/3174804 View at publisher
- [Publication 2]: Matti Karppa, Petteri Kaski, Jukka Kohonen, and Padraig O Cathain. Explicit correlation amplifiers for finding outlier correlations in deterministic subquadratic time. Submitted for publication. Preliminary version published in European Symposium on Algorithms, ESA 2016, Article No. 52, 2016.
- [Publication 3]: Tommi Junttila, Matti Karppa, Petteri Kaski, and Jukka Kohonen. An adaptive prefix-assignment technique for symmetry reduction. Accepted for publication in Journal of Symbolic Computation, January 2019. Preliminary version published in International Conference on Theory and Applications of Satisfiability Testing, SAT 2017, 101–118, August 2017.
-
[Publication 4]: Matti Karppa, and Petteri Kaski. Probabilistic tensors and opportunistic Boolean matrix multiplication. In ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, 496–515, January 2019.
Full text in Acris/Aaltodoc: http://urn.fi/URN:NBN:fi:aalto-202002122143DOI: 10.1137/1.9781611975482.31 View at publisher
- [Publication 5]: Matti Karppa, and Petteri Kaski. Engineering Boolean matrix multiplication for multiple-accelerator shared-memory architectures. Submitted for publication.
- [Errata file]: Errata Matti Karppa DD-9/2020 Publication P1