sparse-linear-algebra-0.2.0.3: Numerical computation in native Haskell

Numeric.LinearAlgebra.Sparse

Synopsis

class Functor f => Additive f where Source #

Minimal complete definition

Methods

zero :: Num a => f a Source #

Ring zero element

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

Ring +

Instances

 Source # Methodszero :: Num 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 # Source # Methodszero :: Num 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

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

Vector space

class Additive f => VectorSpace f where Source #

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

Hilbert space (inner product)

class VectorSpace f => Hilbert f where Source #

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 #

Normed vector space

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 #

Norms and related results

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

Squared 2-norm

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

L1 norm

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

Euclidean norm

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

Lp norm (p > 0)

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

Infinity-norm

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

Normalize w.r.t. p-norm (p finite)

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

Lp inner product (p > 0)

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

Reciprocal

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

Scale

FiniteDim : finite-dimensional objects

class Additive f => FiniteDim f where Source #

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 #

unary dimension-checking bracket

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 #

binary dimension-checking bracket

HasData : accessing inner data (do not export)

class Additive f => HasData f a where Source #

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

Sparse : sparse datastructures

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

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 #

Set : things that behave as sets

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 : apply function on _union_ of two Sets

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

intersection binary lift : apply function on _intersection_ of two Sets

Instances

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

Sparse Vector

data SpVector a Source #

Constructors

 SV FieldssvDim :: Int svData :: IntMap a

Instances

 Source # 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 # 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 spySV :: Fractional b => SpVector a -> b Source # SpVector sparsity Creation empty sparse vector (length n, no entries) singletonSV :: a -> SpVector a Source # singleton sparse vector (length 1) 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) fromListDenseSV :: Int -> [a] -> SpVector a Source # Create new sparse vector, assumin 0-based, contiguous indexing onesSV :: Num a => Int -> SpVector a Source # DENSE vector of 1s zerosSV :: Num a => Int -> SpVector a Source # DENSE vector of 0s Element insertion insertSpVector :: Int -> a -> SpVector a -> SpVector a Source # insert element x at index i in a preexisting SpVector fromList fromListSV :: Int -> [(Int, a)] -> SpVector a Source # toList toListSV :: SpVector a -> [(Key, a)] Source # toDenseListSV :: Num b => SpVector b -> [b] Source # To dense list (default = 0) Lookup lookupDenseSV :: Num a => Key -> SpVector a -> a Source # lookup an index in a SpVector (returns 0 if lookup fails) Sub-vectors Tail elements headSV :: Num a => SpVector a -> a Source # Head element concatSV :: SpVector a -> SpVector a -> SpVector a Source # concatenate two sparse vectors promote a SV to SM Outer vector product (><) :: Num a => SpVector a -> SpVector a -> SpMatrix a Source # Sparse Matrix 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 # 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 # 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 #

Componentwise tuple operations TODO : use semilattice properties instead

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

Componentwise tuple operations TODO : use semilattice properties instead

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

Empty matrix of size d

Creation

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

Zero SpMatrix of size (m, n)

Diagonal matrix

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

Identity matrix

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

Super- or sub- diagonal matrix

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

fromList

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

Add to existing SpMatrix using data from list (row, col, value)

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

Create new SpMatrix using data from list (row, col, value)

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

Create new SpMatrix assuming contiguous, 0-based indexing of elements

toList

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

Populate list with SpMatrix contents and populate missing entries with 0

Element insertion

insertSpMatrix :: IxRow -> IxCol -> a -> SpMatrix a -> SpMatrix a Source #

Insert an element in a preexisting Spmatrix at the specified indices

Lookup

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

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

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

Zero-default lookup, infix form

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

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

Multiply matrix by a scalar

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

Frobenius norm (sqrt of trace of M^T M)

type Rows = Int Source #

type Cols = Int Source #

type IxRow = Int Source #

type IxCol = Int Source #

Predicates

validIxSM :: SpMatrix a -> (Int, Int) -> Bool Source #

Are the supplied indices within matrix bounds?

Is the matrix square?

Is the matrix diagonal?

is the matrix orthogonal? i.e. Q^t ## Q == I

immSM :: SpMatrix t -> IntMap (IntMap t) Source #

Data in internal representation (do not export)

dimSM :: SpMatrix t -> (Rows, Cols) Source #

(Number of rows, Number of columns)

nelSM :: SpMatrix t -> Int Source #

Number of rows times number of columns

nrows :: SpMatrix a -> Rows Source #

Number of rows

ncols :: SpMatrix a -> Cols Source #

Number of columns

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 #

Sub-matrices

extractSubmatrixSM :: SpMatrix a -> (IxRow, IxCol) -> (IxRow, IxCol) -> SpMatrix a Source #

Extract a submatrix given the specified index bounds

toSV :: SpMatrix a -> SpVector a Source #

Demote (n x 1) or (1 x n) SpMatrix to SpVector

Extract j'th column

", and place into SpVector

Extract i'th row

", and place into SpVector

Matrix stacking

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

Vertical stacking

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

Vertical stacking

horizStackSM :: SpMatrix a -> SpMatrix a -> SpMatrix a Source #

Horizontal stacking

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

Horizontal stacking

Misc. SpMatrix operations

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

Left fold over SpMatrix

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

Indexed left fold over SpMatrix

Count sub-diagonal nonzeros

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

Extract the diagonal as a SpVector (with default 0)

subdiagIndicesSM :: SpMatrix a -> [(Key, Key)] Source #

Filter the index subset that lies below the diagonal (used in the QR decomposition, for example)

Value rounding

Round almost-0 and almost-1 to 0 and 1 respectively

Primitive algebra operations

transposeSM, (#^) : Matrix transpose

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

transposeSM, (#^) : Matrix transpose

Matrix action on a vector

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

Matrix-on-vector

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

Matrix-on-vector

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

Vector-on-matrix (FIXME : transposes matrix: more costly than matVec, I think)

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

Vector-on-matrix (FIXME : transposes matrix: more costly than matVec, I think)

Matrix-matrix product

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

Matrix-matrix product, sparsified

Removes all elements x for which | x | <= eps)

Removes all elements x for which | x | <= eps)

A^T B

A B^T

Matrix condition number

uses the R matrix from the QR factorization

Householder transformation

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

a vector x uniquely defines an orthogonal plane; the Householder operator reflects any point v with respect to this plane: v' = (I - 2 x >< x) v

Givens rotation matrix

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

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

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

Givens coefficients (using stable algorithm shown in Anderson, Edward (4 December 2000). "Discontinuous Plane Rotations and the Symmetric Eigenvalue Problem". LAPACK Working Note)

Givens method, row version: choose other row index i' s.t. i' is : * below the diagonal * corresponding element is nonzero

QR.C1 ) To zero out entry A(i, j) we must find row k such that A(k, j) is non-zero but A has zeros in row k for all columns less than j.

Is the kth the first nonzero column in the row?

candidateRows :: IntMap (IntMap a) -> IxRow -> IxCol -> Maybe [Key] Source #

Returns a set of rows {k} that satisfy QR.C1

QR decomposition

Applies Givens rotation iteratively to zero out sub-diagonal elements

Givens matrices in order [G1, G2, .. , G_N ]

Eigenvalue algorithms

One eigenvalue and eigenvector (Rayleigh iteration)

Cubic-order convergence, but it requires a mildly educated guess on the initial eigenpair

Iterative linear solvers

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 #

iterate solver until convergence or until max # of iterations is reached

BiCSSTAB

one step of BiCGSTAB

data BICGSTAB Source #

Constructors

 BICGSTAB Fields

Instances

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

iterate solver until convergence or until max # of iterations is reached

Linear solver interface

Constructors

 CGS_ BICGSTAB_

Instances

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

Linear solve with _random_ starting vector

Linear solve with _deterministic_ starting vector (every component at 0.1)

<> : linSolve using BiCGSTAB method and by default

Control primitives for bounded iteration with convergence check

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 #

Keep a moving window buffer (length 2) of state x to assess convergence, stop when either a condition on that list is satisfied or when max # of iterations is reached

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

Keep a moving window buffer (length 2) of state x to assess convergence, stop when either a condition on that list is satisfied or when max # of iterations is reached (runs in State monad)

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 #

iterate until convergence is verified or we run out of a fixed iteration budget

normDiffConverged :: (Foldable t, Functor t) => (a -> SpVector Double) -> t a -> Bool Source #

convergence check (FIXME)

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

run niter iterations and append the state x to a list xs, stop when either the xs satisfies a predicate q or when the counter reaches 0

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

", NO convergence check

Rounding operations

Rounding rule

Rounding rule

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

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

Round to respectively 0 or 1 within some predefined numerical precision eps

Random matrices and vectors

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

Dense SpMatrix

randVec :: PrimMonad m => Int -> m (SpVector Double) Source #

Dense SpVector

Sparse SpMatrix

Sparse SpVector

Pretty printing

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 #

Pretty printer typeclass

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 #

Misc. utilities

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

integer-indexed ziplist

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

", 2d arrays

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

foldr over the results of a fmap

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

strict left fold

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

indexed right fold

Bounds checking

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 #