Sheafhom is a package for large-scale mathematical computations. Its front end is a language for problems in algebraic topology and number theory. These problems come down to large sparse systems of linear equations over integral domains, especially the integers. Sheafhom's back end solves the sparse systems.

Sheafhom 1.x was developed in 1993-99 in Common Lisp. Sheafhom 2.0 was written in 2001-2004 in Java. Sheafhom 2.1 is again in Common Lisp, which is ideal for several reasons. Arbitrary-precision integers are built into the language and can be very fast. It is easier to write the code in layers by using macros, as well as CLOS.

The back end. Fill-in is a concern in sparse linear algebra using either exact or inexact (floating-point) numbers. Imagine row-reducing the following matrix, where the letters are arbitrary non-zero numbers (all x's distinct).

  a x 0 0 x x
  x 0 x x 0 0
  x 0 x x 0 x
  b 0 0 x 0 x

We want to choose one row and add multiples of it to the other rows until the first column has only one non-zero entry. If we choose the top row (a is the pivot), the result will look like this, where * is a new non-zero entry.

  a x 0 0 x x
  0 * x x * *
  0 * x x * x
  0 * 0 x * x

If b is the pivot, the result will be

  0 x 0 * x x
  0 0 x x 0 *
  0 0 x x 0 x
  b 0 0 x 0 x

The second result has less fill-in, two *'s rather than seven.

Fill-in compounds on itself as we reduce row after row. A sparse solver must reduce fill-in by choosing the pivots cleverly. Sheafhom currently uses the well-established Markowitz pivoting algorithm (see the Book section). It is also a platform for experiments with pivoting strategies that may be better for topology.

Floating-point work must balance fill-in with numerical stability. In the example, if b is much smaller than a, using b as pivot may introduce too much round-off error. We may be forced to use a, with its larger fill-in. Over the integers, numerical stability is replaced with the opposite problem: integer explosion. In integer multiplication, the length (number of digits) of the product is roughly the sum of the lengths of the factors. By the end of a row-reduction, matrix entries often have hundreds or thousands of digits. Sheafhom has several strategies for reducing integer explosion.

Sheafhom 2.x offers two kinds of graphical tools to study fill-in and integer explosion.

• Line graphs show the growth of the sparsity percentage and number of row/column operations.
• Sheafhom can generate movies showing the sparsity pattern changing in real time. This slows down the computation, but is a strong asset for testing pivoting algorithms.

The front end. The front end of Sheafhom 1.x was a language for sheaf theory. A topological space of dimension n can be glued together from cells of dimensions 0 through n, represented in code as a data structure of face relations. A sheaf is a choice of sparse matrices, one for each face relation, with various commuting properties. A linear map of sheaves is a choice of sparse matrix for each cell commuting with the matrices from the face relations. A complex of sheaves is a sequence of linear maps of sheaves, and so on. CLOS is a good tool for handling these layers of abstractions piled on abstractions.

The full front end of Sheafhom 1.x has not been ported over to 2.1. Version 1.x did not handle integers modulo n, and the front end will be rewritten in 2.2 to fix this gap. Nevertheless, 2.1 supports good code for topology, as the Tutorial section shows.

Language features. Sheafhom 2.1's lowest layer is a language of macros that expresses matrices in the bare bones of Lisp, integers for entries and lists for sparse vectors. Macros optimize the low-level code, with prolix declarations and with macroexpand and disassemble for checking the work.

Above the lower levels, Sheafhom treats speed as a second--though high--priority. Avoiding fill-in and integer explosion is the first priority. In the Tutorial, we will reduce a matrix of 26 rows and over 173,000 columns.

The macro with-splicer embodies a mini-language for surgery on lists. It iterates down a list and offers insert, delete, and larger splicing commands, all without disturbing the iteration. The core sparse vector routines rely on with-splicer.

Sheafhom 2.1 is strictly in ANSI CL. The only exception is the file gui.lisp with the graphical tools. This uses Allegro's jlinker to call out to Java. It could be adapted to other platforms.

The back end of Sheafhom 2.1 uses integers. However, the low-level macro language has been carefully written so it can be extended to finite fields, rings of integers in algebraic number fields, and other types of "numbers".

The following papers are related to Sheafhom or its ancestors.

The rational homology of toric varieties is not a combinatorial invariant, Mark McConnell, Proc. AMS 105 (1989), 986-991.

Cohomology at infinity and the well-rounded retract for general linear groups, Avner Ash and Mark McConnell, Duke Math. Jour. 90 (1997), 549-576.

Cohomology of congruence subgroups of SL(4,Z), Avner Ash, Paul Gunnells and Mark McConnell, J. Number Theory 94 (2002), no. 1, 181-212.

http://www.geocities.com/mmcconnell17704/math.html

Direct Methods for Sparse Matrices, I. S. Duff, A. M. Erisman and J. K. Reid, Clarendon Press, 1987. The authors are experts in sparse matrices over the real numbers. The book covers the Markowitz algorithm and other pivoting algorithms.

Cohomology of Sheaves, Birger Iversen, Universitext, Springer-Verlag, 1986. The inspiration for the abstract front end of Sheafhom: exact categories, abelian categories, complexes, and the derived category.

Methods of Homological Algebra, 2nd ed., S. I. Gelfand and Yu. I. Manin, Springer Monographs in Mathematics, Springer, 2003. A modern approach to derived categories.

Basic Algebra I, 2nd ed., Nathan Jacobson, W. H. Freeman and Co., 1985. A serious abstract algebra text. Where I learned Smith normal form.

A Course in Computational Algebraic Number Theory, Henri Cohen, Graduate Text in Mathematics 138, Springer, 1993. The bible in its field. Discusses Smith normal form.