N-dimensional sparse arrays

Version 1.20.0 (24.9 KB) by Matt J
Creates an N-dimensional sparse array object, for arbitrary N.
6.5K Downloads
Updated 16 Mar 2021

View License

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.

Cite As

Matt J (2024). N-dimensional sparse arrays (https://www.mathworks.com/matlabcentral/fileexchange/29832-n-dimensional-sparse-arrays), MATLAB Central File Exchange. Retrieved .

MATLAB Release Compatibility
Created with R2010b
Compatible with R2008a and later releases
Platform Compatibility
Windows macOS Linux
Categories
Find more on Sparse Matrices in Help Center and MATLAB Answers
Acknowledgements

Inspired by: sub2allind

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!
Version Published Release Notes
1.20.0

Added support for implicit expansion, e.g., one can now do things like
>> ndSparse([1,2,3]) + ndSparse([1;2;3])

1.19.0.1

updated release compatibility info

1.19.0.0

Indexing bug fix. Affected scalar, linear indexing (see update notes).

1.18.0.0

Indexing bug fixes.

1.16.0.0

Improvements to MIN/MAX when dealing with singleton dimensions.

Improved memory efficiency in CAT and null assignment.

1.15.0.0

Fixed bug involving ndSparse arrays with singleton dimensions. It affected MIN, MAX, SUBSASGN, and CAT.

1.14.0.0

Speed up indexing operations of the form A(:,:,...,:,i)

1.13.0.0

Fixed the output of ndSparse.build and CONVN, which sometimes had very large nzmax.

1.12.0.0

Improved the DISPLAY method, so that now only A(:,:,i,j,k,...) with non-zero data will be displayed.

1.8.0.0

*Forgot to add installation instructions in my submission earlier this week
*Also, replaced ISDOUBLE in ndsparse.accumarray with something more universal.

1.7.0.0

*Some bug fixes, including Ohad's issue of assigning a matrix into an array.

*Improved memory efficiency of various operations, but with trade-offs. See UpdateNotes

1.6.0.0

Fixed a bug in SUBSASGN operations that expand the size of the matrix,
e.g., A(end+1,end+1)=5;
Thanks to Zvi Devir for reporting.

1.5.0.0

Pervasive changes, some new methods, and some bug fixes. See UpdateNotes in .zip for full details.

Among other things, ndSparse objects should typically consume a lot less memory now.

1.4.0.0

Fixed a bug in the constructor, which could cause ndSparse object to have incorrect dimensions.

1.3.0.0

See UpdateNotes in the .zip for full details. Highlights:

1. Lots of new methods!! BSXFUN, REPMAT, CIRCSHIFT,CONVN,...
2. Improved the efficiency of PERMUTE
3. Some small backward-compatibility issues.
4. Added an R2009b compatible version.

1.2.0.0

See UpdateNotes in the .zip for full details. Highlights:

1. Lots of new methods!! For example BSXFUN, REPMAT, CIRCSHIFT,CONVN.

2. Improved the efficiency of PERMUTE

3. Some small backward-compatibility issues.

1.1.0.0

*Some improvements to CAT and SUM, including minor bug fixes.
*Added methods MIN, MAX, ANY, ALL for the class.
*Improved error checking.

1.0.0.0