Yet Another Mathblog

Evil spkgs?

In Matlab, a plugin is called a “toolkit”. In Photoshop, a plugin is called a plugin:-) As the success of Photoshop and Matlab suggest, plugins are very important. They enable “third party” developers to write specialized applications for your software package.

In Sage, (www.sagemath.org) a plugin is called an “spkg” (short for Sage PacKaGe).

Here is an easy-to-follow recipe for making an evil spkg.

  1. Make sure that your spkg modifies and existing Python or Cython file in the Sage devel tree. Extra evil bonus points for modifying heavily used files, such as in the plot subdirectory, and the more files touched the more evil points you earn. AFAIK, this will insure that, once your “innocent” spkg is applied to a developers tree, he cannot write a trac patch which can be correctly applied to a fresh clone.
  2. Make sure you ruin another spkg (surreptitiously, for extra bonus points). The more important the spkg you hose, the more evil points you get.

I wonder how Matlab and Photoshop avoid evil plugins?

August 1, 2009 Posted by wdjoyner | sage | | No Comments Yet

Sage at the NSF-CDI+ECCAD conferences

This is a very quick view of some highlights of the conference http://www4.ncsu.edu/~kaltofen/NSF_WS_ECCAD09_Itinerary.html. I think further details of the talks will appear on the conference webpage later. This is very incomplete – just a few thought I was able to
jot down correctly.

Panel discussion:
Q1: What are the grand challenges of symbolic computing?
Is the term “symbolic computation” to broad? (Hybrid symbolic/numerical, algebraic geometric computation, algebraic combinatorial/group-theoretical, computer proofs, tensor calculations, differential, mathematical knowledge/database research, user interfaces, …)

General ans: No. Hoon Hong points out that user interfaces are lower level but below to the same group.

Q2: How can the latest algorithmic advances be made readily available: google analog of problem formulation? (Idea: suppose someone has a clever idea for a good algorithm but not enough discipline to implement it …)

One answer: Sage can put software together – is this the right way? Analog of stackoverflow.com?

Q3: What is the next killer app for symbolic computation? (Oil app of Groebner bases, cel phone app, robotics, …)

Q4: Can academically produced software such as LAPACK, LINBOX, SAGE compete with commercial software?

Hoon Hong answer: Yes but why? Why not cooperate. Support Sage very much but more research on interfaces and integration of different systems could lead to cooperation of the commercial systems with Sage.

Another panel:
Q: What are the spectacular successes and failures of computer algebra?

Failures:
(a) Small number of researchers.
(b) Sage could fail from lack of lies with the symbolic/numerical community (as Maxima/Axiom did). Matlab may fail due to uphill battle to integrate Mupad into good symbolic toolbox. (Many voiced view that Matlab is strong because of its many toolboxes, on the panel and privately.)
(c) Education at the High School level using CA.
(d) Presenting output of CA intelligently and in a standard format.
(e) Failure to teach people how to properly use a CA system.

Successes:
(a) Sage – interesting new effort (with caveat above)
(b) Groebner bases, LLL.

My talk on Sage raised a lot of questions. My There is both strong support for Sage and some questions on its design philisophy. My page 6 at http://sage.math.washington.edu/home/wdj/expository/nsf-eccad2009/
was a source of lots of questions.

At ECCAD http://www.cs.uri.edu/eccad2009/Welcome.html, Sage was mentioned a few times in talks as well as in some posters. The “main” Sage event was a laptop software demo Which Karl-Dieter Crisman set up for Sage.

Overall, a good experience for Sage.

May 7, 2009 Posted by wdjoyner | math, sage | , , | No Comments Yet

Sage at AMS-MAA 2009 Washington DC

I think Sage gained a lot of publicity this year both by being at
the booth but also having an MAA panel discussion and an AMS session.
The panel discussion was good to be able to meet others in the
teaching community. I think this is related to Sage development because
projects like the educational open source software webworks has a
funding model which seems to be successful. I think Karl Crisman said he
would try to follow up on that.

A few people I met at the booth said they were interested in Sage development
but more stopped by saying that either they or their students could not afford
Maple or Mma and was looking into a cheaper quality alternative. The collaroration
possibilities of the Sage server was a strong “selling point” for smaller schools
which could load sage on a webserver.

There were some really good talks at the Sage session. For example,
Marshall’s talk had amazing graphics and Robert Miller’s talk was very well attended
(with maybe twice as many people in the audience as some of the others).
I thought the quality overall was great, but I’m very partial to such topics of course.

The general message I got from many was that more written material
on Sage in use would be welcomed, especially books. I was touched by one guy
who explained to me that his students were very poor (waitresses, for example)
who cannot afford calculus texts and commercial math programs. The point
he was implicitly making was that by offering software and documentation for
free we are actually improving the quality of such peoples’ lives in a real way.

January 8, 2009 Posted by wdjoyner | math, sage | , | 2 Comments

Future coding theory in Sage projects

Here are a few ideas for future Sage projects in error-correcting codes.

Needed in Sage is

  • a rewrite in Cython, for speed,
  • special decoding algorithms, also in Cython,
  • for special decoders, it seems to me that one either needs
  1. more classes (eg, a CyclicCodes class), each of which will have a decode method, or
  2. another attribute, such as a name (string) which can be used to determine which decoder method to use.
  • codes over Rings (Cesar Agustin Garcia Vazquez is working on this)
  • codes defined from finite groups fings – for example split group codes,
  • a fast minimum distance function (followed by a fast weight distribution function), valid for all characteristics.

It seems more “Pythonic” to add more classes for decoders, but I am not sure.

December 11, 2008 Posted by wdjoyner | math, sage | , | 2 Comments

Steiner systems and codes

A t-(v,k,λ)-design D=(P,B) is a pair consisting of a set P of points and a collection B of k-element subsets of P, called blocks, such that the number r of blocks that contain any point p in P is independent of p, and the number λ of blocks that contain any given t-element subset T of P is independent of the choice of T. The numbers v (the number of elements of P), b (the number of blocks), k, r, λ, and t are the parameters of the design. The parameters must satisfy several combinatorial identities, for example:

\lambda _i = \lambda \left(\begin{array}{c} v-i\\ t-i\end{array}\right)/\left(\begin{array}{c} k-i\\ t-i\end{array}\right)

where \lambda _i is the number of blocks that contain any i-element set of points.

A Steiner system S(t,k,v) is a t-(v,k,λ) design with λ=1. There are no Steiner systems known with t>5. The ones known (to me anyway) for t=5 are as follows:

S(5,6,12), S(5,6,24), S(5,8,24), S(5,7,28), S(5,6,48), S(5,6,72), and S(5,6,84).

Question: Are there others?

A couple of these are well-known to arise as the support of codewords of a constant weight in a linear code C (as in the Assmus-Mattson theorem, discussed in another post) in the case when C is a Golay code (S(5,6,12) and S(5,8,24)). See also the wikipedia entry for Steiner system.

Question: Do any of these others arise “naturally from coding theory” like these two do? I.e., do they all arise as the support of codewords of a constant weight in a linear code C via Assmus-Mattson?

Here is a Sage example to illustrate the case of S(5,8,24):

sage: C = ExtendedBinaryGolayCode()
sage: C.assmus_mattson_designs(5)
['weights from C: ',
[8, 12, 16, 24],
‘designs from C: ‘,
[[5, (24, 8, 1)], [5, (24, 12, 48)], [5, (24, 16, 78)], [5, (24, 24, 1)]],
‘weights from C*: ‘,
[8, 12, 16],
‘designs from C*: ‘,
[[5, (24, 8, 1)], [5, (24, 12, 48)], [5, (24, 16, 78)]]]
sage: C.assmus_mattson_designs(6)
0
sage: blocks = [c.support() for c in C if hamming_weight(c)==8]; len(blocks)
759

October 2, 2008 Posted by wdjoyner | math, sage | , , , , , | No Comments Yet

The Assmus-Mattson Theorem, Golay codes, and Mathieu groups

A block design is a pair (X,B), where X is a non-empty finite set of v>0 elements called points, and B is a non-empty finite multiset of size b whose elements are called blocks, such that each block is a non-empty finite multiset of k points. A design without repeated blocks is called a simple block design. If every subset of points of size t is contained in exactly \lambda blocks the the block design is called a t–(v,k,\lambda) design (or simply a t-design when the parameters are not specfied). When \lambda = 1 then the block design is called a S(t,k,v) Steiner system.

Let C be an [n,k,d] code and let C_i = \{ c \in C\ |\ wt(c) = i\} denote the weight i subset of codewords of weight i. For each codeword c\in C, let supp(c)=\{i\ |\ c_i\not= 0\} denote the support of the codeword.

The first example below means that the binary [24,12,8]-code C has the property that the (support of the) codewords of weight 8 (resp, 12, 16) form a 5-design.

Example: Let $C$ denote the extended binary Golay code of length 24. This is a self-dual [24,12,8]-code. The set X_8 = \{supp(c)\ |\ c \in C_8\} is a 5-(24, 8, 1) design; X_{12} = \{supp(c)\ |\ c \in C_{12}\} is a 5-(24, 12, 48) design;and, X_{16} = \{supp(c)\ |\ c \in C_{16}\} is a 5-(24, 16, 78) design.

This is a consequence of the following theorem of Assmus and Mattson.

Assmus and Mattson Theorem (section 8.4, page 303 of [HP]):

Let A_0, A_1, ..., A_n be the weight distribution of the codewords in a binary linear [n , k, d] code C, and let A_0^\perp, A_1^\perp, ..., A_n^\perp be the weight distribution of the codewords in its dual [n,n-k, d^\perp] code C^\perp. Fix a t, 0<t<d, and let s = |\{ i\ |\ A_i^\perp \not= 0, 0<i\leq n-t\, \}|.
Assume s\leq d-t.

  • If A_i\not= 0 and d\leq i\leq n then C_i = \{ c \in C\ |\ wt(c) = i\} holds a simple t-design.
  • If A_i^\perp\not= 0 and d^\perp\leq i\leq n-t then C_i^\perp = \{ c \in C^\perp \ |\ wt(c) = i\} holds a simple t–design.
  • If A_i^\perp\not= 0 and d^\perp\leq i\leq n-t then C_i^\perp = \{ c \in C^\perp \ |\ wt(c) = i\} holds a simple t–design.

In the Assmus and Mattson Theorem, X is the set \{1,2,...,n\} of coordinate locations and B = \{supp(c)\ |\ c \in C_i\} is the set of supports of the codewords of C of weight i. Therefore, the parameters of the t-design for C_i are

  • t = given,
  • v = n,
  • k = i, (this k is not to be confused with dim(C)!),
  • b = A_i,
  • \lambda = b*binomial(k,t)/binomial(v,t)

(by Theorem 8.1.6, p. 294, in \cite{HP}). Here is a SAGE example.


sage: C = ExtendedBinaryGolayCode()
sage: C.assmus_mattson_designs(5)
['weights from C: ',
[8, 12, 16, 24],
'designs from C: ',
[[5, (24, 8, 1)], [5, (24, 12, 48)], [5, (24, 16, 78)], [5, (24, 24, 1)]],
'weights from C*: ',
[8, 12, 16],
'designs from C*: ',
[[5, (24, 8, 1)], [5, (24, 12, 48)], [5, (24, 16, 78)]]]
sage: C.assmus_mattson_designs(6)
0

The automorphism group of the extended binary Golay code is the Mathieu group M_{24}. Moreover, the code is spanned by the codewords of weight 8.

References:
[HP] W. C. Huffman, V. Pless, Fundamentals of error-correcting codes, Cambridge Univ. Press, 2003.
[CvL] P. Cameron, J. van Lint, Graphs, codes and designs, Cambridge Univ. Press, 1980.

May 25, 2008 Posted by wdjoyner | math, sage | , , | No Comments Yet