Tag Line

PolyBoRi was created by man. There are two developers. And they have a plan.“

Saturday, July 20, 2013

GSOC 2013 project progress for weeks 0-4

I am Ioana Tamas, and this is a summary of the weekly updates of my GSOC 2013 project for Polybori.
Hopefully, the next updates will be posted in separate blog posts. My repository is: http://sourceforge.net/p/libzdd/code.

Weeks 0 &1:

I have been allocating a lot of time to learning how to work with big code bases etc., so the progress may not be very outstanding. Also, I figured that I will not be able to follow the proposed timeline, one example being the fact that updating the reference and memory allocation methods can't be done without updating the main classes and structures at the same time (which appear as later milestones).

Now, a summary of the code I have written until now:

1) I began the ZDD class, which will contain all the members and methods of the Cudd ZDD class, plus the ones inherited from Cudd classes that are of no use for Polybori (they were implemented in Cudd for handling more types of decision diagrams).

2) I started writing the structures needed for the completeness of the class definition, though I have not decided yet if I should rather have classes instead of structures. I also removed the structure members that are not useful for our purpose.

3) I have set up testing files, but I didn't include meaningful unit tests yet.

4) I added the Cudd code base in my directory, and I will gradually delete the files that are not useful until there is no Cudd left.

5) I made a namespace "libzdd" to avoid name coincidences. However, the way I did this may cause problems when I need Cudd files.

To finalize and summarize, the things I still have issues with would be:
- constructing the library using SCons, so that it accepts the boost unit test framework and takes into consideration the Cudd files
- correctly using the namespace
- choosing meaningful unit tests


During the past week, I started transforming the Cudd's structs into classes and further working on my main source and header file. After revising the timeline a little bit, I decided that I should take a break from what I started (so I temporarily commented a great part of my code) in order to work more on actually providing something that can be tested, using some temporary definitions. This part is still in progress.


The past week I temporarily kept only my Zero-Suppressed Decision Diagram class definition, using typedefs for the other relevant classes at the moment. This way, I was able to set up some boost tests and (more difficult than I expected) passing them. They test the things implemented until now, which are the constructors and some operators.

I also changed the structure of the repository, by making nice and clean header and source files for everything that I use currently use.

I also deleted a few things that I had introduced too early, but they will come back at the right time (they are saved somewhere in my computer for now).


This week, I made some significant progress in making the zdd_ZDD class (my project's main class) avoid using raw pointers, by wrapping the access to the Diagram Manager for all the constructors and operators.

In order to achieve this, I made use of boost shared pointers, and I introduced a new class.

I also introduced a unique table, with its own class (that will soon totally replace Cudd's), using boost tuples and std maps.

Tuesday, June 4, 2013

GSOC 2013 project for Polybori

I am Ioana-Maria Tamas and for this year's Google Summer of code, I will be working for lmonade's project: "Binary decision diagrams for Boolean polynomial rings". The main details of the project are the ones  below, but small modifications may occur.

  • Abstract

Zero-suppressed binary decision diagrams are used by Polybori for efficiently representing Boolean polynomials. At the moment, they are manipulated via CUDD, which is not specialized on this type of diagrams and only uses C in the implementation. The goal of the project is implementing an independent library in C++, that is specialized on  zero-suppressed binary decision diagrams.

  • Objective

There are no major problems in the current method used to deal with decision diagrams, but implementing the new library will definitely increase Polybori’s usability and efficiency. The things that will be reimplemented are the reference counting, the caching management, the diagram manager and then the operators and methods from the decision diagram class.

  • Deliverables

The final product will be a well-documented, well-tested and easy to build library, that will help Polybori manipulate Boolean Polynomials without using CUDD in the background, and in a more efficient and specialized way.

  • Timeline

    Time Frame
    17 June - 24 June
    Prepare unit tests for a wrapper class that works with CUDD in the background
    25 June - 5 July
    Implement a C++ reference counting method
    6 July - 11 July
    Add the new method to the wrapper and test
    12 July - 26 July
    Implement a C++ cache management method
    27 July - 2 August
    Add the new method to the wrapper and test
    Prepare for midterm evaluation
    3 August - 16 August
    Re-implement the DdManager, DdNode and DdChild and test them
    17 August - 31 August
    Implement a C++ ZDD class, with all the operations and methods available in CUDD
    1 September - 9 September
    Write unit tests that are independent from CUDD
    10 September - 15 September
    Optional: Make an independent C++ library using the new implementations (with a proper build system)
    Test everything without CUDD
    16 September - 23 September
    Finalize documentation
    Prepare for final evaluation

Wednesday, April 10, 2013

Release of PolyBoRi 0.8.3

Already some time ago we had released PolyBoRi 0.8.3 at
Among minor fixes it improves the support of multiple Python installations, comes with consistent library version naming, and easier updating of libm4ri. Binary packages for OpenSuse, Fedora, and Ubuntu are available at the usual place. Updated ebuild scripts for lmona.de and Gentoo-prefix as well as spkg packages for Sage will be available soon. Binary packages are available for recent OpenSuSE, and Fedora as well as Ubuntu distributions. Just point your package manager here:  

Updated ebuild scripts for lmona.de and Gentoo-prefix a will be available soon. 

Now, the updated spkg packages for Sage will be included in the next release. 

My best,

Monday, July 9, 2012

PolyBoRi's Bug-fixing Release 0.8.2

We just released PolyBoRi 0.8.2 at
This is a bug-fixing release incorporating various patches contributed by the Sage community , lmonade, and the participants of the ELAGB workshop here in Kaiserslautern.This includes the following issues and features:
  • Dependencies of optional rpm package gui fixed
  • Fixed bug which prevented self-testing of polybori.plot
  • Build systems uses as few libs as possible for linking
  • Explicit name lookup of attributes from template base
  • Preprocessor misconception fixed (#if vs. #ifdef)
  • polybori.gbcore drops assumption ideal were a list (still assuming iteratable)
  • png generation via libm4ri (alternative to libgb)
We also experimented with alternative procedures for converting matrix-represented polynomial systems to binary-decision diagrams. This would improve the F4-like algorithms within PolyBoRi. While having fixed some minor issues we had to postpone major changes due to a serious performance regression :-( We hope to get back to this soon.

My best

Tuesday, June 19, 2012

PolyBoRi at YouTube

Michael Brickenstein was invited to speak at the ELAGB workshop here in Kaiserslautern. You can find his talk at YouTube:
We also recorded the other talks, see here for the complete list of videos and slides.

My best,

Friday, March 16, 2012

Releasing PolyBoRi 0.8.1

Dear PolyBoRi users,
we are proud to announce that PolyBoRi 0.8.1 is available at

We continue to follow the two major goals of the 0.8 branch: stability and compatibility. In addition, for improved supporting of external developers we partially restructured the sources of libpolybori_groebner.

The full changelog of release 0.8.1 reads as follows:
* fallback m4ri updated to release 20111203
* Merged Cudd with cudd 2.5.0
* Prefixed patched Cudd's function with pbori_
* ipbori is now an all-python script with fallback to plain python if
  IPython is not available
* Python interface utilizes shared libraries
* PolyBoRi's shared libraries are found via relative rpath
  (relative install-name on Darwin)
* introducing DEFAULT_*FLAGS
* Install/InstallAs fixes permissions
* ipbori -t runs PolyBoRi's doctests
* internal refactoring of ReductionStrategy and GroebnerStrategy started
* avoiding long long

Binary packages are available for recent OpenSuSE, Mandriva and Fedora as well as Debian and Ubuntu distributions. Just point your package manager here:

In addition the corresponding communities bundled preliminary spkgs
and Gentoo ebuild scripts are available via the lmonade project at http://www.lmona.de/ .

With best regards,
  The PolyBoRi Team

Monday, March 5, 2012

Wanted: Applied Computer Algebra in Tech

Currently I'm about to support a student's projects for collecting and categorizing examples arising from technical applications of computer algebra. Our benchmark examples from formal verification of digital systems and cryptoanalysis mark a (proper) subset of these use cases. But from my experience such projects prosper from a wider example base.

Are there readers around which use computer algebra techniques in industrial, biological, medical, or chemical applications? Would you like to direct our attention to some examples from your area? Of course, one of our goals is proper citing of the contributed stuff as well as mentioning the contributor itself.

If you are interested to drop us a message at industrial@3r4u.de.

My best,