From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <jon@ffconsultancy.com>
X-Original-To: caml-list@yquem.inria.fr
Delivered-To: caml-list@yquem.inria.fr
Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39])
	by yquem.inria.fr (Postfix) with ESMTP id C56F2BB83
	for <caml-list@yquem.inria.fr>; Tue,  4 Jul 2006 04:01:35 +0200 (CEST)
Received: from pih-relay04.plus.net (pih-relay04.plus.net [212.159.14.131])
	by concorde.inria.fr (8.13.6/8.13.6) with ESMTP id k6421aVk016402
	(version=TLSv1/SSLv3 cipher=AES256-SHA bits=256 verify=NO)
	for <caml-list@yquem.inria.fr>; Tue, 4 Jul 2006 04:01:36 +0200
Received: from [80.229.56.224] (helo=chetara)
	 by pih-relay04.plus.net with esmtp (Exim) id 1FxaEE-0007Xd-H8
	for caml-list@yquem.inria.fr; Tue, 04 Jul 2006 03:01:30 +0100
From: Jon Harrop <jon@ffconsultancy.com>
Organization: Flying Frog Consultancy Ltd.
To: caml-list@yquem.inria.fr
Subject: Re: [Caml-list] Package with multidimensional AND sparse matrices?
Date: Sun, 2 Jan 2000 04:56:19 +0000
User-Agent: KMail/1.9.1
References: <fd0847170607031555y3cdeae8fl2e54b75bae052854@mail.gmail.com>
In-Reply-To: <fd0847170607031555y3cdeae8fl2e54b75bae052854@mail.gmail.com>
MIME-Version: 1.0
Content-Type: text/plain;
  charset="iso-8859-1"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline
Message-Id: <200001020456.19386.jon@ffconsultancy.com>
X-Miltered: at concorde with ID 44A9CC00.001 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)!
X-Spam: no; 0.00; matrices:01 matrices:01 hash:01 sig:01 val:01 val:01 struct:01 hashtbl:01 hashtbl:01 iter:01 non-zero:01 non-zero:01 ocaml:01 2006:98 frog:98 
X-Spam-Checker-Version: SpamAssassin 3.0.3 (2005-04-27) on yquem.inria.fr
X-Spam-Level: *
X-Spam-Status: No, score=1.1 required=5.0 tests=DATE_IN_PAST_96_XX 
	autolearn=disabled version=3.0.3

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