Matrix Permanent

Permanent

The permanent of a (square) matrix, like the determinant is a polynomial in the entries of the matrix. Unlike the determinant, the signatures of the permutations are not taken into account making the permanent much more difficult to compute because decomposition methods cannot be used.

The permanent commonly appears in problems related to quantum mechanics, and the most common brute-force combinatorial method has time complexity , thus it is useful to look for more efficient algorithms. The two algorithms considered to be the fastest are one by Ryser (based on the inclusion-exclusion principle), and one by Glynn (based on invariant theory).

This library aims to solve the need for an efficient library that solves the permanent of a given matrix.

Algorithms

permanent.opt()

Compute the permanent of a matrix using the best algorithm for the shape of the given matrix.

Parameters:

• matrix: np.ndarray(M, N, dtype=(np.double|np.complex))

Returns:

• permanent: (np.double|np.complex) - Permanent of matrix.

---

permanent.combinatoric()

Compute the permanent of a matrix combinatorically.

Formula:

\text{per}(A) = \sum_{\sigma \in P(N,M)}{\prod_{i=1}^M{a_{i,{\sigma(i)}}}}

Parameters:

• matrix: np.ndarray(M, N, dtype=(np.double|np.complex))

Returns:

• permanent: (np.double|np.complex) - Permanent of matrix.

---

permanent.glynn()

Formula:

\text{per}(A) = \frac{1}{2^{N-1}} \cdot \sum_{\delta}{
    \left(\sum_{k=1}^N{\delta_k}\right){\prod_{j=1}^N{\sum_{i=1}^N{\delta_i a_{i,j}}}}}

Additional Information: The original formula has been generalized here to work with -by- rectangular permanents with by use of the following identity (shown here for ):

\text{per}\left(\begin{matrix}a_{1,1} & \cdots & a_{1,N} \\ \vdots & \ddots & \vdots \\ a_{M,1} & \cdots & a_{M,N}\end{matrix}\right) = \frac{1}{(M - N + 1)!} \cdot \text{per}\left(\begin{matrix}a_{1,1} & \cdots & a_{1,N} & 1_{1,N+1} & \cdots & 1_{1,M} \\ \vdots & \ddots & \vdots & \vdots & \ddots & \vdots \\ a_{M,1} & \cdots & a_{M,N} & 1_{M,N+1} & \cdots & 1_{M,M}\end{matrix}\right)

This can be neatly fit into the original formula by extending the inner sums over from to :

\text{per}(A) = \frac{1}{2^{N-1}} \cdot \frac{1}{(N - M + 1)!}\cdot \sum_{\delta}{
        \left(\sum_{k=1}^N{\delta_k}\right)
        \prod_{j=1}^N{\left(
            \sum_{i=1}^M{\delta_i a_{i,j}} + \sum_{i=M+1}^N{\delta_i}
        \right)}
    }

Parameters:

• matrix: np.ndarray(M, N, dtype=(np.double|np.complex))

Returns:

• permanent: (np.double|np.complex) - Permanent of matrix.

---

permanent.ryser()

Formula:

\text{per}(A) = \sum_{k=0}^{M-1}{
        {(-1)}^k
        \binom{N - M + k}{k}
        \sum_{\sigma \in P(N,M-k)}{
            \prod_{i=1}^M{
                \sum_{j=1}^{M-k}{a_{i,{\sigma(j)}}}
            }
        }
    }

Parameters:

• matrix: np.ndarray(M, N, dtype=(np.double|np.complex))

Returns:

• permanent: (np.double|np.complex) - Permanent of matrix.

Installation

The permanent package allows you to solve the permanent of a given matrix using the optimal algorithm for your matrix dimensions.

The easiest way to install the permanent package is via PyPI:

   pip install qc-permanent

This will install the package with pre-set parameters with a good performance for most cases. Advanced users can also compile the code locally and fine tune it for their specific architecture. They can either use the pre-defined parameters or fine tune them to their machine.

Setting up your environment

1. Install Python on your machine. Depending on your operating system, the instructions may vary.

2. Install gcc on your machine. Depending on your operating system, the instructions may vary.

3. Create and activate a virtual environment for this project named permanents. One way to do this is with pip.

   pip install virtualenv
   virtualenv permanents
   

4. Activate the virtual environment.

   source permanents/bin/activate
   

5. Install Sphinx and other dependencies.

   pip install sphinx sphinx-rtd-theme sphinx-copybutton
   

6. Install Python dependencies.

   pip install numpy pandas scikit-learn
   

7. (Optional) Install Pytest if you wish to run tests.

   pip install pytest
   

Now that you have your environment set up and activated you are ready to compile the source code into an executable. Here you have two options - compile the code as is with the pre-defined parameters for algorithm swapping, or compile the code with machine specific tuning for algorithm swapping. Note that machine specific tuning will run a series of tests. This will take anywhere from 10 minutes to 1 hour depending on your system.

Option 1: Use given parameters

1. Compile the permanent code (natively for your CPU architecture).

   make BUILD_NATIVE=1
   

   Note: if using M1 architecture, or want a portable build, simply run the following.

   make
   

2. (Optional) Run tests on the algorithms.

   make test
   

3. Compile the website.

   cd docs && make html
   

4. Load the website.

   open build/html/index.html
   

Option 2: Tune parameters

1. Compile the permanent code with the tuning flag.

   make RUN_TUNING=1
   

   Note: it will take some time to run the tuning tests on your machine.

2. (Optional) Run tests on the algorithms.

   make test
   

3. Compile the website.

   cd docs && make html
   

4. Load the website using your web browser.

   <browser> build/html/index.html
   

Notes about the Makefile

The Makefile in this project is used to compile C and Python libraries and includes rules for installation, testing, and cleaning. Here's a breakdown of its sections:

1. Variables:

• CXX, AR, PYTHON: Define compiler, archiver, and Python executable.
• CXXFLAGS: Compiler flags including C++ version, warnings, debugging, optimization, and platform-specific options.

2. Conditional Compilation:

• ifeq ($(shell uname -s),Darwin): Additional flags for macOS.
• ifneq ($(BUILD_NATIVE),): Optimization flags if building for native architecture.
• ifneq ($(RUN_TUNING),): Flag for runtime tuning.
• ifeq ($(PREFIX),): Default installation prefix.

3. Targets:

• all, c, python: Phony targets for building all, C, or Python libraries.
• install: Installs C libraries and headers
• test: Runs tests using pytest.
• clean: Removes generated files.

4. File generation:

• compile_flags.txt: Generates compilation flags for clangd.
• src/tuning.h: Generates tuning parameters header file.

5. Compilation Rules:

• permanent/permanent.so: Compiles Python extension module.
• src/libpermanent.o: Compiles object code.
• libpermanent.a, libpermanent.so: Compiles static and shared C libraries respectively.

License

This code is distributed under the GNU General Public License version 3 (GPLv3). See http://www.gnu.org/licenses/ for more information.

Dependencies

The following programs/libraries are required to compile this package:

• Python (≥3.6)
• gcc (≥11.4)
• Sphinx (≥7.2)
• sphinx-rtd-theme (≥2.0)
• NumPy (≥1.13)
• pandas (≥2.2)
• scikit-learn (≥1.4)
• Pytest (optional: to run tests)