Fast computation of permanents over $\mathbb{F}_3$ via $\mathbb{F}_2$ arithmetic
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _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 |