sparse-linear-algebra-0.1.0.1: Sparse linear algebra datastructures and algorithms. Currently it provides iterative linear solvers, matrix decompositions, eigenvalue computations and related utilities.

Math.Linear.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

squared 2-norm

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

L1 norm

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

Euclidean norm

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

Lp norm (p > 0)

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

infinity-norm

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

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

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

Lp inner product (p > 0)

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

reciprocal

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

scale

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

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 (e.g. of which we can take the union and the intersection)

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 # 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

Instances for SpMatrix

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

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?

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 #

SPARSE MATRIX BUILDERS

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

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

to List

Populate missing entries with 0

Diagonal matrix

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

Identity matrix

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

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

Create Super- or sub- diagonal matrix

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

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

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

SUB-MATRICES

toSV :: SpMatrix a -> SpVector a Source #

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

Extract jth column

extractCol :: SpMatrix a -> Int -> SpVector a Source #

", and place into SpVector

Extract ith row

extractRow :: SpMatrix a -> Int -> SpVector a Source #

", 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

MATRIX ELEMENT LOOKUP

lookupWD_SM :: Num a => SpMatrix a -> (Key, Key) -> 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 -> (Key, Key) -> 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) -> (Key, Key) -> a Source #

MISC SpMatrix OPERATIONS

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

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

mapping

folding

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

filtering

extract with default 0

ALGEBRAIC PRIMITIVE OPERATIONS

A^T B

A B^T

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 #

Predicates

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

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) -> Key -> Key -> 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 corresponding eigenvector, using Rayleigh iteration

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

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 #

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 SOLVERS 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)

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 #

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 #

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

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 #