N-dimensional sparse arrays

This submission defines a class of N-dimensional sparse arrays for N possibly greater than 2. However, it should really be thought of as a way of starting with an ordinary MATLAB sparse matrix and reshaping it to have N dimensions. In other words, the sparse data must first be able to exist as an ordinary 2D MATLAB sparse matrix before being made N-dimensional. In fact, if the intended array has dimensions MxNxP...YxZ, then the class will store it internally as an ordinary 2D sparse array of dimensions (M*N*P*...*Y)xZ. This leads to certain memory strains when using large numbers of dimensions. I find the class useful mainly for moderate dimensional things like edge detection in 3D imaging, where you often want to hold a sparse 3D edge map.


USAGE:

S=ndSparse(X) where X is an ordinary MATLAB sparse matrix converts X into an ndSparse object. S can be reshaped into an N-dimensional sparse array using its RESHAPE method, for arbitrary N.

S=ndSparse(X,[M,N,P,...]) is equivalent to reshape(ndSparse(X),[M,N,P,...]).

The class also has a variety of static methods that can be used to construct instances of the class. For example,

S=ndSparse.build(Coordinates,Values,[m,n,p,...],nzmax)

lets you generate an N-dimensional sparse array from a table of explicit entries. This is a generalization to N dimensions of S=sparse(i,j,s,m,n,nzmax).

Other such methods include:

ndSparse.accumarray
ndSparse.sprand
ndSparse.sprandn
ndSparse.spalloc

EXAMPLES:

>> A=ndSparse.build( [1 1 1; 2 1 1;2 2 2] , [50,60 70]) %Builds a 2x2x2 sparse array from table

A(:,:,1) =

(1,1) 50
(2,1) 60

A(:,:,2) =

(2,2) 70

Many of the same manipulations common to ordinary multidimensional MATLAB full arrays can be performed on the sparse 3D array A generated above. It can be permuted, summed, concatentated, and so forth e.g.,

>> B=sum( permute([A,A+10], [3,2,1]) ,2)

B(:,:,1) =

(1,1) 120
(2,1) 20

B(:,:,2) =

(1,1) 140
(2,1) 160

Other overloaded methods include BSXFUN, REPMAT, CIRCSHIFT, CONVN, FLIPDIMS, SQUEEZE, SHIFTDIM and many more. Type "methods ndSparse" for a full list and use "help ndSparse.methodname" to get details of usage.

When browsing the list of methods, note that certain common operations have different implementations, optimized for different situations. Specifically, SUM, ANY,ALL, MIN, MAX... have alternative implementations SUMML, ANYML, ALLML, MINML, MAXML which are optimized for "low-dimensional" ndSparse objects OBJ. Here, low-dimensional means that a normal N-column MATLAB sparse matrix won't consume too much memory on your platform for N=MAX(NUMEL(OBJ)./SIZE(OBJ)).

Another feature of the class is that bi-operand operations are allowed between ndSparse objects and MATLAB objects of any numeric type (single, uint16, etc...). This is not true of ordinary MATLAB sparse matrices, as of R2010b.

>> C=eye(2,'single')*B(:,:,2)

C =

(1,1) 140
(2,1) 160

>> whos A B C

Name Size Bytes Class Attributes

A 2x2x2 136 ndSparse
B 2x1x2 140 ndSparse
C 2x1 104 ndSparse

To convert back to an ordinary n-D full array, use the class' overloaded FULL method. To convert to a normal 2D sparse matrix, use the methods SPARSE or SPARSE2D. For example, SPARSE2D will convert an MxNxPx...xQ ndSparse array to the two dimensional (M*N*P*...)xQ sparse matrix in native MATLAB form.