Engineering an Algorithm for the Shortest Even Cycle Problem

Thumbnail Image

Files

master_Karppinen_Eetu_2022.pdf (665.37 KB)

URL

Journal Title

Journal ISSN

Volume Title

Perustieteiden korkeakoulu | Master's thesis
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

2022-12-12

Department

Major/Subject

Computer Science

Mcode

SCI3042

Degree programme

Master’s Programme in Computer, Communication and Information Sciences

Language

en

Pages

79

Series

Abstract

In the shortest even cycle problem, we are given a graph and the goal is to determine the length of a shortest cycle with an even number of vertices. In digraphs, the shortest even cycle problem remained open until 2021 when Björklund, Husfeldt and Kaski published a randomized polynomial time algorithm for the problem. The algorithm is based on algebraic fingerprinting and a well known correspondence between even cycles and the permanent and determinant of an adjacency matrix. To compute the permanent of a matrix in polynomial time the algorithm utilizes a specifically engineered characteristic 4 extension to a characteristic 2 finite field. In this thesis we study the polynomial time algorithm for the shortest even cycle problem in digraphs and the related algebraic structures. Our main contribution is a vectorized and bit sliced parallel implementation of the algorithm. We provide multiple implementations utilizing finite fields of varying size. This thesis includes a description, with pseudocode, of the algorithm and our implementation. Additionally, we discuss ways of performing fast multiplication in the characteristic 4 extension. To this end, we propose three ways of multiplying in Z4[x] and three ways of computing remainders in Z4[x]. Implementations for all of the propositions are provided. All of our implementations are available as open source. We measured the runtime of our implementation using digraphs of varying size and topology. We display the difference in runtime when using different finite fields and the performance gained from vectorization and bit slicing. Additionally, our results show that the runtime of our implementation can be predicted by the number of vertices and edges a digraph has. Considering multiplication in the characteristic 4 extension, we measured the throughput of the proposed ways of implementing multiplication in the extension. Our results show that multiplication in the characteristic 4 extension can be considerably sped up by using more advanced algorithms.

Lyhyimmän syklin ongelmassa annetusta verkosta on tarkoitus löytää lyhyin sykli, jossa on parillinen määrä solmuja. Suunnatuissa verkoissa lyhyimmän syklin ongelma pysyi avoinna vuoteen 2021 asti, kunnes Björklund, Husfeldt ja Kaski julkaisivat polynomisen ajan satunnaisalgoritmin ongelmaan. Kyseinen algoritmi perustuu algebrallisiin sormenjälkiin sekä tunnettuun vastaavuuteen parillisten syklien ja yhteysmatriisien permanenttien ja determinanttien välillä. Matriisien permanenttien laskemiseen polynomisessa ajassa algoritmi käyttää nimenomaisesti suunniteltua karakteristikaa 4 olevaa laajennusta karakteristikaa 2 olevasta äärellisestä kunnasta. Tässä työssä tutkimme polynomisen ajan algoritmia lyhyimmän parillisen syklin ongelmaan suunnatuissa verkoissa ja tähän liittyviä algebrallisia rakenteita. Päätuloksemme on vektorisoitu ja bittiviilletty rinnakkaistoteutus algoritmista. Tuotimme useamman toteutuksen, jotka käyttävät vaihtelevan kokoisia äärellisiä kuntia. Tämä työ sisältää kuvauksen, pseudokoodeineen, algoritmista ja toteutuksestamme. Lisäksi pohdimme tapoja toteuttaa kertolasku karakteristikaa 4 olevassa laajennuksessa. Tätä varten ehdotamme kolme tapaa toteuttaa kertolasku polynomirenkassa Z4[x] ja kolme tapaa laskea jakojäännöksiä polynomirenkaassa Z4[x]. Tuotimme toteutuksen kaikista ehdotuksistamme. Kaikki toteutuksemme ovat saatavilla avoimena lähdekoodina. Mittasimme toteutuksemme ajoaikaa käyttäen eri kokoisia ja topologiaa olevia suunnattuja verkkoja. Vertaamme ajoaikaa eri äärellisiä kuntia käyttävien toteutuksien välillä ja näytämme vektorisoinnista ja bittiviiltelystä saadun suorituskyvyn. Tuloksemme näyttävät, että toteutuksen ajoajan voi ennustaa verkossa olevien solmujen ja linkkien määrästä. Mittasimme myös suorituskykyä kaikille ehdotuksillemme toteuttaa kertolasku karakteristikaa 4 olevassa laajennuksessa. Tuloksemme näyttävät, että kertolaskua karakteristikaa 4 olevassa laajennuksessa voi huomattavasti nopeuttaa käyttämällä kehittyneempiä algoritmeja.

Description

Supervisor

Kaski, Petteri

Thesis advisor

Kaski, Petteri

Keywords

algorithm engineering, algebraic fingerprinting, permanent, finite field, galois ring, bit slicing

Other note

Citation

Permanent link to this item

https://urn.fi/URN:NBN:fi:aalto-202212187112

Collections

[dipl] Perustieteiden korkeakoulu / SCI