Ruffini – abstract algebra in Java

Class inheritance and generics/templates makes it possible to write code with nice abstractions very similar to the abstractions used in math, particularly in abstract algebra, where a computation can be described for an entire class of algebraic structures sharing some similar properties (eg. groups and rings). This has been described nicely in the book “From Mathematics to Generic Programming” by Alexandra A. Stepanov and Daniel E. Rose.

Inspired by this book, I have implemented a library for computations on algebraic structures called Ruffini using Java generics to get the same kind of abstraction that is used in abstract algebra, eg. that you do not specify what specific algebraic structure is used, only that is eg. a group or a ring.

Abstract algebraic structures are defined by a number of interfaces extending each other, the simplest being a semigroup:

public interface Semigroup<E> {

  /**
   * Return the result of the product <i>ab</i> in this 
   * semigroup.
   * 
   * @param a
   * @param b
   * @return
   */
  public E multiply(E a, E b);

}

The semigroup is extended by a monoid interface which adds a getIdentity() method and by a group interface which adds an invert(E) method etc. Continuing like this we get end up with interfaces for more complicated structures like rings, fields and vector spaces.

Now, each of these interfaces describes functions that can be applied to a generic type E (eg. that given two instances of E, the multiply method above returns a new instance of type E). As in abstract algebra, these functions can be used to describe complicated computations without specifying exactly what algebraic structure is being used.

Ruffini currently implements a number of algorithms that is defined and described for the abstract structures, including the discrete Fourier transform, the Euclidean algorithm, Gröbner bases, the Gram-Schmidt process and Gaussian elimination. The abstraction makes it possible to write the algorithms only once, while still being usable on any of the algebraic structures defined in the library, including integers, rational numbers, integers modulo n, finite fields, polynomial rings and matrix rings. Below is the code for the Gram-Schmidt process:

public List<V> apply(List<V> vectors) {
  List<V> U = new ArrayList<>();

  Projection<V, S> projection = new Projection<>(vectorSpace, innerProduct);
  for (V v : vectors) {
    for (V u : U) {
      V p = projection.apply(v, u);
      v = vectorSpace.subtract(v, p);
    }
    U.add(v);
  }
  return U;
}

Here V and S are the generic types for resp. the vectors and scalars of the underlying vector space, and Projection is a class defining projection given a specific vector space and an inner product. Note that the vector space has a subtract method which subtracts two vectors. Now, the above algorithm can be executed on any of the vector spaces defined in Ruffini.

The library is can be downloaded from GitHub: https://github.com/jonas-lj/Ruffini.