

        SHEAFHOM 2.1 User Manual         Release: March 17, 2005

                             Mark McConnell



INSTALLATION GUIDE

Please see README.txt in the shh21 directory.



INTRODUCTION

Please see abstract.txt in the shh21 directory.



------------------------------ macros.lisp ------------------------------

Note: aif, awhen, till and with-gensyms are from _On Lisp_ by Paul Graham.

----------

AIF (test-form then-form &optional else-form)                       [MACRO]
   Anaphoric if.

AWHEN (test-form &body body)                                        [MACRO]
   Anaphoric when.

DOTIMES-F ((i n &optional ans) &body body)                          [MACRO]
   Dotimes for fixnums: declare i and n fixnum, i >= 0.

TILL (test &body body)                                              [MACRO]

WITH-GENSYMS (syms &body body)                                      [MACRO]

WITH-SPLICER (place &body body)                                     [MACRO]
   A mini-language for surgery on lists.  'place' should evaluate to a
   proper list (a ... b y ...).  The splicer has a head that starts from
   the first element of the list and runs forward.  (In the examples
   below, the head is at y.)  The macro sets up the following forms, of
   which the last five destructively modify the underlying list.
   Throughout, 'place' always evaluates to the modified list.  Calls to
   with-splicer can be nested.
   [.] (splicer-read) => return the element y currently under the head
   [.] (splicer-tail) => return the sublist (y ...)
   [.] (splicer-fwd) => move the head forward
   [.] (splicer-endp) => true iff there are no more elements
   [.] (splicer-insert x) => insert x before y; reposition the head at x
   [.] (splicer-modify x) => replace y with x; leave the head there
   [.] (splicer-delete) => delete y, putting the head at the next position
   [.] (splicer-nconc l) => discard (y ...); nconc l onto the end
                            of (... b); put head at start of l
   [.] (splicer-split) => reset place to the front sublist (a ... b), and
                          return three values:
                            the front sublist
                            last cons (b) of front [nil if front is empty]
                            the tail (y ...)

------------------------------ gui.lisp ------------------------------

This file runs a graphical utility to show a simple line graph.
It also offers a "csparse window" [csw]; as a sparse matrix is
reduced, the window displays the changing sparsity pattern.  The
implementations here are specific to Allegro CL.  They link to
Java using Allegro's jlinker.

HOW TO USE THIS FILE gui.lisp
[.] If you don't have Allegro CL, jlinker or Java, or simply don't
    need to use the GUI features, please COMMENT OUT everything
    above the line marked "NO GUI", and uncomment everything below
    that line.
[.] If you do have Allegro CL, jlinker and Java, please edit the
    lines marked EDIT to match your installation.

----------

SHOW-LINE-GRAPH (v title &optional (max-points (length v)))      [FUNCTION]
   Display a line graph with y-coordinates from the vector of
   numbers v.  The number of points is the lesser of max-points and
   the length of v.

*CSW* (nil)                                                      [VARIABLE]
   A 'csparse window' showing the changing sparsity pattern of
   a csparse as it is reduced.

CSW-INIT (title m n)                                             [FUNCTION]
   Create a new csw and show it.

CSW-SET-CORNER (corner)                                          [FUNCTION]
   Sets the boundary of the active region in the csw, if a csw exists.

CSW-SET-NOTE (note)                                              [FUNCTION]
   Sets a text note in the csw, if a csw exists.

CSW-SET-YELLOW (a b)                                             [FUNCTION]
   Paints the csw yellow in columns a to b, if a csw exists.

CSW-SET-COUNTER (counter)                                        [FUNCTION]
   Resets the painted portion of the csw, if a csw exists.

CSW-IS-ACTIVE ()                                                 [FUNCTION]
   Whether the csw exists and is the active window.

------------------------------ csparsez.lisp ------------------------------

Sparse linear algebra code over an arbitrary integral domain D.
In this file it is specialized to one particular D, the integers
(D = Z), but it can be specialized to other D's as follows:
(1) redefine what's in the first section bounded by === lines.
(2) leave unchanged what's in the second section of ==='s.
(3) completely replace the third section.

D's that could be implemented include finite fields, polynomials
in one variable over Q, or the ring of integers in a number field
of class number 1.

Immediate parent: Sheafhom II (Sheafhom 2.0), Java, 2003-2004.
Grandparent: Sheafhom, Lisp, 1993-1999.
These are at http://www.geocities.com/mmcconnell17704/math.html
Earlier: various Lisp programs starting from 1986.
"Book of J" source: APL code for jac from the early 1980s,
first used for a published paper at Epiphany 1985.

The code has careful declarations so that optimizing 'speed' will
have a large effect.

----------

NNFIXNUM NIL `(integer 0 ,most-positive-fixnum)                      [TYPE]
   The type of a non-negative fixnum [single-precision integer].

====================

In this first section of ==='s, the documentation is a contract
for all D's, mixed together with implementation notes for D = Z.

----------

SPARSE-ELT NIL 'cons                                                 [TYPE]
   A sparse-elt is an element of a sparse vector (see sparse-v).
   It holds two pieces of data, an index in the sparse-v and a value
   in the integral domain D.
    Over any D, a sparse-elt should be immutable.  The value may be
   zero, but it is an error if a sparse-elt with value zero becomes an
   element of a sparse-v.  nil must not be sparse-elt.  equalp must
   test whether two sparse-elts have the same index and the same value.
    In this implementation over Z, a sparse-elt is just a cons whose
   car is the fixnum index and whose cdr is the integer value.

SP-I (elt)                                                          [MACRO]
   The index of a sparse-elt in a sparse vector (see sparse-v). It
   must be non-negative, or negative to mean 'unspecified'.  It must be
   a fixnum [single-precision integer].

SP-V (elt)                                                          [MACRO]
   The value of a sparse-elt.  In this implementation, it is an integer.

MAKE-SP (index value)                                               [MACRO]
   Creates a sparse-elt.

SP-NEG-ONE-P (x)                                                    [MACRO]
   Whether the value is -1.

SP-ONEP (x)                                                         [MACRO]
   Whether the value is 1.

SP-ZEROP (x)                                                        [MACRO]
   Whether the value is 0.

SP-UNITP (x)                                                        [MACRO]
   Whether the value is a unit in D.

+SP-ZERO+ ('(-1 . 0))                                            [CONSTANT]
   A sparse-elt of unspecified index and value 0.

+SP-ONE+ ('(-1 . 1))                                             [CONSTANT]
   A sparse-elt of unspecified index and value 1.

+SP-NEG-ONE+ ('(-1 . -1))                                        [CONSTANT]
   A sparse-elt of unspecified index and value -1.

SP-BINARY-OP (f x y &rest new-ind)                                  [MACRO]
   Expands to a function taking two sparse-elts x, y and returning a
   sparse-elt.  f should be + if the function is addition, etc.  The
   index of the result is the optional fourth argument, or is the index
   of x if there is no fourth argument.

SP-ADD (x y &rest new-ind)                                          [MACRO]
   Sum of two sparse-elts.  See sp-binary-op for details.

SP-SUBTRACT (x y &rest new-ind)                                     [MACRO]
   Difference of two sparse-elts.  See sp-binary-op for details.

SP-MULT (x y &rest new-ind)                                         [MACRO]
   Product of two sparse-elts.  See sp-binary-op for details.

SP-DIVIDES (x y)                                                    [MACRO]
   Whether there is a c in D such that c * x = y.  Assumes x is
   non-zero. 

SP-= (x y)                                                          [MACRO]
   Whether the values are equal in the domain D.  Note: equalp
   tests for equality of index and value simultaneously.

SP-NEGATE (x)                                                       [MACRO]
   Returns a sparse-elt with x's index and the negative of its value.

SP-EUC-NORM (x)                                                     [MACRO]
   The Euclidean norm of a sparse-elt.

SP-NEG-CLOSEST-QUOTIENT (x y)                                       [MACRO]
   Returns q such that q * y + x is as small as possible
   for sp-euc-norm.  In other words, returns -x/y rounded to
   the nearest element of D.  The index of q is that of x.

SP-DIVIDED-BY (x y)                                              [FUNCTION]
   Returns x/y exactly, with index that of x.

DENSE-MATRIX NIL '(array integer 2)                                  [TYPE]
   The type of m-by-n arrays specialized to the values in this D.

MAKE-DENSE-MATRIX (m n)                                          [FUNCTION]
   Makes a dense-matrix of size m-by-n with all entries 0.

====================

SP-COPY (x new-ind)                                              [FUNCTION]
   Returns a sparse-elt with x's value and index new-ind.

INTEGRITY-CHECK (a &optional arg1)                       [GENERIC FUNCTION]
   Signals an error if a has internal errors.  Otherwise does nothing.

SPARSE-V NIL 'list                                                   [TYPE]
   A sparse-v is a proper list of sparse-elts representing a vector
   over the integral domain D.  The i-th entry in the vector is the
   value of the sparse-elt whose index is i.  The sparse-elts must have
   distinct non-negative indices and be sorted in order of increasing
   index.  A sparse-elt with zero value must never appear in a sparse-v.
    A sparse-v must never share top-level list structure with another
   list, because we often destructively modify the top-level structure,
   as in with-splicer.
    Note: two sparse-v's are mathematically equal iff they are equalp.

INPUT-SPARSE-V (lyst)                                            [FUNCTION]
   Convert a dense list to a sparse-v.
   Example: (input-sparse-v '(17 0 19)) has value 17 at index 0 and
   19 at index 2.

V-ADD (a b)                                                      [FUNCTION]
   Given sparse-v's a and b, destructively alters a to hold their sum.
   Returns the altered a.  Does not alter b.

V-ADD-NONDESTR (a b)                                             [FUNCTION]
   Returns the sum of the sparse-v's a and b, but, unlike v-add, alters
   neither a nor b.

V-SCALAR-MULT (a fac)                                            [FUNCTION]
   Destructively alters the sparse-v a to hold its scalar multiple by
   the value in fac.  Returns the altered a.

V-NEGATE (a)                                                     [FUNCTION]
   Destructively alters the sparse-v a to hold its scalar multiple
   by -1.  Returns the altered a.

V-ALTER (a fac b)                                                [FUNCTION]
   Given sparse-v's a and b, destructively alters a to hold a + c * b,
   where c is the value in fac.  Returns the altered a.  Does not alter
   b.  Assumes D is an integral domain, so that the product of non-zero
   values is non-zero.

V-ALTER-ELT (a i1 fac i2)                                        [FUNCTION]
   Alters the i1-th entry of a by adding to it [value of fac] times
   [value of the i2-th entry of a].  Returns the altered a.  Assumes D
   is an integral domain, so that the product of non-zero values is
   non-zero.

V-NEGATE-ELT (a i)                                               [FUNCTION]
   Negates the i-th element of the sparse-v a.  Returns the altered a.

V-SWAP (a i1 i2)                                                 [FUNCTION]
   Destructively alters the sparse-v a by swapping the i1-th and
   i2-th entries.  Returns the altered a.

V-DOT (a b)                                                      [FUNCTION]
   Returns a sparse-elt whose value is the dot product of a and b.

V-GET (a i)                                                      [FUNCTION]
   Returns the sparse-elt of index i in the sparse-v a, or nil if
   the value is zero there.

V-SET (a i new-elt)                                              [FUNCTION]
   Destructively alters the sparse-v a so the i-th elt has the
   value of new-elt.  Returns the altered a.

V-ZEROP (a)                                                      [FUNCTION]
   Whether the sparse-v a is the zero vector.

V-SINGLETON-P (a)                                                [FUNCTION]
   Whether the sparse-v a has exactly one non-zero element.

INTEGRITY-CHECK ((a t) &optional m)                                [METHOD]
   If a is a sparse-v, then m is the dimension of a vector space
   containing a, or nil if the dimension is unknown.

CSPARSE (m n cols)                                              [STRUCTURE]
   A csparse is a sparse m-by-n matrix over the integral domain D.
   The j-th column is the sparse-v held in the j-th entry of cols.
    Note: two csparse's are mathematically equal iff they are equalp.

MAKE-CSPARSE-ZERO (m n)                                          [FUNCTION]
   Constructs an m-by-n csparse with all entries 0.

INPUT-CSPARSE (m n entries)                                      [FUNCTION]
   Returns an m-by-n csparse whose entries run through the list
   'entries' in row-major order.  If the list is too short, we reread
   it cyclically, in the spirit of APL's ravel function (rho).

WITH-CSPARSE-SLOTS (slots var &body body)                           [MACRO]
   Version of with-slots for csparse, including type declarations.

CSPARSE-COPY (a)                                                 [FUNCTION]
   Returns a copy of the csparse a, sharing no structure with a itself.

PRINT-OBJECT ((a csparse) s)                                       [METHOD]

ALTER-COL (a j1 fac j2)                                          [FUNCTION]
   In the csparse a, applies v-alter to the indicated columns.  Returns
   a. 

ALTER-ROW (a i1 fac i2)                                          [FUNCTION]
   Like alter-col, but operates on the indicated rows.

SWAP-COLS (a j1 j2)                                              [FUNCTION]
   In the csparse a, interchanges the indicated columns.  Returns a.

SWAP-ROWS (a i1 i2)                                              [FUNCTION]
   In the csparse a, interchanges the indicated rows.  Returns a.

NEGATE-COL (a j)                                                 [FUNCTION]
   In the csparse a, multiplies column j by -1.  Returns a.

NEGATE-ROW (a i)                                                 [FUNCTION]
   In the csparse a, multiplies row i by -1.  Returns a.

SPARSITY (a &optional (corner 0) (northeast-zero-p t))           [FUNCTION]
   Finds the ratio (number of non-zero entries)/(total number of
   entries) in the southeast region [corner,m)-by-[corner,n) of the
   csparse a.  Returns it as a float between 0 and 1.  Columns with all
   0's in the southeast region are not counted.  When northeast-zero-p
   is true [the default], we know in advance that the northeast region
   [0,corner)-by-[corner,n) is all 0's, as it is in jac.

MAKE-ZERO-AND-ID (m n i0 j0 s)                                   [FUNCTION]
   Returns an m-by-n csparse with all 0's except that the square
   block starting at i0,j0 and of side s has 1's on the diagonal.

CSPARSE-ADD (a1 a2)                                              [FUNCTION]
   Returns the sum of the csparses a1 and a2.  Doesn't alter a1 and a2.

CSPARSE-GET (a i j)                                              [FUNCTION]
   Returns the sparse-elt giving the i,j-th entry of the csparse a,
   or nil if the value is zero there.

DO-ROWS-CSPARSE ((row-var a &optional end-form) &body body)         [MACRO]
   Executes its body for i = 0, 1, ..., with row-var bound to a
   sparse-v holding the i-th row of the csparse a.

M-MULT (a b)                                             [GENERIC FUNCTION]
   Returns the matrix product a * b.  Check the defmethods for details.

M-MULT ((a csparse) (b csparse))                                   [METHOD]
   Returns the csparse a * b.  Doesn't alter a or b.

CSPARSE-PRODUCT-ZEROP (a b)                                      [FUNCTION]
   Whether the product a * b of csparses is zero.  Doesn't store a * b.

M-NUM-COLS (a)                                           [GENERIC FUNCTION]
   The number of columns in the matrix a.

M-NUM-COLS ((a csparse))                                           [METHOD]

M-NUM-ROWS (a)                                           [GENERIC FUNCTION]
   The number of rows in the matrix a.

M-NUM-ROWS ((a csparse))                                           [METHOD]

CSPARSE-SET (a i-and-val j)                                      [FUNCTION]
   Destructively alters the csparse a so the i,j-th elt has value v,
   where i-and-val equals (sp-make i v).  Returns the altered a.

CSPARSE-ZEROP (a)                                                [FUNCTION]
   Whether the csparse a is the zero matrix.

M-TRANSPOSE (a)                                          [GENERIC FUNCTION]
   Returns the transpose of the matrix a.  Check defmethods for details.

M-TRANSPOSE ((a csparse))                                          [METHOD]
   Returns the transpose of the csparse a.  Destroys a in the process.

INTEGRITY-CHECK ((a csparse) &optional arg1)                       [METHOD]

TO-COUNTER (a delta width height counter)                        [FUNCTION]
   Helper method for csw-set-counter.  Overwrites counter to show a's
   sparsity pattern.  counter is a one-dimensional array storing a
   width-by-height rectangular array of numbers in column-major order.
   We count the number of non-zeroes in each delta-by-delta submatrix of
   a, and write the number into the corresponding entry of counter.

M-INVERSE (a)                                            [GENERIC FUNCTION]
   The inverse of a.

M-INVERSE-TRANSPOSE (a)                                  [GENERIC FUNCTION]
   The inverse-transpose of the matrix a.

PERM2 (i1 i2)                                                   [STRUCTURE]
   A permutation matrix: the identity, but with columns i1 and i2
   swapped. 

WITH-PERM2-SLOTS (var &body body)                                   [MACRO]
   Version of with-slots for perm2, including type declarations.

PRINT-OBJECT ((e perm2) s)                                         [METHOD]

M-INVERSE ((e perm2))                                              [METHOD]

M-INVERSE-TRANSPOSE ((e perm2))                                    [METHOD]

M-MULT ((e perm2) (a csparse))                                     [METHOD]
   Destructively modifies a by swapping rows i1 and i2.

M-MULT ((a csparse) (e perm2))                                     [METHOD]
   Destructively modifies a by swapping columns i1 and i2.

M-TRANSPOSE ((e perm2))                                            [METHOD]

INTEGRITY-CHECK ((e perm2) &optional n)                            [METHOD]

TRANSV (i j v)                                                  [STRUCTURE]
   A transvection matrix: the identity, but with an entry v at i,j.

WITH-TRANSV-SLOTS (var &body body)                                  [MACRO]
   Version of with-slots for transv, including type declarations.

PRINT-OBJECT ((e transv) s)                                        [METHOD]

M-INVERSE ((e transv))                                             [METHOD]

M-INVERSE-TRANSPOSE ((e transv))                                   [METHOD]

M-MULT ((e transv) (a csparse))                                    [METHOD]
   Destructively modifies a by adding v times row j to row i.

M-MULT ((a csparse) (e transv))                                    [METHOD]
   Destructively modifies a by adding v times column i to column j.

M-TRANSPOSE ((e transv))                                           [METHOD]

INTEGRITY-CHECK ((e transv) &optional n)                           [METHOD]

CSPARSE-MOVE-FROM-DENSE (ca da i0 i1 j0 j1)                      [FUNCTION]
   Destructively replaces a rectangular block of the csparse ca with
   the contents of the dense-matrix da.  The block is
   i0 <= i < i1, j0 <= j < j1.

CSPARSE-MOVE-TO-DENSE (ca i0 i1 j0 j1)                           [FUNCTION]
   Destructively removes a rectangular block of the csparse ca,
   putting the entries into a dense-matrix and returning the latter.
   The block is i0 <= i < i1, j0 <= j < j1.

TIME-STAMP "()"                                                  [FUNCTION]
   Returns 03:05:17 to mean 17 seconds after 3:05 a.m.

*SHOW-PROG* (nil)                                                [VARIABLE]
   If true while reducing a csparse, print timing data to std output.

*SHOW-STATS* (nil)                                               [VARIABLE]
   If true while reducing a csparse, pop up graphs of the changing
   sparsity and number of elementary matrices.

*SHOW-CSW* (nil)                                                 [VARIABLE]
   If true while reducing a csparse, show the sparsity pattern in real
   time.  [This may slow down the computation.]

*USE-MARKOWITZ* (t)                                              [VARIABLE]
   If true, use the pure Markowitz pivoting algorithm.  If false,
   use the 'sort to lower right, then greedy' algorithm of the author.

*MARKOWITZ-RLEN* (nil)                                           [VARIABLE]
   Scratch space for the Markowitz algorithm.

*MARKOWITZ-CLEN* (nil)                                           [VARIABLE]
   Scratch space for the Markowitz algorithm.

*ALLOW-LLL* (nil)                                                [VARIABLE]
   If true, permit Lenstra-Lenstra-Lovasz while reducing a csparse.

*LLL-WIDTH* (200)                                                [VARIABLE]
   Use Lenstra-Lenstra-Lovasz on strips of columns up to this wide.

*LLL-THRESHOLD* (0.1)                                            [VARIABLE]
   Permit Lenstra-Lenstra-Lovasz when sparsity > this number.

*LLL-NEXT-TRY* (50)                                              [VARIABLE]
   After one Lenstra-Lenstra-Lovasz, don't do another until the
   active region has moved over this many columns.

SNF ""                                                              [CLASS]
   Holds the Smith normal form of a csparse.  Documented at make-snf.
   Superclasses
   None.
   Initialization Arguments
   The :mat argument is a (or csparse null)
   The :d argument is a csparse
   The :use-p argument is a 
   The :use-q argument is a 
   Readers
   Writers

MAKE-SNF ((mat csparse) &optional (use-p t) (use-q t)              [METHOD]
          (destructive-p nil))
   Finds the Smith normal form of mat, a csparse over the integral
   domain D, while aiming to avoid fill-in and entry explosion.
    The Smith normal form is
          mat = p d q.
   Here p and q are square matrices over Z of determinant +/- 1 [hence
   invertible over D].  They are represented by an snf's slots p-list
   and q-list, which are lists of elementary matrices--instances of
   perm2 and transv.  p is the product of the matrices in p-list, and q
   the product for q-list, both in the usual left-to-right order.  The
   matrix d, held as a csparse in an snf's slot d, is a diagonal matrix
          d = diag(d0, d1, d2, ...),
   over D, where d0 is a divisor of d1, d1 is a divisor of d2, and so on
   for all dj and d(j+1).  Possibly dk = d(k+1) = ... = 0 for some k.
   The dj's are called the elementary divisors.
    The optional arguments to make-snf can save space with large
   csparses.  If use-p is nil, the matrices in p-list are not computed.
   Ditto for use-q and q-list.  If destructive-p is nil, the original
   matrix is preserved in mat, and the reduction steps work on a copy;
   if destructive-p is true, the original matrix is destroyed during the
   reduction.
    make-snf fires the Smith normal form computation automatically. 
   The algorithm is in the function jac and the various pivot functions
   it calls.
    By changing the following flags, the user can specify different
   forms of the algorithm.  See the documentation on the flags.
   *use-markowitz*
   [if D = Z] *allow-lll* *lll-width* *lll-threshold* *lll-next-try*
    Use the following flags to view graphs and windows that show the
   progress of the computation.
   *show-prog* *show-stats* *show-csw*

JAC (a)                                                          [FUNCTION]
   The main algorithm for Smith normal form computations.  The author
   calls this method jac because he learned it as Theorem 3.8 of Basic
   Algebra I by Nathan Jacobson.

RANK ((a snf))                                                     [METHOD]
   The rank of a over the field of fractions of D.  For instance, if D
   = Z, this is the rank over Q or R.  It is the number of non-zero
   elementary divisors in the snf.

NUM-UNITS ((a snf))                                                [METHOD]
   The number of units among the elementary divisors of a.

TORSION ((a snf))                                                  [METHOD]
   A list of the non-units among the elementary divisors of a.

KER ((a snf))                                                      [METHOD]
   Returns a csparse whose columns are a D-basis for the kernel of a.

KER-RETRACTION ((a snf))                                           [METHOD]
   Returns a csparse that's a retraction for (ker a).  That is, the
   retraction has linearly independent rows, and the product
   (ker-retraction a) * (ker a) is the identity.  [The product the other
   way around need not be.]

M-NUM-COLS ((a snf))                                               [METHOD]

M-NUM-ROWS ((a snf))                                               [METHOD]

PRINT-OBJECT ((a snf) s)                                           [METHOD]

INTEGRITY-CHECK ((a snf) &optional (orig (slot-value a 'mat)))     [METHOD]
   orig should be a copy of the original csparse.  It can be omitted
   if the snf was built non-destructively.

====================

PIVOT (d corner use-q last-lll)                                  [FUNCTION]
   Finds the next pivot for jac to use.  The algorithm is affected
   by several of the global variables.  Returns three values,
   i j val, or 0 0 nil.

PIVOT-METHOD "()"                                                [FUNCTION]
   A short string describing what (pivot ...) does.

PIVOT-GREEDY (cols corner)                                       [FUNCTION]
   Helper for (pivot ...).

SORT-BY-UTMARKOWITZ (cols corner)                                [FUNCTION]
   Sort cols, an array of sparse-v's, by number of non-zero entries.
   Break ties by putting to the left the sparse-v whose first index is
   *bigger*.  The result looks like several upper-triangular strips,
   reflected in the y-axis...hence the 'ut'.

V-NORM-SQ (v)                                                    [FUNCTION]
   The square of the norm of a sparse-v, as a double-float.  Assumes
   the integral domain D is a subring of the real numbers.

SORT-BY-NORM-SQ (cols corner)                                    [FUNCTION]
   Sort cols, an array of sparse-v's, by increasing v-norm-sq.

PIVOT-MARKOWITZ (d corner)                                       [FUNCTION]
   A pure Markowitz algorithm for pivoting.

HIT-WITH-LLL (d corner)                                          [FUNCTION]
   Perform Lenstra-Lenstra-Lovasz on successive vertical strips,
   of width up to *lll-width*, overwriting d with the results.

DO-LLL (a)                                                       [FUNCTION]
   Does LLL reduction on the columns of the dense-matrix a,
   destructively, using Algorithm 2.7.2 in Henri Cohen's book.  Returns
   'kerdim', the dimension of the kernel.  On exit, the columns >= the
   kerdim-th are a Z-basis of the lattice generated by the columns of
   the input.

DENSE-COL-DOT (a j0 j1 m)                                        [FUNCTION]
   Dot product of columns in the dense-matrix a.

DENSE-COL-SWAP (a j0 j1 m)                                       [FUNCTION]
   Interchange columns in the dense-matrix a.

DENSE-REDI (a k l m d lam)                                       [FUNCTION]
   Helper for do-lll.

-------------------- two-complex.lisp --------------------

Programs to study the topology of two-complexes.

A simplex is a list of distinct integers sorted by <.  An
n-dimensional simplex (or n-simplex) has n+1 elements.  This
package uses 0-simplices (vertices), 1-simplices (edges), and
2-simplices (triangles).

A polygon is a list of three or more distinct integers.
For instance, (0 1 2 3) is this square:
0 - 1
|   |
3 - 2
The code automatically splits the square into two 2-simplices:
0 - 1
| \ |
3 - 2

SX-BOUNDARY (sx)                                                 [FUNCTION]
   Lists all the (i-1) dimensional faces of the i-simplex sx.
   The usual orientation convention for simplicial complexes
   holds: the orientation of the j-th face in the list is (-1)^j.

TRIANGULATE-POLYGON (polygon &optional (ans 'nil))               [FUNCTION]

TWO-COMPLEX ""                                                      [CLASS]
   A two-complex is built by gluing vertices, edges and
   polygons together along their faces.  Examples include
   the surfaces of the sphere, torus, and Klein bottle.  Use
   make-two-complex to construct a two-complex.  The complex
   computing the homology is
   C_0 <-- d1 -- C_1 <-- d2 -- C_2.
   Superclasses
   None.
   Initialization Arguments
   Readers
   Writers

*TORUS-CELLS* ((list '(6 7 1 0) '(7 8 2 1) '(8 6 0 2) '         [PARAMETER]
               (3 4 7 6) '(4 5 8 7) '(5 3 6 8) '(0 1 4 3) '
               (1 2 5 4) '(2 0 3 5)))
   Sample data: (make-two-complex *torus-cells*) gives
   a torus.

*KLEIN-BOTTLE-CELLS* ((list '(6 7 2 0) '(7 8 1 2) '(8 6 0 1)    [PARAMETER]
                      '(3 4 7 6) '(4 5 8 7) '(5 3 6 8) '
                      (0 1 4 3) '(1 2 5 4) '(2 0 3 5)))
   Sample data: (make-two-complex *klein-bottle-cells*) gives
   a Klein bottle.

*SPHERE-CELLS* ((sx-boundary '(0 1 2 3)))                       [PARAMETER]
   Sample data: (make-two-complex *sphere-cells*) gives
   a sphere.

MAKE-TWO-COMPLEX (cells)                                         [FUNCTION]
   Cells is a list of items to be glued together to make a
   two-complex.  An length-1 list is a 0-simplex [vertex].  A length-2
   list is a 1-simplex [edge].  A length-3 list is a 2-simplex
   [triangle].  A length-n list is an n-sided polygon, which is
   automatically divided into 2-simplices.  The return value is a
   two-complex data structure.  Note: this method modifies the top-level
   structure of 'cells'.

D1 ((cx two-complex))                                              [METHOD]
   The map from simplicial 1-chains to 0-chains, as an snf.

D2 ((cx two-complex))                                              [METHOD]
   The map from simplicial 2-chains to 1-chains, as an snf.

MAKE-D ((cx two-complex) (i fixnum))                               [METHOD]
   The user should call d1 and d2, not this method.

PRINT-HOMOLOGY ((cx two-complex) &optional (stream t))             [METHOD]
   Prints to stream the ranks and torsion coefficients of the
   homology H_*(cx, Z) of the two-comples cx.

------------------------------------------------------------

[Manual prepared with user-manual.lisp by Mark Kantrowitz et al.]

