On Bilinear Techniques for Similarity Search and Boolean Matrix Multiplication

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.