Monos Algebra Software

Mathematics Department

University of California, Davis

2005-05-08

1. OVERVIEW

Monos is a software system written in Java  for computing on monomial and binomial ideals. The software contains implementations of algorithms found in  and  for computations related to monomial and binomial ideals. In addition, monos contains a scripting language that uses R5RS Scheme .

This software was referenced last year in a presentation at ISSAC 2004  and has since been enhanced and released. The latest version is also available as a web-based application that can be used without installing any software.

2. COMPUTATIONS SUPPORTED

The following is a list of the major computations supports by monos:

• Computing the irreducible irredundant decomposition.

• Intersecting monomial ideals.

• Computing a binomial Gröbner basis given a generating set.

• Computing a Gröbner basis of a toric ideal.

In addition, there is a full complement of functions for manipulating the data produced with the scripting language.

3. EXAMPLES

A monomial ideal generating set can be listed directly as an expression in scheme. When the monomials are stored, they are stored as vectors. As such, a lexicographic ordering must be specified. The constructor monomial-ideal allows both the lexicographic ordering and the generators of the ideal to be specified in variable expression format:

```(monomial-ideal-with-order
(lex-order x1 x2 x3 x4)
(x1^2*x2 x1*x3*x4 x2^4*x3*x4^2 x3^3*x4^2))```

Within the Scheme-based scripting language, a lexicographic ordering is just another object in the language. As such, you can bind the lex order to a variable and re-use that ordering during computations. The monomial-ideal constructor also allows you to leave off the monomial ordering. When this is done, it expects the monomial ordering to be bound to the *lex-order* symbol in the environment as shown in the following example:

```(fluid-let ((*lex-order* (lex-order x1 x2 x3 x4)))
(intersect
(monomial-ideal x1  x2  x3*x4)
(monomial-ideal x1^2*x2  x1*x3*x4
x2^4*x3*x4^2  x3^3*x4^2)) )

```

In addition, mathematical objects can be read and written as scheme objects. For example, here is a simple program that decomposes an ideal read from a file and writes the result to program output:

```(let* ((file (vector-ref command-line-arguments 0))
(input (open-input-file file))
(write (decompose-ideal generators))

```

In fact, every mathematical object can be written by the Scheme write function such that it can be read in again. The Scheme read function allows a serialized object to be read and instantiated by the eval function. This treatment is consistent with Scheme's use of read and write for its own data structures.

A more complicated example is the following program that will post-process the decomposition of a monomial ideal for an integer gap computation. This program will only output the components where the generators have exponents greater than one:

```(let* ((file (vector-ref command-line-arguments 0))
(input (open-input-file file))
(ones
(list->monomial
(make-list
(dimension
(lex-order-ref components))
1)))
(size (java.util.List:size components)) )
(write
(do ((i 0
(if (monomial-divides?
(lcm (java.util.List:get components i))
ones)
(begin (invoke 'remove components i) i)
(+ i 1)) ))
((= i size) components) ) ) )

```

The scheme environment provided by the kawa  scheme implementation  provides the ability for Schema and Java to interact. This means that not only is all the R5RS functionality available within the environment but also all of Java and any Java library that exposes public APIs.

For example, this example creates a window that contains a label via the Java AWT library:

```(let ((frame (java.awt.Frame:new "My Application"))
(label (java.awt.Label:new "Math is Cool!")))
(java.awt.Frame:show frame))```

Finally, there is a full Java API for the core algorithms. This API can be used independently of the Scheme scripting language.

4. RELATED PROGRAMS

The monos software is currently integrated into a XML pipelining technology called smallx  as well as a P2P (peer to peer) computing environment based on JXTA  for distributed process. The smallx XML pipelining technology allows computations to be input as XML documents. This allows easy deployment as a web service or for integration into other web-based technologies.

The JXTA-based P2P software is for collaborative grid computing. The essential idea here is to use the XML-enabled form of the monos software to allow distributed processing. This version of the monos software allows processing to be distributed to unused computing power such in a computer lab or on a desktop computer at night. In contrast to other distributed computing environments, as a P2P technology, the computation is decentralized and runs on whatever resources "decide" to join a computation.

A test P2P grid will be deployed this summer (2005) between San Francisco State University and the author's servers.

5. ONLINE RESOURCES

Monos is available at:

and requires a Java 1.4.x environment to run.

Also, there is an online demonstration of the software that allows computing:

• the decomposition of a monomial ideal,

• the toric ideal Gröbner basis of a matrix,

• the Gröbner basis of a binomial ideal

• the Integer Gap for an Integer Programming problem.

all within a web form. Eventually, this application will be attached to the P2P grid to share its computational power.

This web application also has a set of web services available that mirror the web form functionality. In fact, the web forms are just interfaces to these web services.

For example, the following document can be sent to compute example 12.7 in :

```<compute-basis
xmlns="http://www.milowski.com/schemata/monos/2005"
monomial-order="lex">
<binomial-ideal>
<matrix>
<list>1 2 3 4 0 1 4 5</list>
<list>2 3 4 1 1 4 5 0</list>
<list>3 4 1 2 4 5 0 1</list>
<list>4 1 2 3 5 0 1 4</list>
</matrix>
</binomial-ideal>
</compute-basis>```

The result comes back as:

```<binomial-ideal xmlns='http://www.milowski.com/schemata/monos/2005'>
<matrix compact="true">
<list>0 0 0 4 0 -1 0 -3</list>
<list>0 0 4 0 -1 0 -3 0</list>
<list>0 1 0 -3 0 0 0 2</list>
<list>0 1 0 1 0 -1 0 -1</list>
<list>0 2 0 -2 0 -1 0 1</list>
<list>0 3 0 -1 0 -2 0 0</list>
<list>1 0 -3 0 0 0 2 0</list>
<list>1 0 1 0 -1 0 -1 0</list>
<list>2 0 -2 0 -1 0 1 0</list>
<list>3 0 -1 0 -2 0 0 0</list>
</matrix>
</binomial-ideal>
```

REFERENCES

1. R. Alexander Milowski, Computing Irredundant Irreducible Decompositions and the Scarf Complex of Large Scale Monomial Ideals, San Francisco State University, 2004
2. Bernd Sturmfels, Gröbner Bases and Convex Polytopes, American Mathematical Society, 1995
3. R. Kelsey, W. Clinger, J. Rees, Revised 5 Report on the Algorithmic Language Scheme, August 1998
4. R. Alexander Milowski, Computing Irredundant Irreducible Decompositions of Large Scale Monomial Ideals, ISSAC 2004, ACM, 235-242, 2004
5. Sun Microsystems, JXTA, http://www.jxta.org, 2005
6. R. Alexander Milowski, smallx, http://smallx.dev.java.net, 2005
7. Sun Microsystems, Java, http://www.sun.com/java, 2005
8. Per Bothner, Kawa: Compiling Scheme to Java, Lisp Users Conference, 1998
9. Per Bothner, Kawa Software, http://www.gnu.org/software/kawa/, 2005