sparsematmult

A Matrix

    [ 1 0 2 0 ]
A = [ 0 2 0 0 ]
    [ 0 0 0 3 ]
    [ 0 0 4 0 ]

sparse representation

Wikipedia: (row compressed form)

cells = [ 1 2 2 3 4 ]
Is    = [ 0 2 3 4 ]
Js    = [ 0 2 1 3 2 ]

Exploiting segmented arrays (still row compressed form)

cells = [ [1 2] [ 2 ] [ 3 ] [ 4 ] ]
cols  = [ [0 2] [ 1 ] [ 3 ] [ 2 ] ]

or even

cells = [ [ (1,0) (2,2) ] [ (2,1) ] [ (3,3) ] [ (4,2) ] ]

"dph":

wikipedia style:

matVecMult mat vec =
  let
  -- A matrix is a tuple of cells, a mapping from row numbers
  -- to cells-ixes, and a mapping from cells-ixes to columns
     (cells, is, cs) = mat
     rows = length is
  in
    [: rowSum | i        <- [:0 .. rows -1 :],
                ixBounds <- indexP [:i,i+1:] is,
                cellsIxs <- [:ixBounds[0] .. ixBounds[1] :],
                rowCells <- indexP cellsIxs cells,
                cellCols <- indexP cellsIxs cs,
                vecCells <- indexP cellCols vec,
                -- products <- [: rowCells[j] * vecCells[j] | j <- [:0 .. length cellsIxs:] :],
                -- products <- mapP (uncurry (*)) (zipP rowCells vecCells),
                products <- zipWithP (*) rowCells vecCells,
                rowSum   <- reduceP (+) products
              :]

Segmented array style: (using [: [: (F,Int) :] :] for matrix)

matVecMult mat vec =
   mapP rowSum (mapP colProd mat)
   where
     rowSum = reduceP (+)
     colProd row = let
       (cells,cols) = unzipP row
       in mapP (uncurry (*)) (zipP cells (indexP cols vec))

Flattening:

⟨reduceP op arr⟩ → ⟨reduceP op arr⟩  -- (primitive for now)
(mapP_s: ) ⟨mapP f arr⟩ → ⟨f⟩ arr    -- dph also need to handle closure environment extension
(mapP_L: ) ⟨mapP...

mapP   :: (a -> b) -> PA a -> PA b
⟨mapP⟩ :: PA (a -> b) -> PA (PA a) -> PA (PA b)

⟨mapP f arr⟩ → unconcatP arr (⟨f⟩ (concatP arr))

unzipP :: PA (a, b) -> (PA a, PA b)
⟨unzipP⟩ :: PA (PA (a,b)) -> PA (PA a, PA b)

flatten matVecMult →
  let
    matVecMult_s :: ([:[:(F,Int):]:], [:F:]) -> [:F:]
    matVecMult_s (mat, vec) =
    matVecMult_p :: [: ( [: [: (F,Int) :] :], [: F :] ) :] -> [: [:F:] :]
    matVecMult_p matVecs =
      let colProds = unconcatP matVecs (colProd_p (concatP matVecs))
       in unconcatP colProds (rowSum_p (concatP colProds))
      where
        rowSum_p  = ⟨reduceP (+)⟩
        colProd_p rows = let
          cellsCols_p :: PA (PA a, PA b)
          cellsCols_p = ⟨unzipP⟩ rows -- possibly the same as ⟨mapP⟩ unzipP ?
          ...
          in ...
  in (matVecMult_s, matVecMult_p