Pseudo Cone Package

This package implements general simplicial complex software for the purpose of finding and studying pseudo cones.

  1. Quick Start
  2. User Interface
  3. Simplicial Complex Functionality
  4. Pseudo Cone Functionality
  5. Implementation Strategy
  6. Copyright

Quick Start

Download the Java jar file from http://www.ccs.neu.edu/home/kenb/pc.jar. Run the jar file using this command:

java -jar pc.jar
and the program will explain the command-line arguments.

The following are the command-line arguments:

  1. The number of (potential) vertices in each simplicial complex. A particular simplicial complex might not use all of the potential vertices. Vertices are numbered starting at 0.
  2. The maximum length of a simplex in a generated simplicial complex. The length is the number of vertices in a simplex, i.e., one more than the dimension.
  3. The number of maximal simplices in each simplicial complex.
  4. The initial number of trials per simplicial complex. A trial is one attempt to find a pseudo cone structure for a candidate simplicial complex. If not specified, then a default number is used.
  5. The number of simplicial complexes to generate randomly. If not specified then 10,000 simplicial complexes are generated.
  6. Optional name of a comma-delimited file where results are potential written.
  7. Optional seed for the random number generator. potential the Specifying the seed will ensure that the results are the same from one run to the next, provided that the other command-line parameters are the same.

Here is an example:

java -jar pc.jar 5 3 6 700 20000 results.csv
This will generate simplicial complexes with at most 5 vertices, with length 3, and with 3 maximal simplices. A total of 20,000 simplicial complexes will be generated with these properties. For each candidate for being a proper pseudo cone the program will try 700 times to find a pseudo cone structure before giving up. The statistics are printed both to the standard output and to the results.csv file.

User Interface

If you prefer to use a Graphical User Interface rather than the command line, then use this link: http://www.ccs.neu.edu/home/kenb/nupcf/. It will run a Java applet. The web page as instructions. The source code for the applet is available at http://www.ccs.neu.edu/home/kenb/nupcf/PseudoConeApplet.java.

Simplicial Complex Functionality

The {@link pc.SimplicialComplex} class provides general functionality for simplicial complexes. A simplex is specified using an integer in which the one bits are the vertices of the simplex. The number of vertices can be at most 31. A simplicial complex is specified by an array of maximal simplices. There are methods for testing whether a simplicial complex is connected, whether it has an even number of simplices, whether it is a cone (and returns a peak vertex if it is a cone), and whether it is a pseudo cone. Other useful methods are the computation of the link of a vertex and the subcomplex obtained by removing one vertex. There is also a method that tests whether there is a vertex that allows the simplicial complex to be link reduced.

Pseudo Cone Functionality

The {@link pc.PseudoCone} class provides an abstraction for the pseudo cone concept. The constructor tries to find a bijection (Hasse diagram matching) by attempting to arrange the simplices in pairs. The vertices are examined starting with the empty simplex and then proceeding up from one length to the next. Within each length, the simplices are examined in a random order. Each simplex is matched with a randomly selected simplex that covers it and that is not yet matched.

Note that while the bijections are selected randomly, it would not be correct to say that they are selected uniformly at random. The fact that the simplices are matched by levels does have an effect on the probability distribution of the bijections. On the other hand, within each level, the simplices are tested in an order that is uniformly random.

Implementation Strategy

As mentioned earlier, a simplex is specified using an integer in which the one bits are the vertices of the simplex. This limits the number of vertices to 32. The software actually limits the number to 31 to avoid problems with signs. One can increase the limit to 63 by using longs rather than ints.

Sets of simplices are implemented using hash sets. An alternative that was tried was to use bit sets. While bit sets improve performance somewhat, they use too much memory when the number of vertices is large. Since the improvement in speed is only about 10%, bit sets were not used.

Extensive profiling has shown that the main performance bottleneck is in the topological sort algorithm, not in the simplicial complex algorithms. So there is little to be gained by tuning the simplicial complex code.

The current implementation gives up the first time it is unable to continue adding to the matching. An alternative approach would be to use backtracking. However, this would essentially be searching the entire set of matchings, and the number of them increases very rapidly. Starting over each time searches the set of mappings more thoroughly.

Copyright

See {@link pc.Copyright} for the copyright notice. The copyright is specified using a Java annotation.