sparse-linear-algebra-0.1.0.0: Sparse linear algebra datastructures and algorithms

Math.Linear.Sparse

Synopsis

# Documentation

class Functor f => Additive f where Source #

###### === CLASSES and common operations

Minimal complete definition

Methods

zero :: Num a => f a Source #

zero element

(^+^) :: Num a => f a -> f a -> f a Source #

componentwise operations

(^-^) :: Num a => f a -> f a -> f a Source #

Instances

 Source # IntMap implementation Methodszero :: Num a => IntMap a Source #(^+^) :: Num a => IntMap a -> IntMap a -> IntMap a Source #(^-^) :: Num a => IntMap a -> IntMap a -> IntMap a Source # Source # Methodszero :: Num a => SpMatrix a Source #(^+^) :: Num a => SpMatrix a -> SpMatrix a -> SpMatrix a Source #(^-^) :: Num a => SpMatrix a -> SpMatrix a -> SpMatrix a Source # Source # Methodszero :: Num a => SpVector a Source #(^+^) :: Num a => SpVector a -> SpVector a -> SpVector a Source #(^-^) :: Num a => SpVector a -> SpVector a -> SpVector a Source #

negated :: (Num a, Functor f) => f a -> f a Source #

negate the values in a functor

minus :: (Additive f, Num a) => f a -> f a -> f a Source #

class Additive f => VectorSpace f where Source #

Vector space

Minimal complete definition

(.*)

Methods

(.*) :: Num a => a -> f a -> f a Source #

multiplication by a scalar

Instances

 Source # Methods(.*) :: Num a => a -> IntMap a -> IntMap a Source # Source # Methods(.*) :: Num a => a -> SpVector a -> SpVector a Source #

lerp :: (VectorSpace f, Num a) => a -> f a -> f a -> f a Source #

linear interpolation

class VectorSpace f => Hilbert f where Source #

Hilbert space (inner product)

Minimal complete definition

dot

Methods

dot :: Num a => f a -> f a -> a Source #

inner product

Instances

 Source # Methodsdot :: Num a => IntMap a -> IntMap a -> a Source # Source # Methodsdot :: Num a => SpVector a -> SpVector a -> a Source #

class Hilbert f => Normed f where Source #

Minimal complete definition

norm

Methods

norm :: (Floating a, Eq a) => a -> f a -> a Source #

Instances

 Source # Methodsnorm :: (Floating a, Eq a) => a -> IntMap a -> a Source # Source # Methodsnorm :: (Floating a, Eq a) => a -> SpVector a -> a Source #

normSq :: (Hilbert f, Num a) => f a -> a Source #

norm1 :: (Foldable t, Num a, Functor t) => t a -> a Source #

norm2 :: (Hilbert f, Floating a) => f a -> a Source #

normP :: (Foldable t, Functor t, Floating a) => a -> t a -> a Source #

normInfty :: (Foldable t, Ord a) => t a -> a Source #

normalize :: (Normed f, Floating a, Eq a) => a -> f a -> f a Source #

dotLp :: (Set t, Foldable t, Floating a) => a -> t a -> t a -> a Source #

reciprocal :: (Functor f, Fractional b) => f b -> f b Source #

scale :: (Num b, Functor f) => b -> f b -> f b Source #

class Additive f => FiniteDim f where Source #

FiniteDim : finite-dimensional objects

Minimal complete definition

dim

Associated Types

type FDSize f :: * Source #

Methods

dim :: f a -> FDSize f Source #

Instances

 Source # Associated Typestype FDSize (SpMatrix :: * -> *) :: * Source # Methods Source # Associated Typestype FDSize (SpVector :: * -> *) :: * Source # Methods

withDim :: (FiniteDim f, Show e) => f a -> (FDSize f -> f a -> Bool) -> (f a -> c) -> String -> (f a -> e) -> c Source #

withDim2 :: (FiniteDim f, FiniteDim g, Show e) => f a -> g b -> (FDSize f -> FDSize g -> f a -> g b -> Bool) -> (f a -> g b -> c) -> String -> (f a -> g b -> e) -> c Source #

class Additive f => HasData f a where Source #

HasData : accessing inner data (do not export)

Minimal complete definition

dat

Associated Types

type HDData f a :: * Source #

Methods

dat :: f a -> HDData f a Source #

Instances

 Source # Associated Typestype HDData (SpMatrix :: * -> *) a :: * Source # Methods Source # Associated Typestype HDData (SpVector :: * -> *) a :: * Source # Methods

class (FiniteDim f, HasData f a) => Sparse f a where Source #

Sparse : sparse datastructures

Minimal complete definition

spy

Methods

spy :: Fractional b => f a -> b Source #

Instances

 Source # Methodsspy :: Fractional b => SpMatrix a -> b Source # Source # Methodsspy :: Fractional b => SpVector a -> b Source #

class Functor f => Set f where Source #

Minimal complete definition

Methods

liftU2 :: (a -> a -> a) -> f a -> f a -> f a Source #

union binary lift

liftI2 :: (a -> b -> c) -> f a -> f b -> f c Source #

intersection binary lift

Instances

Source #
###### =================================================

Methods

liftU2 :: (a -> a -> a) -> IntMap a -> IntMap a -> IntMap a Source #

liftI2 :: (a -> b -> c) -> IntMap a -> IntMap b -> IntMap c Source #

Source #

Methods

liftU2 :: (a -> a -> a) -> SpMatrix a -> SpMatrix a -> SpMatrix a Source #

liftI2 :: (a -> b -> c) -> SpMatrix a -> SpMatrix b -> SpMatrix c Source #

Source #

Methods

liftU2 :: (a -> a -> a) -> SpVector a -> SpVector a -> SpVector a Source #

liftI2 :: (a -> b -> c) -> SpVector a -> SpVector b -> SpVector c Source #

data SpVector a Source #

###### =================================================

Sparse Vector

Constructors

 SV FieldssvDim :: Int svData :: IntMap a

Instances

 Source # instances for SpVector Methodsfmap :: (a -> b) -> SpVector a -> SpVector b #(<$) :: a -> SpVector b -> SpVector a # Source # Methodsfold :: Monoid m => SpVector m -> m #foldMap :: Monoid m => (a -> m) -> SpVector a -> m #foldr :: (a -> b -> b) -> b -> SpVector a -> b #foldr' :: (a -> b -> b) -> b -> SpVector a -> b #foldl :: (b -> a -> b) -> b -> SpVector a -> b #foldl' :: (b -> a -> b) -> b -> SpVector a -> b #foldr1 :: (a -> a -> a) -> SpVector a -> a #foldl1 :: (a -> a -> a) -> SpVector a -> a #toList :: SpVector a -> [a] #null :: SpVector a -> Bool #length :: SpVector a -> Int #elem :: Eq a => a -> SpVector a -> Bool #maximum :: Ord a => SpVector a -> a #minimum :: Ord a => SpVector a -> a #sum :: Num a => SpVector a -> a #product :: Num a => SpVector a -> a # Source # MethodsliftU2 :: (a -> a -> a) -> SpVector a -> SpVector a -> SpVector a Source #liftI2 :: (a -> b -> c) -> SpVector a -> SpVector b -> SpVector c Source # Source # Associated Typestype FDSize (SpVector :: * -> *) :: * Source # Methods Source # Methodsnorm :: (Floating a, Eq a) => a -> SpVector a -> a Source # Source # Methodsdot :: Num a => SpVector a -> SpVector a -> a Source # Source # Methods(.*) :: Num a => a -> SpVector a -> SpVector a Source # Source # Methodszero :: Num a => SpVector a Source #(^+^) :: Num a => SpVector a -> SpVector a -> SpVector a Source #(^-^) :: Num a => SpVector a -> SpVector a -> SpVector a Source # Source # Methodsspy :: Fractional b => SpVector a -> b Source # Source # Associated Typestype HDData (SpVector :: * -> *) a :: * Source # Methods Eq a => Eq (SpVector a) Source # Methods(==) :: SpVector a -> SpVector a -> Bool #(/=) :: SpVector a -> SpVector a -> Bool # Show a => Show (SpVector a) Source # MethodsshowsPrec :: Int -> SpVector a -> ShowS #show :: SpVector a -> String #showList :: [SpVector a] -> ShowS # (Show a, Num a) => PrintDense (SpVector a) Source # Methodsprd :: SpVector a -> IO () Source # type FDSize SpVector Source # type FDSize SpVector = Int type HDData SpVector a Source # type HDData SpVector a = IntMap a empty sparse vector (size n, no entries) mkSpVector :: (Num a, Eq a) => Int -> IntMap a -> SpVector a Source # create a sparse vector from an association list while discarding all zero entries mkSpVectorD :: (Num a, Eq a) => Int -> [a] -> SpVector a Source # ", from logically dense array (consecutive indices) onesSV :: Num a => Int -> SpVector a Source # DENSE vector of 1s zerosSV :: Num a => Int -> SpVector a Source # DENSE vector of 0s fromListSV :: Int -> [(Int, a)] -> SpVector a Source # toListSV :: SpVector a -> [(Key, a)] Source # toDenseListSV :: Num b => SpVector b -> [b] Source # lookupDenseSV :: Num a => Key -> SpVector a -> a Source # lookup SV manipulation headSV :: Num a => SpVector a -> a Source # concatSV :: SpVector a -> SpVector a -> SpVector a Source # concatenate SpVector promote a SV to SM outerProdSV :: Num a => SpVector a -> SpVector a -> SpMatrix a Source # outer vector product (><) :: Num a => SpVector a -> SpVector a -> SpMatrix a Source # outer vector product data SpMatrix a Source # ###### ================================================= Constructors  SM FieldssmDim :: (Rows, Cols) smData :: IntMap (IntMap a) Instances  Source # Methodsfmap :: (a -> b) -> SpMatrix a -> SpMatrix b #(<$) :: a -> SpMatrix b -> SpMatrix a # Source # MethodsliftU2 :: (a -> a -> a) -> SpMatrix a -> SpMatrix a -> SpMatrix a Source #liftI2 :: (a -> b -> c) -> SpMatrix a -> SpMatrix b -> SpMatrix c Source # Source # Associated Typestype FDSize (SpMatrix :: * -> *) :: * Source # Methods Source # Methodszero :: Num a => SpMatrix a Source #(^+^) :: Num a => SpMatrix a -> SpMatrix a -> SpMatrix a Source #(^-^) :: Num a => SpMatrix a -> SpMatrix a -> SpMatrix a Source # Source # Methodsspy :: Fractional b => SpMatrix a -> b Source # Source # Associated Typestype HDData (SpMatrix :: * -> *) a :: * Source # Methods Eq a => Eq (SpMatrix a) Source # Methods(==) :: SpMatrix a -> SpMatrix a -> Bool #(/=) :: SpMatrix a -> SpMatrix a -> Bool # Show a => Show (SpMatrix a) Source # instances for SpMatrix MethodsshowsPrec :: Int -> SpMatrix a -> ShowS #show :: SpMatrix a -> String #showList :: [SpMatrix a] -> ShowS # (Show a, Num a) => PrintDense (SpMatrix a) Source # Methodsprd :: SpMatrix a -> IO () Source # type FDSize SpMatrix Source # type FDSize SpMatrix = (Rows, Cols) type HDData SpMatrix a Source # type HDData SpMatrix a = IntMap (IntMap a)

maxTup :: Ord t => (t, t) -> (t, t) -> (t, t) Source #

TODO : use semilattice properties instead

minTup :: Ord t => (t, t) -> (t, t) -> (t, t) Source #

TODO : use semilattice properties instead

emptySpMatrix :: (Int, Int) -> SpMatrix a Source #

empty matrix of size d

matScale :: Num a => a -> SpMatrix a -> SpMatrix a Source #

type Rows = Int Source #

type Cols = Int Source #

type IxRow = Int Source #

type IxCol = Int Source #

nrows :: SpMatrix a -> Int Source #

nrows, ncols : size accessors

ncols :: SpMatrix a -> Int Source #

nrows, ncols : size accessors

data SMInfo Source #

Constructors

 SMInfo FieldssmNz :: Int smSpy :: Double

Instances

 Source # Methods(==) :: SMInfo -> SMInfo -> Bool #(/=) :: SMInfo -> SMInfo -> Bool # Source # MethodsshowsPrec :: Int -> SMInfo -> ShowS #showList :: [SMInfo] -> ShowS #

bandwidth bounds (min, max)

zeroSM :: Int -> Int -> SpMatrix a Source #

###### === SPARSE MATRIX BUILDERS

fromListSM' :: Foldable t => t (IxRow, IxCol, a) -> SpMatrix a -> SpMatrix a Source #

from list (row, col, value)

fromListSM :: Foldable t => (Int, Int) -> t (IxRow, IxCol, a) -> SpMatrix a Source #

toDenseListSM :: Num t => SpMatrix t -> [(IxRow, IxCol, t)] Source #

to List

mkDiagonal :: Int -> [a] -> SpMatrix a Source #

eye :: Num a => Int -> SpMatrix a Source #

ones :: Num a => Int -> [a] Source #

mkSubDiagonal :: Int -> Int -> [a] -> SpMatrix a Source #

encode :: (Int, Int) -> (Rows, Cols) -> Int Source #

decode :: (Int, Int) -> Int -> (Rows, Cols) Source #

extractSubmatrixSM :: SpMatrix a -> (Int, Int) -> (Int, Int) -> SpMatrix a Source #

###### === SUB-MATRICES

vertStackSM :: SpMatrix a -> SpMatrix a -> SpMatrix a Source #

###### === MATRIX STACKING

(-=-) :: SpMatrix a -> SpMatrix a -> SpMatrix a Source #

###### === MATRIX STACKING

lookupSM :: SpMatrix a -> Key -> Key -> Maybe a Source #

###### === LOOKUP

lookupWD_SM :: Num a => SpMatrix a -> (Key, Key) -> a Source #

Looks up an element in the matrix (if not found, zero is returned)

(@@) :: Num a => SpMatrix a -> (Key, Key) -> a Source #

Looks up an element in the matrix (if not found, zero is returned)

lookupWD_IM :: Num a => IntMap (IntMap a) -> (Key, Key) -> a Source #

foldlSM :: (a -> b -> b) -> b -> SpMatrix a -> b Source #

###### === MISC SpMatrix OPERATIONS

ifoldlSM :: (Key -> Key -> a -> b -> b) -> b -> SpMatrix a -> b Source #

mapping

folding

sparsify : remove 0s (!!!)

ROUNDING operations (!!!)

###### === ALGEBRAIC PRIMITIVE OPERATIONS

transpose

(#^) :: SpMatrix a -> SpMatrix a Source #

###### === ALGEBRAIC PRIMITIVE OPERATIONS

transpose

A^T B

A B^T

matVec :: Num a => SpMatrix a -> SpVector a -> SpVector a Source #

matrix action on a vector

(#>) :: Num a => SpMatrix a -> SpVector a -> SpVector a Source #

matrix action on a vector

(<#) :: Num a => SpVector a -> SpMatrix a -> SpVector a Source #

matMatU :: Num a => SpMatrix a -> SpMatrix a -> SpMatrix a Source #

matrix-matrix product

(##) :: Num a => SpMatrix a -> SpMatrix a -> SpMatrix a Source #

sparsified matrix-matrix product (prunes all elements x for which abs x <= eps)

sparsified matrix-matrix product (prunes all elements x for which abs x <= eps)

###### === condition number

hhMat :: Num a => a -> SpVector a -> SpMatrix a Source #

###### === Householder transformation

hypot :: Floating a => a -> a -> a Source #

###### === Givens rotation matrix

sign :: (Ord a, Num a) => a -> a Source #

givensCoef :: (Ord a, Floating a) => a -> a -> (a, a, a) Source #

###### =================================================

LINEAR SOLVERS : solve A x = b

numerical tolerance for e.g. solution convergence

residual :: Num a => SpMatrix a -> SpVector a -> SpVector a -> SpVector a Source #

residual of candidate solution x0

CGS

one step of CGS

data CGS Source #

Constructors

 CGS Fields_x :: SpVector Double _r :: SpVector Double _p :: SpVector Double _u :: SpVector Double

Instances

 Source # Methods(==) :: CGS -> CGS -> Bool #(/=) :: CGS -> CGS -> Bool # Source # MethodsshowsPrec :: Int -> CGS -> ShowS #show :: CGS -> String #showList :: [CGS] -> ShowS #

BiCSSTAB

one step of BiCGSTAB

data BICGSTAB Source #

Constructors

 BICGSTAB Fields

Instances

 Source # Methods Source # MethodsshowList :: [BICGSTAB] -> ShowS #
###### === LINEAR SOLVERS INTERFACE

Constructors

 CGS_ BICGSTAB_

Instances

 Source # Methods Source # MethodsshowList :: [LinSolveMethod] -> ShowS #

TODO : if system is poorly conditioned, is it better to warn the user or just switch solvers (e.g. via the pseudoinverse) ?

###### === PRETTY PRINTING

Show details and contents of sparse matrix

showNonZero :: (Show a, Num a, Eq a) => a -> String Source #

toDenseRow :: Num a => SpMatrix a -> Key -> [a] Source #

toDenseRowClip :: (Show a, Num a) => SpMatrix a -> Key -> Int -> String Source #

printDenseSM :: (Show t, Num t) => SpMatrix t -> IO () Source #

printDenseSV :: (Show t, Num t) => SpVector t -> IO () Source #

class PrintDense a where Source #

Minimal complete definition

prd

Methods

prd :: a -> IO () Source #

Instances

 (Show a, Num a) => PrintDense (SpMatrix a) Source # Methodsprd :: SpMatrix a -> IO () Source # (Show a, Num a) => PrintDense (SpVector a) Source # Methodsprd :: SpVector a -> IO () Source #

rounding to 0 or 1 within some predefined numerical precision

rounding to 0 or 1 within some predefined numerical precision

withDefault :: (t -> Bool) -> t -> t -> t Source #

with2Defaults :: (t -> Bool) -> (t -> Bool) -> t -> t -> t -> t Source #

modifyUntil :: MonadState s m => (s -> Bool) -> (s -> s) -> m s Source #

transform state until a condition is met

loopUntilAcc :: Int -> ([t] -> Bool) -> (t -> t) -> t -> t Source #

modifyInspectN :: MonadState s m => Int -> ([s] -> Bool) -> (s -> s) -> m s Source #

meanl :: (Foldable t, Fractional a) => t a -> a Source #

norm2l :: (Foldable t, Functor t, Floating a) => t a -> a Source #

diffSqL :: Floating a => [a] -> a Source #

untilConverged :: MonadState a m => (a -> SpVector Double) -> (a -> a) -> m a Source #

runAppendN :: ([t] -> Bool) -> (t -> t) -> Int -> t -> [t] Source #

runAppendN' :: (t -> t) -> Int -> t -> [t] Source #

randMat :: PrimMonad m => Int -> m (SpMatrix Double) Source #

random matrices and vectors

denseIxArray :: [b] -> [(Int, b)] Source #

misc utils

integer-indexed ziplist

denseIxArray2 :: Int -> [c] -> [(Int, Int, c)] Source #

foldrMap :: (Foldable t, Functor t) => (a -> b) -> (b -> c -> c) -> c -> t a -> c Source #

foldlStrict :: (a -> b -> a) -> a -> [b] -> a Source #

ifoldr :: Num i => (a -> b -> b) -> b -> (i -> c -> d -> a) -> c -> [d] -> b Source #

type LB = Int Source #

type UB = Int Source #

inBounds :: LB -> UB -> Int -> Bool Source #

inBounds2 :: (LB, UB) -> (Int, Int) -> Bool Source #

inBounds02 :: (UB, UB) -> (Int, Int) -> Bool Source #

untilC :: (a -> Bool) -> Int -> (a -> a) -> a -> a Source #

terminate after n iterations or when q becomes true, whichever comes first