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 $\mathcal{O}(N!N)$, 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 permenent 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 $M$-by-$N$ rectangular permanents with $M \leq N$ by use of the following identity (shown here for $M \geq N$):

$$\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 $\delta$ from $[1,M]$ to $[1,N]$:

$$\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. You can either use the pre-defined parameters or fine tune them to your machine.

Setting up your environment

Install Python on your machine. Depending on your operating system, the instructions may vary.
Install gcc on your machine. Depending on your operating system, the instructions may vary.
Create and activate a virtual environment for this project named permanents. One way to do this is with pip.
```
pip install virtualenv
virtualenv permanents
```
Activate the virtual environment.
```
source permanents/bin/activate
```

Install Sphinx and other dependencies.

pip install sphinx sphinx-rtd-theme sphinx-copybutton

Install Python dependencies.
```
pip install numpy pandas scikit-learn
```
(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

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
```
(Optional) Run tests on the algorithms.
```
make test
```
Compile the website.
```
cd docs && make html
```
Load the website.
```
open build/html/index.html
```

Option 2: Tune parameters

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.
(Optional) Run tests on the algorithms.
```
make test
```
Compile the website.
```
cd docs && make html
```
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:

Variables:

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

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.

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.

File generation:

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

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)

to-do list

I pushed some changes to the michelle branch. It broke the Ryser algorithm, but that's fixable...

Here's what's left to do:

Tuning the function to choose the best algorithm

See run_tuning.c which determines the parameters for the code to choose the best algorithm, and writes them to a header file when run_tuning is executed. We need to work out how we want to determine the best algorithm, and then write the code to determine the appropriate parameters. You can also output some benchmarks into that file, as C comments, which would be useful.
See permanent.c which includes this header if TUNING_FILE is defined. If it's not defined, the parameters are given some default values. When we compile the final C and Python libraries, we define TUNING_FILE using a C compiler flag, e.g. gcc -DTUNING_FILE=1 .... We need to write better default parameters, as well as write proper code in the function opt to choose the best algorithm using the tuning parameters (my code for this is just nonsense).
See also the Makefile to understand how the entire compilation is done.

Support complex type

Use macros to support complex double type. I'll do this if Paul wants.

Cleaning up the code

Can we split up the square and rectangular parts of the Glynn and Ryser algorithms into two shorter functions in permanent.c?
Let's try to make things a bit faster. In C, sizes of things are unsigned (I'm sure you got the size_t lecture for example) so let's do that where possible. And you can use int in most places since the matrices won't have M or N greater than 64.
Clean up the code and comments.
Do something with the stuff in old_tools/.

Writing documentation

Adapt the documentation in old_docs to the Python Sphinx-Doc format in docs.
Make sure version/author/website/etc. fields in setup.py, Makefile, etc. are up to date.

theochem / matrix-permanent Goto Github PK

matrix-permanent's Introduction

Permanent

Algorithms

Installation

Setting up your environment

Option 1: Use given parameters

Option 2: Tune parameters

Notes about the Makefile

License

Dependencies

matrix-permanent's People

Contributors

Stargazers

Watchers

Forkers

matrix-permanent's Issues

Tuning the function to choose the best algorithm

Support complex type

Cleaning up the code

Writing documentation

Recommend Projects

Recommend Topics

Recommend Org

Notes about the `Makefile`