sparse-0.9: A playground of sparse linear algebra primitives using Morton ordering

Portability non-portable experimental Edward Kmett None

Sparse.Matrix

Description

Sparse Matrices in Morton order

The design of this library is described in the series "Revisiting Matrix Multiplication" on FP Complete's School of Haskell.

Synopsis

# Sparse Matrices

data Mat a Source

Constructors

 Mat !Int !(Vector Word) !(Vector Word) !(Array a)

Instances

 (Arrayed a, Eq (Array a)) => Eq (Mat a) (Arrayed a, Eq0 a) => Num (Mat a) (Arrayed a, Ord (Array a)) => Ord (Mat a) (Arrayed a, Read a) => Read (Mat a) (Arrayed a, Show a) => Show (Mat a) NFData (Array a) => NFData (Mat a) Arrayed a => Ixed (Mat a) Arrayed a => Arrayed (Mat a) (Arrayed a, Eq0 a) => Eq0 (Mat a) (Arrayed a, ~ * a b) => Each (Mat a) (Mat b) a b

# Keys

data Key Source

`Key i j` logically orders the keys as if the bits of the keys `i` and `j` were interleaved. This is equivalent to storing the keys in "Morton Order".

````>>> ````Key 100 200 ^. _1
```100
```
````>>> ````Key 100 200 ^. _2
```200
```

Constructors

 Key !Word !Word

Instances

 Eq Key Ord Key Read Key Show Key Unbox Key Arrayed Key Vector Vector Key FunctorWithIndex Key Heap FoldableWithIndex Key Heap TraversableWithIndex Key Heap MVector MVector Key (~ * a Word, ~ * b Word) => Field1 Key Key a b (~ * a Word, ~ * b Word) => Field2 Key Key a b

# Construction

fromList :: Arrayed a => [(Key, a)] -> Mat aSource

Build a sparse matrix.

singleton :: Arrayed a => Key -> a -> Mat aSource

`singleton` makes a matrix with a singleton value at a given location

transpose :: Arrayed a => Mat a -> Mat aSource

Transpose a matrix

ident :: (Arrayed a, Num a) => Int -> Mat aSource

`ident n` makes an `n` x `n` identity matrix

````>>> ````ident 4
```fromList [(Key 0 0,1),(Key 1 1,1),(Key 2 2,1),(Key 3 3,1)]
```

empty :: Arrayed a => Mat aSource

The empty matrix

````>>> ````empty :: Mat Int
```fromList []
```

# Consumption

size :: Mat a -> IntSource

Count the number of non-zero entries in the matrix

````>>> ````size (ident 4)
```4
```

null :: Mat a -> BoolSource

````>>> ````null (empty :: Mat Int)
```True
```

# Distinguishable Zero

class (Arrayed a, Num a) => Eq0 a whereSource

Methods

isZero :: a -> BoolSource

Return whether or not the element is 0.

It may be okay to never return `True`, but you won't be able to thin spurious zeroes introduced into your matrix.

nonZero :: (x -> y -> a) -> x -> y -> Maybe aSource

Remove results that are equal to zero from a simpler function.

When used with `addWith` or `multiplyWith`'s additive argument this can help retain the sparsity of the matrix.

addMats :: Mat a -> Mat a -> Mat aSource

Add two matrices. By default this assumes `isZero` can possibly return `True` after an addition. For some ring-like structures, this doesn't hold. There you can use:

``` `addMats` = `addWith` (`+`)
```

By default this will use

``` `addMats` = `addWith0` `\$` `nonZero` (`+`)
```

addHeap :: Maybe (Heap a) -> Stream (Key, a)Source

Convert from a `Heap` to a `Stream`.

If addition of non-zero valus in your ring-like structure cannot yield zero, then you can use

``` `addHeap` = `streamHeapWith` (`+`)
```

``` `addHeap` = `streamHeapWith0` `\$` `nonZero` (`+`)
```

Instances

 Eq0 Double Eq0 Float Eq0 Int Eq0 Integer Eq0 Word (RealFloat a, Eq0 a) => Eq0 (Complex a) (Arrayed a, Eq0 a) => Eq0 (Mat a)

# Customization

addWith :: Arrayed a => (a -> a -> a) -> Mat a -> Mat a -> Mat aSource

Merge two matrices where the indices coincide into a new matrix. This provides for generalized addition, but where the summation of two non-zero entries is necessarily non-zero.

multiplyWith :: Arrayed a => (a -> a -> a) -> (Maybe (Heap a) -> Stream (Key, a)) -> Mat a -> Mat a -> Mat aSource

Multiply two matrices using the specified multiplication and addition operation.

# Storage

class (Vector (Arr a) a, Monoid (Arr a a)) => Arrayed a Source

Associated Types

type Arr a :: * -> *Source

Instances

 Arrayed Double Arrayed Float Arrayed Int Arrayed Int8 Arrayed Int16 Arrayed Int32 Arrayed Int64 Arrayed Integer Arrayed Word Arrayed Word8 Arrayed Word16 Arrayed Word32 Arrayed Word64 Arrayed () Arrayed Key (Arrayed a, RealFloat a) => Arrayed (Complex a) Arrayed a => Arrayed (Mat a) (Arrayed a, Arrayed b) => Arrayed (a, b)

# Lenses

_Mat :: Arrayed a => Iso' (Mat a) (Vector Vector (Arr a) (Key, a))Source

bundle up the matrix in a form suitable for vector-algorithms

keys :: Lens' (Mat a) (Vector Key)Source

Access the keys of a matrix

values :: Lens (Mat a) (Mat b) (Array a) (Array b)Source

Access the keys of a matrix