Can I read Fast computation of permanents over $\mathbb{F} 3$ via $\mathbb{F} 2$ arithmetic on EtoBox?

Fast computation of permanents over $\mathbb{F} 3$ via $\mathbb{F} 2$ arithmetic by Scheinerman, Danny is a scholarly article available to read on EtoBox.

What is Fast computation of permanents over $\mathbb{F} 3$ via $\mathbb{F} 2$ arithmetic about?

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$.

Author

Scheinerman, Danny

Published

2024

Language

EN