
                           SHEAFHOM

                        Mark McConnell

Sheafhom 2.1 is a Common Lisp 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 "exact" domains of numbers,
especially the integers.  Sheafhom's back end solves the sparse
systems.

This abstract is long.  The section "The Talk" near the end summarizes
the proposed talk.

----- Sparse Linear Algebra over the Integers  -----

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,
though it is also a platform for research in pivoting strategies that
are 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.  There has been relatively little work in this area [1], so
Sheafhom fills a niche.

Sheafhom 2.x offers graphical tools to study fill-in and integer
explosion.  There are line graphs showing the growth of the sparsity
percentage and number of row/column operations.  More important,
Sheafhom can generate movies showing the sparsity pattern changing in
real time.  A sample movie is attached to this e-mail.

Sheafhom 2.1 has produced new results in a number theory research
project of Avner Ash, Paul Gunnells and the author.  The most recent
published results from this project are at [2].
 
----- Language Features -----

Sheafhom 1.x was developed in 1993-99 in Common Lisp.  During this
period I was a tenured professor pf mathematics at Oklahoma State
University and was the principal investigator on two NSF grants
funding Sheafhom.  Since 1999 I have been an algorithm and Java GUI
developer at WANDL, Inc.  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 combining CLOS with macros.

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

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.

A design decision in Sheafhom is that, above the lower levels, speed
will be less important than avoiding fill-in and integer explosion.
Some of the high-level algorithms in 2.1 (Lisp) are under development
compared to 2.0 (Java), and are theoretically slower [though the same
in space usage.]  Surprisingly, the two systems take about the same
time to solve the same large matrices.  I have confidence that "Lisp
is faster than Java" will be a fair statement, with the usual
qualifications (in my program, on my machine), once the slower
algorithms in 2.1 are replaced.

Sheafhom 2.1 was developed in Allegro 6.2.  Version 1.x used CMUCL.

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

----- 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.
The reason is that 1.x did not handle integers modulo n, and the front
end should be rewritten to fix this gap.  Nevertheless, 2.1 supports
good code for topology.  One example is the project with Ash and
Gunnells.  As another example, the file two-complex.lisp has demo code
for the topology of 2-manifolds: spheres, tori, Klein bottles, and the
like.  The spaces are made by gluing triangles together along their
edges.  They have features (torsion in the homology group H_1) that
call for integer computations as opposed to floating-point.

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 Talk -----

The talk would focus on the back end, since that's probably more
interesting to the ILC audience than high-dimensional topology.  It
would present

[.] sparse matrix theory (fill-in, integer explosion)
[.] sparse data structures (Lisp versus Java)
[.] the macro mini-languages
[.] demonstrations with the tori and Klein bottles.  One idea is for a
    graphic demo with a space made of triangles lying on the floor,
    folded up.  Sheafhom can distinguish the inside of the space from
    the outside.  A physics model in Lisp would inflate the inside, so
    we would see a torus blowing up on the screen in a Java window.
    You can't inflate a Klein bottle, since it doesn't live in three
    dimensions, but another demo could draw its H_1 and show what
    torsion means.

Sheafhom 1.x, 2.0 and 2.1 are available at
http://www.geocities.com/mmcconnell17704/math.html

----- Footnotes -----

[1] Some authors approach sparse integer matrices by working modulo a
prime p, which eliminates integer explosion.  Using several p's, one
can reconstruct the integer result at the end.  One can solve the
mod-p matrices with Lanczos methods mod p; these are iterative methods
which introduce no fill-in at all.  Sheafhom may go in this direction
in the future--in fact, the paper [2] used Lanczos mod p.  However,
Sheafhom 2.x does not use these methods, because they are indirect and
can be very slow.

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

[3] Sheafhom 2.0 stored sparse vectors in Java's ArrayList, an
array-backed object.  Lisp lists have overhead compared to an array,
of course--the size of the conses.  But there is evidence that lists
perform not so differently from ArrayList because of paging
considerations.  You don't have to allocate large arrays all in one
place; linked lists break more easily across several pages.  More work
is necessary to verify these statements.
