Triangle dissections

August 28, 2009 | Filed Under sage | Leave a Comment 

Some of my research is on dissections of triangles into equilateral triangles. Here’s an example:

So the outer equilateral triangle is cut up into smaller equilateral triangles, and no triangles overlap except along a common edge or point.

One of the earliest references on triangle dissections is this paper: The Dissection of Equilateral Triangles into Equilateral Triangles, W.T.Tutte, Proceedings of the Cambridge Philosophical Society, Vol. 44, pages 464-82, 1948. There, Tutte showed a connection between equilateral triangle dissections and electrical networks. See also http://www.squaring.net/tri/twt.html and the paper The dissection of rectangles into squares – R. L. Brooks, C. A. B. Smith, A. H. Stone and W. T. Tutte; 312-340.

A perfect dissection has no two triangles of the same size in the same orientation (up or down). Tutte conjectured that the smallest perfect dissection has size 15, and some recent enumeration work shows this to be the case (a paper will come out soon with these results). Here are the two perfect dissections of size 15, and perfect dissections of size 16 and 17:

Those graphics are produced using PyX and Sage. Full PDFs are available here.

Debugging Sage using Eric4

June 18, 2009 | Filed Under sage | Leave a Comment 

This is just a short note on how to use the Eric4 program to debug a Sage script (a .py file). It’s a slightly updated version of a post on some Sage mailing list that I can’t find right now.

On Ubuntu 9.04, install Eric4:

sudo apt-get install eric

Save the following to a file:

#!/bin/bash
x=`pwd`
export SAGE_ROOT=/path_to_your_sage_installation
cd $SAGE_ROOT
source local/bin/sage-env
cd $x
sage-python ${*}

Start Eric4 and go to Settings, Preferences, Debugger/Python, and set the Custom Python Interpreter to the file that you just saved.

Using File, Open you can debug a Python file that uses the Sage libraries, e.g.:

from sage.all import *
r=MPolynomialRing(GF(127),2,'x')
print r.gens()

To set a breakpoint in the Sage library itself use the ? sign to find out where a file is located. For example

sage: PolynomialRing?

shows us that PolynomialRing comes from

$SAGE_ROOT/local/lib/python2.5/site-packages/sage/rings/polynomial/polynomial_ring_constructor.py

If you open that file (File, Open) you can set breakpoints and so on.

A note to netbook users: Eric4′s default window is quite large and did not display properly on my Asus EEE PC. The solution is to remove most of the toolbar entries (these are accessible from the menu anyway) and also change the window mode to detached windows so that you can alt-tab between the various components of Eric4 instead of having them all in one giant window.

Cython vs. C++, improved

November 9, 2008 | Filed Under sage | 2 Comments 

In a recent post I compared my Cython and C++ implementations of a depth first search algorithm. The Cython code was quite slow, and Robert Bradshaw commented:

This graph looked pretty depressing, so I made some optimizations to your code (basically the ones suggested above, and a couple of other glaring things that stood out). The algorithm is still completely the same, and I didn’t do any code re-factoring other than __getitem__/__setitem__, just mostly typing things here and there. It’s now faster than c++ on my machine for the whole range graphed above (and much faster for small inputs).

Code and diff up at http://sage.math.washington.edu/home/robertwb/cython/scratch/cython-latin/

I applied Robert’s patch and re-ran the tests on my laptop:

The Cython implementation with Robert’s patch is now significantly faster than the C++ implementation on most of the range that I checked.

Cython vs C++

March 4, 2008 | Filed Under sage | 10 Comments 

Edit (2008-11-09): Robert Bradshaw posted a patch to my code and the Cython implementation is now a lot faster. Click here to read more.

In a comment on a recent post, Robert Šámal asked how Cython compares to C++. The graph below shows a comparison of a greedy critical set solver written in Cython and C++ (both use a brute force, naive, non-randomised implementation of a depth first search):

So things look good until n = 10. In defence of Cython, I must point out that my implementation was a first attempt and I am by no means an expert on writing good Cython code. Also, the Cython code is probably fast enough – in my experience, solving problems (computationally) for latin squares of order 10 is futile, so the code is more convenient for testing out small ideas.

edit: the code is here

edit: Robert’s code is here http://sage.math.washington.edu/home/robertwb/cython/scratch/cython-latin/

An exact cover solver for Sage

March 1, 2008 | Filed Under sage | Leave a Comment 

For a while now I’ve been using my own C++ implementation of Knuth’s Dancing Links algorithm. The algorithm is quite fast for solving the 0-1 matrix exact cover problem. More importantly, a number of other combinatorial problems can be converted into an exact cover framework, such as finding latin square completions, enumerating latin bitrades, and computing the chromatic number and chromatic polynomial of graphs (those last two are from comments by Tom Boothby on the sage-devel mailing list).

The thread started by Tom inspired me to make my code public, license it with GPL, write a few doctests, and learn the necessary Cython to write a wrapper for my C++ code so that it would be usable from Sage. The code is available here, in particular dancing_links.sage (top level Sage wrapper), dancing_links.spyx (Cython code that calls my C++ code), and finally dancing_links.cpp (the actual solver).

Not surprisingly, the C++ version is a fair bit faster than the Python implementation adapted by Tom when used as a latin square solver for finding “greedy” critical sets:

x-axis: n, y-axis: number of seconds to compute the greedy critical set of B_n (addition table for Z_n), blue is Python, red is C++.

pyx-0.10 experimental package

February 17, 2008 | Filed Under sage | Leave a Comment 

PyX is a Python package for the creation of PostScript and PDF files. It seems like a more modern alternative to MetaPost so I was keen to try it out. I found that the experimental pyx-0.8.1 package in Sage 2.10 did not work (errors about a DVI file not finishing) so I created a Sage source package of the latest version: pyx-0.10.spkg.

Download that package and then do sage -i pyx-0.10.skpg to install it.

Here is the standard Hello World example (look for hello.pdf in your working directory):

import pyx

x = y = int(0)

c = pyx.canvas.canvas()
c.text(x, y, “Hello, world!”)
c.stroke(pyx.path.line(x, y, x+5, y+0))
c.writePDFfile(“hello”)

The previous pyx spkg tried to put the pyxrc file into /etc but I prefer to run Sage as a normal user, and sudo-ing to install a package isn’t completely straightforward (you have to set some environment variables, so it’s not newbie-friendly). I made my spkg-install file put pyxrc into $SAGE_LOCAL/etc but I’m not sure if this is a suitable location. Any suggestions?

edit: On the sage-devel mailing list I was told to use ~/.sage so I have ammended the pyx-0.10 package to do this.

Using ‘yield’ to simulate a Markov chain

December 16, 2007 | Filed Under sage | Leave a Comment 

One thing that I really like about Sage is that it uses Python as its underlying language. This means that we get “for free” many nice features of Python. One of these features that I particularly like is the yield keyword. Here is a small example:

def foo():
    i = 0
    while True:
        yield i
        i = i + 1

We can use the foo function as a generator:

sage: g = foo()
sage: print g.next()
0
sage: print g.next()
1
sage: print g.next()
2

In other words, the yield keyword acts as a way to a Python function into a generator. The execution of foo is paused until the next call to g.next(). If we reach the end of the function, the StopIteration exception is raised.

The yield keyword makes it pretty easy to write the skeleton for a Markov chain simulator, using the following basic form:

def markov_chain():
    state = initial_state()
    while True:
        yield state

        state = new_state(state)

        if some_condition: return

For a real example, see the latin_square_generator function in
latin.sage which is part of a small library for
latin square manipulations in Sage. The Markov chain itself was given by Jacobson and Matthews in “Generating uniformly distributed random Latin squares,” Journal of Combinatorial Designs, vol 4, 1996, no 6, pp 405–437.