Closed mlxd closed 3 years ago
Sorta done with adding BBFG support, I think. However, as I've changed the list of requirements just a bit, I'll review what's been done this evening:
./include/permanent.hpp
. perm_BBFG_qp
and perm_BBFG_cmplx
) and one for the future parallel vs. serial integration (perm_BBFG
)../tests/libwalrus_unittest.cpp
./thewalrus/libwalrus.pyx
:
T perm_BBFG[T](vector[T] &mat)
double perm_BBFG_qp(vector[double] &mat)
double complex perm_BBFG_cmplx(vector[double complex] &mat)
./thewalrus/tests/test_permanent.py
for integrated python methods naming perm_BBFG_real
and perm_BBFG_complex
.My script to test changes before commit:
make clean && \
pip install -e . && \
make test-cpp && \
make test
Please, let me know if the list of changes cover all concerns within this issue.
Hi @maliasadi sounds good. Feel free to open a PR with your changes. The team can review and discuss in there.
Feel free to open a PR with your changes. The team can review and discuss in there.
Sorry for the late reply @mlxd. I was looking for some time to optimize my code and implement the parallel version (that's not done yet!) before making a PR. I collected some promising benchmarks comparing my two versions of BBFG formula with the Ryser's one. I'll open a PR and continue the conversation there.
Issue description
Currently, The Walrus uses the Ryser formula to calculate permanents of arbitrary matrices (https://en.wikipedia.org/wiki/Computing_the_permanent#Ryser_formula). Another useful algorithm to calculate permanents is the Balasubramanian–Bax–Franklin–Glynn (BBFG) formula (https://en.wikipedia.org/wiki/Computing_the_permanent#Balasubramanian%E2%80%93Bax%E2%80%93Franklin%E2%80%93Glynn_formula). Having both methods implemented will allow for performance and accuracy comparisons and trade-offs.
Required tasks:
./include
directory (see existing implementation)/tests
directorysetup.py
,/include/libwalrus.hpp
and/include/libwalrus.pyx
)