Re: [Caml-list] Package with multidimensional AND sparse matrices?

[Jon Harrop <jon@ffconsultancy.com>]

On Monday 03 July 2006 23:55, Andreas Biegert wrote:
> The ocamlfloat package provides a sparse matrix implmentation for
> 2-dimensional matrices, but I would need at least 4 dimensions.

You probably mean "tensor" rather than "matrix".

> In case there is no such package, would it be very hard to write one by
> myself?

Provided performance and memory usage are not too important, it is quite 
simple to write your own implementation. First, you must decide what 
requirements you have, i.e. what do you want to do with these tensors? Then, 
you must choose a data structure to represent your tensors, e.g. a hash table 
that maps int * int * int * int to float. Finally, you must implement the 
functions that you need.

You could start with something like this:

module SparseArray : sig
  type t

  val make : int list -> t
  val get : t -> int list -> float
  val set : t -> int list -> float -> unit
end = struct
  type t = int list * (int list, float) Hashtbl.t

  let make n = n, Hashtbl.create 0

  let check s n i =
    List.iter2 (fun n i -> if i<0 || i>=n then invalid_arg s) n i

  let get (n, m) i =
    check "SparseArray.get" n i;
    try Hashtbl.find m i with Not_found -> 0.

  let set (n, m) i x =
    check "SparseArray.set" n i;
    if x<>0. then Hashtbl.replace m i x else
    try Hashtbl.remove m i with Not_found -> ()
end;;

That should be fine for getting and setting but you probably want to loop over 
dimensions and perform arithmetic operations, in which case you need a way to 
jump to the non-zero elements.

How many non-zero elements do you have and how long do you expect your 
calculations to take?

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
Objective CAML for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists