Algebraic Hierarchy

Oftentimes, we want to create generic operations that can operate on many different types. For instance, we might want to sum up all the elements in a Vector, or we might want to make an algorithm that can find the minimum of a function in a generic way that works for DenseVectors, SparseVectors, Doubles, or even GPU types like Gust's CuVector. In Breeze, we use the typeclass pattern to achieve this, using concepts from abstract algebra as our guide. That possibly sounds scarier than it really is.

Breeze has a fairly elaborate algebraic hierarchy. It is not as complete as Spire's in many ways, but it handles many purposes quite well. We have organized them into two groups: those that are mostly associated with scalar types (like Fields) and those that are associated with Vector types (like VectorSpaces). Note that we actually also provide Rings and Fields for certain vector-y types (notably Vectors, DenseVectors, and SparseVectors), and we also (XXX do we still?) provide VectorSpaces for scalar-y types, e.g. by turning a Field into a VectorSpace (of dimension 1). Nevertheless, we usually think about these types as being separated between Vectors and Scalars.

Using the Algebraic Hierarchy

XXX talk about implicits and sums, etc.

Scalar Types

Types like Semiring and Field provide generic facilities for dealing with scalar types like Double, Int, Complex, and Boolean.

Semiring

The root of the algebraic hierarchy for scalar types is currently the Semiring, which has the following definition:

trait Semiring[V] {
  def zero : V
  def one : V

  def +(a : V, b : V) : V
  def *(a : V, b : V) : V

  def ==(a : V, b : V) : Boolean
  def !=(a : V, b : V) : Boolean
  def close(a: V, b: V, tolerance: Double=1E-4):Boolean = a == b
}

Semirings provide addition and multiplication along with their identities. Addition is associative and commutative, and multiplication is associative and distributes over addition. (Spire calls semirings "Rigs", which is a nonstandard name.) See the Wikipedia entry for more information.

Ring

A Ring adds negative values: every v has an additive inverse -v such that v + -v = zero.

Field

A Field adds division: every v now also has a multiplicative inverse one / v such that v * one / v == one. In addition, multiplication must be commutative. The Real numbers and Complex numbers both have fields. We abuse terminology and make Ints and other integer types into Fields, even though they're not actually fields. (They have division, and we didn't feel like making another type.)

Vector Types

For algorithms and operations that operate at the level of Vectors, we have another set of type classes. XXX Nearly all of these type classes also have mutable variants: many algorithms are more efficiently written using mutation. Note, however, that we can turn most immutable type classes (e.g. VectorSpace) into their mutable equivalents (e.g. MutableVectorSpace) using the MutabilizingAdaptor, which wraps a VectorSpace to make it appear to be mutable.

VectorSpace

A VectorSpace is the typeclass you're most likely to have seen. VectorSpaces are over a scalar type S and a vector type V. The scalar type must have a Field, and the vectors have to interact in particular ways, notably that you have to be able to add vectors, and you have to be able to multiply a vector by a scalar. The operations are defined like so:

// Vector Spaces
trait VectorSpace[V, S] extends Module[V, S] {
  implicit def scalars: Field[S]


  // Brings NumericOps into scope so you can use operators.
  implicit def hasOps(v: V): NumericOps[V]

  implicit def addVV: OpAdd.Impl2[V, V, V]  // defined in AdditiveTensorAbelianGroup (see below)            
  implicit def subVV: OpSub.Impl2[V, V, V] // defined in Module (below)

  implicit def mulVS: OpMulScalar.Impl2[V, S, V] // Module
  implicit def mulVS_M: OpMulMatrix.Impl2[V, S, V] // alias for above

  implicit def divVS: OpDiv.Impl2[V, S, V] 

  // create a zero vector
  implicit def zeroLike: CanCreateZerosLike[V, V]

  // whether two vectors are "close" according to some tolerance. May be strict equality.
  def close(a: V, b: V, tolerance: Double): Boolean
}

One of the big differences is that VectorSpaces mostly define operator ufunc implementations, rather than just raw methods. Coupled with the hasOps implicit, these all you to use the provided operations using operators, just by importing the vector space:

implicit def addAndScale[V, S](v1: V, v2: V, s: S)(implicitly vspace: VectorSpace[V, S]) = {
  import vspace._ // enable operations
  v1 + v2 * s
}

Note that many things can have VectorSpaces besides just Vectors. Matrices can also have VectorSpaces, as can Counters, and even functions!

Module (Advanced)

A Module is a VectorSpace where the underlying type is a Ring, rather than a Field. So, it's a VectorSpace without division and a Ring for scalars instead of a field:

trait Module[V, S] extends AdditiveTensorAbelianGroup[V, S]{
  implicit def scalars: Ring[S]

  // Brings NumericOps into scope so you can use operators.
  implicit def hasOps(v: V): NumericOps[V]

  implicit def addVV: OpAdd.Impl2[V, V, V]  // defined in AdditiveTensorAbelianGroup (see below)            
  implicit def subVV: OpSub.Impl2[V, V, V] 

  implicit def mulVS: OpMulScalar.Impl2[V, S, V]
  implicit def mulVS_M: OpMulMatrix.Impl2[V, S, V] // alias for above

  // create a zero vector
  implicit def zeroLike: CanCreateZerosLike[V, V]

  // whether two vectors are "close" according to some tolerance. May be strict equality.
  def close(a: V, b: V, tolerance: Double): Boolean
}

AdditiveTensorAbelianGroup (Advanced)

An AdditiveTensorAbelianGroup is an [abelian group] with respect to addition. It leaves out the multiplication operations from Module.

InnerProductSpace

An InnerProductSpace is a VectorSpace where you can take the dot product of two

XXX

Like VectorSpace, the vectors in an InnerProductSpace are not required to have finite dimension, or even to have an "index set" at all. See CoordinateField instead.

NormedVectorSpace

LPSpace (Advanced)

VectorRing (Advanced)

VectorField (Advanced)

CoordinateField

FiniteCoordinateField

EnumeratedCoordinateField (Advanced)

OptimizationSpace