Archive

Archive for the ‘symbolic computation’ Category

Sage Math weekly Facebook update: 2010-09-08

8 September 2010 Leave a comment

Here is this week’s summary for the Sage Math Facebook page:

  • 335 monthly active users; 17 since last week
  • 1,752 people like this; 15 since last week
  • 13 wall posts and comments this week; no change since last week
  • 460 visits this week; 87 since last week

Typesetting Sage code listings in LaTeX

27 June 2010 1 comment

I needed to typeset Sage code listings in a LaTeX document. I have used the listings package before, but I want to customize with colours for keywords, comments, strings, etc. Borrowing some customization from William Stein’s ICMS 2010 paper, I think I have my customization just about right. The relevant code snippet for the preamble is:

%% For typesetting code listings                                                
\usepackage{listings}
\lstdefinelanguage{Sage}[]{Python}
{morekeywords={False,sage,True},sensitive=true}
\lstset{
  frame=none,
  showtabs=False,
  showspaces=False,
  showstringspaces=False,
  commentstyle={\ttfamily\color{dgreencolor}},
  keywordstyle={\ttfamily\color{dbluecolor}\bfseries},
  stringstyle={\ttfamily\color{dgraycolor}\bfseries},
  language=Sage,
  basicstyle={\fontsize{10pt}{10pt}\ttfamily},
  aboveskip=0.3em,
  belowskip=0.1em,
  numbers=left,
  numberstyle=\footnotesize
}
\definecolor{dblackcolor}{rgb}{0.0,0.0,0.0}
\definecolor{dbluecolor}{rgb}{0.01,0.02,0.7}
\definecolor{dgreencolor}{rgb}{0.2,0.4,0.0}
\definecolor{dgraycolor}{rgb}{0.30,0.3,0.30}
\newcommand{\dblue}{\color{dbluecolor}\bf}
\newcommand{\dred}{\color{dredcolor}\bf}
\newcommand{\dblack}{\color{dblackcolor}\bf}

And here’s an example

\begin{lstlisting}
sage: R.<x> = ZZ[]
sage: type(R.an_element())
<type 'sage.rings...Polynomial_integer_dense_flint'>
sage: R.<x,y> = ZZ[]
sage: type(R.an_element())
<type 'sage.rings...MPolynomial_libsingular'>
sage: R = PolynomialRing(ZZ, 'x', implementation='NTL')
sage: type(R.an_element())  # this is a comment
<type 'sage.rings...Polynomial_integer_dense_ntl'>
sage: def abc():
...       """
...       This should be a very long comment.
...       That should span multiple lines.
...       To illustrate what colour Sage comments look like.
...       To get a feel for the color when rendered using LaTeX.
...       """
...       return 2
\end{lstlisting}

This renders as follows:

Pushing towards 90% doctest coverage for Sage 5.0

10 June 2010 Leave a comment

This is an edited version of my post to sage-devel. One of the main goals of the upcoming Sage 5.0 release is to get doctest coverage of the Sage library up to at least 90%. As of Sage 4.4.4.alpha0, the overall weighted coverage is 82.7%. To get a sense of which modules in the Sage library need work on their coverage scores, you could use the coverage script as follows:

$ ./sage -coverage /path/to/module.py[x]

Or you could do the following to get the coverage scores of all modules, including a coverage summary:

$ ./sage -coverageall

You might be interested in knowing which modules have a certain coverage percentage, in which case you could save the output of -coverageall to a text file and then grep that file for certain coverage scores. At this repository is a script to generate various types of coverage analysis reports. You can also find the script here. The script currently supports the following reports

  1. The coverage summary of all modules.
  2. Modules with 100% coverage.
  3. Modules with zero coverage.
  4. Modules with between 1% and 9% coverage.
  5. Modules with between 10% and 19% coverage.
  6. Modules with between 20% and 29% coverage.
  7. Modules with between 30% and 39% coverage.
  8. Modules with between 40% and 49% coverage.
  9. Modules with between 50% and 59% coverage.
  10. Modules with between 60% and 69% coverage.
  11. Modules with between 70% and 79% coverage.
  12. Modules with between 80% and 89% coverage.
  13. Modules with between 90% and 99% coverage.

Each report has links to detailed reports for individual modules. To run the script, copy it to the SAGE_ROOT of a Sage source or binary installation and do

[mvngu@sage sage-4.4.4.alpha0]$ ./coverage-status.py 
Coverage report of all modules...
Summary of doctest coverage...
Modules with 0% coverage...
Modules with 100% coverage...
Coverage reports within certain ranges...
Detailed coverage report for all modules...
Format the detailed coverage reports...
Format the summary reports...
Generate index.html...

And you’re done. Here is a report generated by the script. The idea is to provide an overview of which modules need work. I’d be interested to know what other types of doctest coverage reports people would like to see. Comments, suggestions, critiques, etc. are welcome.

Hill cipher in Sage

2 June 2010 1 comment

Let’s first consider how Hill cipher encryption is commonly presented in introductory texts on cryptography or even Wikipedia. Let {M} be a {3 \times 3} invertible matrix over {\mathbf{Z}_{26}} and let {P} be a {3 \times n} matrix also over {\mathbf{Z}_{26}}. We call {M} the encryption key and {P} is referred to as the plaintext. The ciphertext {C} corresponding to {P} is given by

\displaystyle  C = MP \pmod{26}.

According to this scheme of encryption, given

\displaystyle   M = \begin{bmatrix} 6 & 24 & 1 \\ 13 & 16 & 10 \\ 20 & 17 & 15 \end{bmatrix} \ \ \ \ \ (1)

and

\displaystyle   P = \begin{bmatrix} 0 \\ 2 \\ 19 \end{bmatrix} \ \ \ \ \ (2)

then the ciphertext is

\displaystyle  C = \begin{bmatrix} 6 & 24 & 1 \\ 13 & 16 & 10 \\ 20 & 17 & 15 \end{bmatrix} \begin{bmatrix} 0 \\ 2 \\ 19 \end{bmatrix} = \begin{bmatrix} 15 \\ 14 \\ 7 \end{bmatrix}.

Hill cipher encryption in Sage works differently from that presented above. If {M} is the encryption matrix key and {P} is the plaintext matrix, then the ciphertext is the matrix {PM}. Here, {M} is still a square ({3 \times 3}) matrix and {P} is an {n \times 3} matrix where the entries are filled from left to right, top to bottom. According to this scheme of encryption, with {M} and {P} as in (1) and (2), respectively, we get

\displaystyle  C = P^T M = \begin{bmatrix} 0 & 2 & 19 \end{bmatrix} \begin{bmatrix} 6 & 24 & 1 \\ 13 & 16 & 10 \\ 20 & 17 & 15 \end{bmatrix} = \begin{bmatrix} 16 & 17 & 19 \end{bmatrix}.

Or using Sage:

sage: version()
Sage Version 4.4.1, Release Date: 2010-05-02
sage: H = HillCryptosystem(AlphabeticStrings(), 3)
sage: M = Matrix(IntegerModRing(26), [[6,24,1], [13,16,10], [20,17,15]])
sage: P = H.encoding("ACT")
sage: H.enciphering(M, P)
QRT

Sage 4.4.2 release schedule

7 May 2010 Leave a comment

Sage 4.4.2 is intended to be a little release on the way to Sage 5.0. I’m devoting a week or so to managing the release of Sage 4.4.2. Here’s a proposed release schedule I posted to sage-release:

  • Sage 4.4.2.alpha0 — release 10th May 2010
  • Sage 4.4.2.rc0 — feature freeze; release 15th May 2010
  • Anything critical to get Sage 4.4.2.final to stabilize
  • Sage 4.4.2.final — release 18th May 2010

I’m being too optimistic here with the above schedule. But we’ll see how things go.

Binary trees and branch cut

1 May 2010 1 comment

The topic and content of this post originate from a question to sage-support. I’m posting the essential responses here so it doesn’t get lost in the sage-support archive.

Problem

How do you construct a binary tree in Sage? If T is a binary tree, how do you cut off a branch of that tree?

Solution

There is as yet no class for representing binary trees in Sage. However, you could use either the classes Graph or DiGraph to construct a graph T and then use the method T.is_tree() to determine whether or not T is a tree. There is also a balanced tree generator. Also missing is a method to determine whether or not a tree is binary. That can be remedied by defining your own function to test the number of children a vertex has. Using Graph to construct a tree, and then test that tree to see that it is binary, is rather difficult because unless you label the vertices to indicate their parents, you don’t know which vertex is a child of which other vertex.

In general, I prefer using DiGraph to construct a tree T and then use the method T.neighbors_out() in testing whether or not T is a binary tree. The reason is that in a digraph that represents a tree, you can think of the out-neighbors of a vertex as being the children of that vertex. Here is an example demonstrating the construction of a binary tree rooted at vertex v. By definition, a vertex in a binary tree has at most 2 children. The session below uses this definition to test whether or not a tree is binary.

sage: T = DiGraph({"v": ["a", "w"],
....: "w": ["x", "y"],
....: "x": ["c", "b"],
....: "y": ["z", "d"],
....: "z": ["f", "e"]})
sage: T.vertices()
['a', 'b', 'c', 'd', 'e', 'f', 'v', 'w', 'x', 'y', 'z']
sage: T.edges(labels=None)
[('v', 'a'), ('v', 'w'), ('w', 'x'), ('w', 'y'), ('x', 'b'), ('x', 'c'), ('y', 'd'), ('y', 'z'), ('z', 'e'), ('z', 'f')]
sage: T.is_tree()
True
sage: def is_binary_tree(tree):
....:     for v in tree.vertex_iterator():
....:         if len(tree.neighbors_out(v)) > 2:
....:             return False
....:     return True
....:
sage: is_binary_tree(T)
True

Nathann Cohen offered another way to test that a graph is a binary tree.

sage: def is_binary_tree(g):
....:     if g.is_tree() and max(g.degree()) == 3 and g.degree().count(2) == 1:
....:         return True
....:     return False
....: 
sage: is_binary_tree(T)
True

Once you have determined the root vertex of a branch that you want to cut off, you could use breadth-first search (or depth-first search) to determine all vertices in that branch. Again, assume that your binary tree T is represented using the DiGraph class and V is a list of vertices in the branch you want to cut off. You can use the method T.delete_vertices() to cut off that branch. Deleting a vertex v not only deletes v, but also all edges incident on that vertex. Say you have constructed your tree as in the above session and you have determined that the vertex y is the root of the branch you want to cut off. Here is how you can cut off that branch:

sage: V = list(T.breadth_first_search("y"))
sage: V
['y', 'd', 'z', 'e', 'f']
sage: T.delete_vertices(V)
sage: T.vertices()
['a', 'b', 'c', 'v', 'w', 'x']
sage: T.edges(labels=None)
[('v', 'a'), ('v', 'w'), ('w', 'x'), ('x', 'b'), ('x', 'c')] 

Adding Mercurial patches before building Sage

8 March 2010 Leave a comment

The following problem and accompanying solution were posted to sage-devel. I have polished them up a bit and put them here so they won’t be buried in the huge sage-devel mailing list.

Problem

You have a number of Mercurial patches that you want to apply to a Sage source distribution. However, you don’t want to go through the following work flow:

  1. Build a Sage source distribution.
  2. Apply your patches to the Sage library.
  3. Produce a new source tarball based on your patched Sage source distribution.
  4. Compile your newly wrapped up modified Sage source tarball.

The key problem is that you don’t want to run through two separate compilation processes.

Solution

The following solution uses the queues extension of Mercurial. In a Sage source tarball, the Sage library is wrapped up as the package

SAGE_ROOT/spkg/standard/sage-x.y.z.spkg

Uncompress that bzip2 compressed tarball to get a directory named

SAGE_ROOT/spkg/standard/sage-x.y.z/

If you want, you could delete

SAGE_ROOT/spkg/standard/sage-x.y.z.spkg

Now patch the Sage library as if it had been built and found under SAGE_ROOT/devel:

$ cd SAGE_ROOT/spkg/standard/sage-x.y.z/
$ hg qimport /URL/or/path/to/patch.patch
$ hg qpush
$ <repeat-previous-two-commands-as-often-as-required>

The command

$ hg qapplied

should return a list of patches you have applied using “hg qpush“. Once you are happy that you have applied all necessary patches, wrap up the patched Sage library:

$ pwd
SAGE_ROOT/spkg/standard/sage-x.y.z/
$ hg qfinish -a
$ cd ..

And see this section of the Developer’s Guide to find out how to package the newly patched Sage library, i.e. the directory

SAGE_ROOT/spkg/standard/sage-x.y.z/

Now you should have

SAGE_ROOT/spkg/standard/sage-x.y.z.spkg

so you could delete

SAGE_ROOT/spkg/standard/sage-x.y.z/

Finally, proceed to build Sage from source.