Fast computation of permanents over $\mathbb{F}_3$ via $\mathbb{F}_2$ arithmetic
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911976688451584 |
|---|---|
| author | Scheinerman, Danny |
| author_facet | Scheinerman, Danny |
| contents | We present a method of representing an element of $\mathbb{F}_3^n$ as an element of $\mathbb{F}_n^2 \times \mathbb{F}_n^2$ which in practice will be a pair of unsigned integers. We show how to do addition, subtraction and pointwise multiplication and division of such vectors quickly using primitive binary operations (and, or, xor). We use this machinery to develop a fast algorithm for computing the permanent of a matrix in $\mathbb{F}_3^{n\times n}$. We present Julia code for a natural implementation of the permanent and show that our improved implementation gives, roughly, a factor of 80 speedup for problems of practical size. Using this improved code, we perform Monte Carlo simulations that suggest that the distribution of $\mbox{perm}(A)$ tends to the uniform distribution as $n \to \infty$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_20205 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Fast computation of permanents over $\mathbb{F}_3$ via $\mathbb{F}_2$ arithmetic Scheinerman, Danny Data Structures and Algorithms Combinatorics We present a method of representing an element of $\mathbb{F}_3^n$ as an element of $\mathbb{F}_n^2 \times \mathbb{F}_n^2$ which in practice will be a pair of unsigned integers. We show how to do addition, subtraction and pointwise multiplication and division of such vectors quickly using primitive binary operations (and, or, xor). We use this machinery to develop a fast algorithm for computing the permanent of a matrix in $\mathbb{F}_3^{n\times n}$. We present Julia code for a natural implementation of the permanent and show that our improved implementation gives, roughly, a factor of 80 speedup for problems of practical size. Using this improved code, we perform Monte Carlo simulations that suggest that the distribution of $\mbox{perm}(A)$ tends to the uniform distribution as $n \to \infty$. |
| title | Fast computation of permanents over $\mathbb{F}_3$ via $\mathbb{F}_2$ arithmetic |
| topic | Data Structures and Algorithms Combinatorics |
| url | https://arxiv.org/abs/2407.20205 |