Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
High-dimensional sparse array ??

Subject: High-dimensional sparse array ??

From: Pier Ferd

Date: 9 Dec, 2010 12:26:05

Message: 1 of 33

Hi all,

As indicated by my title, I would really need to use multidimensional sparse arrays. Indeed the arrays I use are full of 0 and I cannot reduce them to simple matrices (i.e. the fact that they are multidimensional is very very important). Of course I notices that sparse() only accepts matrices as imput and even worse as Matlab says : "??? N-dimensional indexing allowed for Full matrices only.".

Is there a way around this ? How can I create sparse arrays with dimensions larger than 2 ?

Subject: High-dimensional sparse array ??

From: Bruno Luong

Date: 9 Dec, 2010 12:41:04

Message: 2 of 33

"Pier Ferd" <plg255@hotmail.com> wrote in message <idqhst$mo7$1@ginger.mathworks.com>...
> Hi all,
>
> As indicated by my title, I would really need to use multidimensional sparse arrays. Indeed the arrays I use are full of 0 and I cannot reduce them to simple matrices (i.e. the fact that they are multidimensional is very very important). Of course I notices that sparse() only accepts matrices as imput and even worse as Matlab says : "??? N-dimensional indexing allowed for Full matrices only.".
>
> Is there a way around this ? How can I create sparse arrays with dimensions larger than 2 ?

Not possible.

But you can define your own storing scheme for example with a list of nd-coordinates where data is non-zero.

Bruno

Subject: High-dimensional sparse array ??

From: Pier Ferd

Date: 9 Dec, 2010 12:52:05

Message: 3 of 33

Gosh that sounds like an important Matlab limitation !! Also, and this is related to my previous question, is there a way to call a function to act only on the non-zero matrix elements of an array ? This would save me a lot of time and memory as for the moment I call my function (say Func) as Func(M) where M is my high-dimensional array, but then I discard the results of Func(M) where M was 0. So can I have Func to act only on non-zero elements of M?


"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <idqip0$91c$1@ginger.mathworks.com>...
> "Pier Ferd" <plg255@hotmail.com> wrote in message <idqhst$mo7$1@ginger.mathworks.com>...
> > Hi all,
> >
> > As indicated by my title, I would really need to use multidimensional sparse arrays. Indeed the arrays I use are full of 0 and I cannot reduce them to simple matrices (i.e. the fact that they are multidimensional is very very important). Of course I notices that sparse() only accepts matrices as imput and even worse as Matlab says : "??? N-dimensional indexing allowed for Full matrices only.".
> >
> > Is there a way around this ? How can I create sparse arrays with dimensions larger than 2 ?
>
> Not possible.
>
> But you can define your own storing scheme for example with a list of nd-coordinates where data is non-zero.
>
> Bruno

Subject: High-dimensional sparse array ??

From: Loren Shure

Date: 9 Dec, 2010 12:54:06

Message: 4 of 33


"Pier Ferd" <plg255@hotmail.com> wrote in message
news:idqjdl$jpo$1@ginger.mathworks.com...
> Gosh that sounds like an important Matlab limitation !! Also, and this is
> related to my previous question, is there a way to call a function to act
> only on the non-zero matrix elements of an array ? This would save me a
> lot of time and memory as for the moment I call my function (say Func) as
> Func(M) where M is my high-dimensional array, but then I discard the
> results of Func(M) where M was 0. So can I have Func to act only on
> non-zero elements of M?
>
>
> "Bruno Luong" <b.luong@fogale.findmycountry> wrote in message
> <idqip0$91c$1@ginger.mathworks.com>...
>> "Pier Ferd" <plg255@hotmail.com> wrote in message
>> <idqhst$mo7$1@ginger.mathworks.com>...
>> > Hi all,
>> >
>> > As indicated by my title, I would really need to use multidimensional
>> > sparse arrays. Indeed the arrays I use are full of 0 and I cannot
>> > reduce them to simple matrices (i.e. the fact that they are
>> > multidimensional is very very important). Of course I notices that
>> > sparse() only accepts matrices as imput and even worse as Matlab says :
>> > "??? N-dimensional indexing allowed for Full matrices only.".
>> >
>> > Is there a way around this ? How can I create sparse arrays with
>> > dimensions larger than 2 ?
>>
>> Not possible.
>>
>> But you can define your own storing scheme for example with a list of
>> nd-coordinates where data is non-zero.
>>
>> Bruno

doc spfun : Apply function to nonzero matrix elements

--
Loren
http://blogs.mathworks.com/loren/
http://www.mathworks.com/matlabcentral/newsreader/search_results?search_string=tag%3Afaq

Subject: High-dimensional sparse array ??

From: Bruno Luong

Date: 9 Dec, 2010 13:04:05

Message: 5 of 33

"Pier Ferd" <plg255@hotmail.com> wrote in message <idqjdl$jpo$1@ginger.mathworks.com>...
> Gosh that sounds like an important Matlab limitation !!

No big deal, Matlab have a bunch of functions to manipulate scattered coordinates (sortrows, ismember, intersect, ...). Mathematically they are equivalent to sparse-nd for element-wise manipulation. It just does carry a name "sparse".

The only thing is lacking of indexing convenient. You might create your own class by defining subsref and subsassgn, etc...

> Also, and this is related to my previous question, is there a way to call a function to act only on the non-zero matrix elements of an array ?

Use logical indexing. If your matrix is sparse use sparsefun().

Bruno

Subject: High-dimensional sparse array ??

From: Pier Ferd

Date: 9 Dec, 2010 13:08:04

Message: 6 of 33

But spfun works for sparse matrices and the point is my array cannot be put into sparse form since it is high-dimensional...

"Loren Shure" <loren.shure@mathworks.com> wrote in message <idqjhf$lnc$1@ginger.mathworks.com>...
>
> "Pier Ferd" <plg255@hotmail.com> wrote in message
> news:idqjdl$jpo$1@ginger.mathworks.com...
> > Gosh that sounds like an important Matlab limitation !! Also, and this is
> > related to my previous question, is there a way to call a function to act
> > only on the non-zero matrix elements of an array ? This would save me a
> > lot of time and memory as for the moment I call my function (say Func) as
> > Func(M) where M is my high-dimensional array, but then I discard the
> > results of Func(M) where M was 0. So can I have Func to act only on
> > non-zero elements of M?
> >
> >
> > "Bruno Luong" <b.luong@fogale.findmycountry> wrote in message
> > <idqip0$91c$1@ginger.mathworks.com>...
> >> "Pier Ferd" <plg255@hotmail.com> wrote in message
> >> <idqhst$mo7$1@ginger.mathworks.com>...
> >> > Hi all,
> >> >
> >> > As indicated by my title, I would really need to use multidimensional
> >> > sparse arrays. Indeed the arrays I use are full of 0 and I cannot
> >> > reduce them to simple matrices (i.e. the fact that they are
> >> > multidimensional is very very important). Of course I notices that
> >> > sparse() only accepts matrices as imput and even worse as Matlab says :
> >> > "??? N-dimensional indexing allowed for Full matrices only.".
> >> >
> >> > Is there a way around this ? How can I create sparse arrays with
> >> > dimensions larger than 2 ?
> >>
> >> Not possible.
> >>
> >> But you can define your own storing scheme for example with a list of
> >> nd-coordinates where data is non-zero.
> >>
> >> Bruno
>
> doc spfun : Apply function to nonzero matrix elements
>
> --
> Loren
> http://blogs.mathworks.com/loren/
> http://www.mathworks.com/matlabcentral/newsreader/search_results?search_string=tag%3Afaq

Subject: High-dimensional sparse array ??

From: James Tursa

Date: 9 Dec, 2010 16:04:04

Message: 7 of 33

"Pier Ferd" <plg255@hotmail.com> wrote in message <idqkbk$1ho$1@fred.mathworks.com>...
> But spfun works for sparse matrices and the point is my array cannot be put into sparse form since it is high-dimensional...

So do what Bruno suggested, use your own storage scheme. e.g., put each 2D sparse slice as an individual cell in a cell array. Then write your own functions for whatever you need to do as loops over the cell array & call spfun etc.

James Tursa

Subject: High-dimensional sparse array ??

From: Matt J

Date: 9 Dec, 2010 16:15:05

Message: 8 of 33

If you want to take an object oriented approach, below (bottom of post) is a rudimentary classdef to get you started.

As an example of use, consider the following sparse-type vector

M=sparse(1:12);

and its full form, reshaped into a 2x3x2 array.

Mfull=reshape(full(M),[2,3,2]);

Now I create my "higher-dimensional" sparse object by doing,

>> A=ndSparse(M, [2,3,2])

A =

   (1,1) 1
   (1,2) 2
   (1,3) 3
   (1,4) 4
   (1,5) 5
   (1,6) 6
   (1,7) 7
   (1,8) 8
   (1,9) 9
   (1,10) 10
   (1,11) 11
   (1,12) 12

It looks/displays like the original sparse vector M because I haven't bothered to write a very sophisticated display method. However, the object A is indexible as a 2x3x2 array. Compare:

>> A(1:2,1,2)

ans =

   (1,1) 7
   (1,2) 8
 
>> Mfull(1:2,1,2)

ans =

     7
     8

I leave it to you to add error checking, a more sophisticated display method, etc...



%%%%%Put in file ndSparse.m
classdef ndSparse<double
 properties
        ndShape;
 end
 methods
     function obj=ndSparse(data,ndShape)
         obj=obj@double(data);
         obj.ndShape=ndShape;
     end
     
    function obj=subsref(obj,S)

        S.subs=nd2linear(S.subs,obj.ndShape);
        obj=ndSparse(builtin('subsref',double(obj),S) , obj.ndShape);
        
    end

    function obj=subsasgn(obj,S,rhs)

        S.subs=nd2linear(S.subs,obj.ndShape);
        obj=ndSparse(builtin('subsasgn',double(obj),S,rhs) , obj.ndShape);
        
    end

    function display(obj)
                      
            l=inputname(1);
            T=evalc('sparse(obj)'); %only way to get at the builtin display method
            if ~isempty(l),
                 T=strrep(T,'ans =',[l ' =']);
            end

            jj=find(T~=sprintf('\n'),1,'last');
            
            T=T(1:jj);
           
            disp(T), disp ' '
            
     end

 end
end

 function linsubs=nd2linear(ndSubs,ndShape)


      N=length(ndSubs);

      [linsubs{1:N}]=ndgrid(ndSubs{:});
       linsubs={sub2ind(ndShape,linsubs{:})};
       
 end
  

Subject: High-dimensional sparse array ??

From: Pier Ferd

Date: 9 Dec, 2010 17:50:25

Message: 9 of 33

"James Tursa" <aclassyguy_with_a_k_not_a_c@hotmail.com> wrote in message <idqulk$hip$1@fred.mathworks.com>...
> "Pier Ferd" <plg255@hotmail.com> wrote in message <idqkbk$1ho$1@fred.mathworks.com>...
> > But spfun works for sparse matrices and the point is my array cannot be put into sparse form since it is high-dimensional...
>
> So do what Bruno suggested, use your own storage scheme. e.g., put each 2D sparse slice as an individual cell in a cell array. Then write your own functions for whatever you need to do as loops over the cell array & call spfun etc.
>
> James Tursa

Yeah I thought this might slow down the computations a lot by adding for loops when I do everything vectorially.

Subject: High-dimensional sparse array ??

From: James Tursa

Date: 9 Dec, 2010 19:45:24

Message: 10 of 33

"Pier Ferd" <plg255@hotmail.com> wrote in message <idr4t1$ess$1@fred.mathworks.com>...
> "James Tursa" <aclassyguy_with_a_k_not_a_c@hotmail.com> wrote in message <idqulk$hip$1@fred.mathworks.com>...
> > "Pier Ferd" <plg255@hotmail.com> wrote in message <idqkbk$1ho$1@fred.mathworks.com>...
> > > But spfun works for sparse matrices and the point is my array cannot be put into sparse form since it is high-dimensional...
> >
> > So do what Bruno suggested, use your own storage scheme. e.g., put each 2D sparse slice as an individual cell in a cell array. Then write your own functions for whatever you need to do as loops over the cell array & call spfun etc.
> >
> > James Tursa
>
> Yeah I thought this might slow down the computations a lot by adding for loops when I do everything vectorially.

I doubt this would add very much to the overall computation timing. Since the cells are already individual variables, getting the 2D slices would simply amount to getting a shared data copy of the cell. Certainly this is *some* overhead, but it is quite different from getting a 2D slice from a full 3D array because in the full case you are forced to do a data copy to get the 2D slice. How large is your 3rd dimension?

James Tursa

Subject: High-dimensional sparse array ??

From: Pier Ferd

Date: 9 Dec, 2010 22:33:05

Message: 11 of 33

My arrays have up to 10 dimensions and each dimension can be up to a hundred elements, although because of memory considerations when I have 10 D I limit each dimension size to a smaller number.

"James Tursa" <aclassyguy_with_a_k_not_a_c@hotmail.com> wrote in message <idrbkk$lis$1@fred.mathworks.com>...
> "Pier Ferd" <plg255@hotmail.com> wrote in message <idr4t1$ess$1@fred.mathworks.com>...
> > "James Tursa" <aclassyguy_with_a_k_not_a_c@hotmail.com> wrote in message <idqulk$hip$1@fred.mathworks.com>...
> > > "Pier Ferd" <plg255@hotmail.com> wrote in message <idqkbk$1ho$1@fred.mathworks.com>...
> > > > But spfun works for sparse matrices and the point is my array cannot be put into sparse form since it is high-dimensional...
> > >
> > > So do what Bruno suggested, use your own storage scheme. e.g., put each 2D sparse slice as an individual cell in a cell array. Then write your own functions for whatever you need to do as loops over the cell array & call spfun etc.
> > >
> > > James Tursa
> >
> > Yeah I thought this might slow down the computations a lot by adding for loops when I do everything vectorially.
>
> I doubt this would add very much to the overall computation timing. Since the cells are already individual variables, getting the 2D slices would simply amount to getting a shared data copy of the cell. Certainly this is *some* overhead, but it is quite different from getting a 2D slice from a full 3D array because in the full case you are forced to do a data copy to get the 2D slice. How large is your 3rd dimension?
>
> James Tursa

Subject: High-dimensional sparse array ??

From: Matt J

Date: 27 Dec, 2010 15:29:05

Message: 12 of 33

"Matt J" wrote in message <idqva9$bh$1@fred.mathworks.com>...
>
> If you want to take an object oriented approach, below (bottom of post) is a rudimentary classdef to get you started.
==============

Developing this further turned into a fun weekend project for me, which I've submitted to the FEX here

http://www.mathworks.com/matlabcentral/fileexchange/29832-n-dimensional-sparse-arrays

For one thing, I enhanced the display method, so that MATLAB's n-dimensional display scheme is used for N-dimensional sparse arrays as well, e.g.,

>> A=sparse(1:8);

>> A=reshape(ndSparse(A),2,2,2)

A(:,:,1) =

   (1,1) 1
   (2,1) 2
   (1,2) 3
   (2,2) 4
 

A(:,:,2) =

   (1,1) 5
   (2,1) 6
   (1,2) 7
   (2,2) 8

 
You can also permute, cat, sum, and other common things you would do with nD arrays:

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

B(:,:,1) =

   (1,1) 10
   (2,1) 26
 

B(:,:,2) =

   (1,1) 14
   (2,1) 30

Subject: High-dimensional sparse array ??

From: Pier Ferd

Date: 11 Jan, 2011 13:33:05

Message: 13 of 33

Thanks a lot that looks amazing, I will test it thoroughly but anyway I think you really filled a big hole in Matlab's possibilities.

"Matt J" wrote in message <ifabc1$n1f$1@fred.mathworks.com>...
> "Matt J" wrote in message <idqva9$bh$1@fred.mathworks.com>...
> >
> > If you want to take an object oriented approach, below (bottom of post) is a rudimentary classdef to get you started.
> ==============
>
> Developing this further turned into a fun weekend project for me, which I've submitted to the FEX here
>
> http://www.mathworks.com/matlabcentral/fileexchange/29832-n-dimensional-sparse-arrays
>
> For one thing, I enhanced the display method, so that MATLAB's n-dimensional display scheme is used for N-dimensional sparse arrays as well, e.g.,
>
> >> A=sparse(1:8);
>
> >> A=reshape(ndSparse(A),2,2,2)
>
> A(:,:,1) =
>
> (1,1) 1
> (2,1) 2
> (1,2) 3
> (2,2) 4
>
>
> A(:,:,2) =
>
> (1,1) 5
> (2,1) 6
> (1,2) 7
> (2,2) 8
>
>
> You can also permute, cat, sum, and other common things you would do with nD arrays:
>
> >> B=sum( permute([A,A+1], [3,2,1]) ,2)
>
> B(:,:,1) =
>
> (1,1) 10
> (2,1) 26
>
>
> B(:,:,2) =
>
> (1,1) 14
> (2,1) 30

Subject: High-dimensional sparse array ??

From: Pier Ferd

Date: 11 Jan, 2011 13:41:05

Message: 14 of 33

ndstest does not work as it is, Matlab says :

??? Undefined function or method 'iscolumn' for input arguments of type
'ndSparse'.

Error in ==> ndSparse>ndSparse.subsref at 220
            if ischar(idx1)|| iscolumn(obj)

and indeed in the Methods for class ndSparse, iscolumn does not appear. Do you have a solution ? Sorry if this error comes from my current lack of understanding of your program.


"Matt J" wrote in message <ifabc1$n1f$1@fred.mathworks.com>...
> "Matt J" wrote in message <idqva9$bh$1@fred.mathworks.com>...
> >
> > If you want to take an object oriented approach, below (bottom of post) is a rudimentary classdef to get you started.
> ==============
>
> Developing this further turned into a fun weekend project for me, which I've submitted to the FEX here
>
> http://www.mathworks.com/matlabcentral/fileexchange/29832-n-dimensional-sparse-arrays
>
> For one thing, I enhanced the display method, so that MATLAB's n-dimensional display scheme is used for N-dimensional sparse arrays as well, e.g.,
>
> >> A=sparse(1:8);
>
> >> A=reshape(ndSparse(A),2,2,2)
>
> A(:,:,1) =
>
> (1,1) 1
> (2,1) 2
> (1,2) 3
> (2,2) 4
>
>
> A(:,:,2) =
>
> (1,1) 5
> (2,1) 6
> (1,2) 7
> (2,2) 8
>
>
> You can also permute, cat, sum, and other common things you would do with nD arrays:
>
> >> B=sum( permute([A,A+1], [3,2,1]) ,2)
>
> B(:,:,1) =
>
> (1,1) 10
> (2,1) 26
>
>
> B(:,:,2) =
>
> (1,1) 14
> (2,1) 30

Subject: High-dimensional sparse array ??

From: Matt J

Date: 11 Jan, 2011 14:29:04

Message: 15 of 33

"Pier Ferd" <plg255@hotmail.com> wrote in message <ighmlh$s7l$1@fred.mathworks.com>...
> ndstest does not work as it is, Matlab says :
>
> ??? Undefined function or method 'iscolumn' for input arguments of type
> 'ndSparse'.
>
> Error in ==> ndSparse>ndSparse.subsref at 220
> if ischar(idx1)|| iscolumn(obj)
>
> and indeed in the Methods for class ndSparse, iscolumn does not appear. Do you have a solution ? Sorry if this error comes from my current lack of understanding of your program.
=========

Pier, as the FEX page states, the tool was designed under R2010b which you apparently do not have (and so are missing functions like iscolumn())

You can create your own iscolumn.m file, as follows

function bool=iscolumn(V)
% ISCOLUMN(V) returns logical true (1) if SIZE(V) returns [n 1]
% with a nonnegative integer value n, and logical false (0) otherwise.

  bool=isequal( size(A), size(A(:));

end


Of course, I cannot guarantee that you are not missing other R2010b functions, so upgrading your MATLAB version is the more advisable fix here.

Subject: High-dimensional sparse array ??

From: Pier Ferd

Date: 11 Jan, 2011 14:50:20

Message: 16 of 33

Thank you for your quick reply. I updated my version to R2010b and everything works fine now. Your program is great and seems to work in my computations so far ! What a memory saving code !!

Subject: High-dimensional sparse array ??

From: Matt J

Date: 11 Jan, 2011 14:59:06

Message: 17 of 33

"Matt J" wrote in message <ighpfg$t2s$1@fred.mathworks.com>...
> "Pier Ferd" <plg255@hotmail.com> wrote in message <ighmlh$s7l$1@fred.mathworks.com>...
> > ndstest does not work as it is, Matlab says :
> >
> > ??? Undefined function or method 'iscolumn' for input arguments of type
> > 'ndSparse'.
>>
> Of course, I cannot guarantee that you are not missing other R2010b functions, so upgrading your MATLAB version is the more advisable fix here.
=================

Since you are working with sparse matrices, there are also other good reasons to upgrade to R2010b or higher. In earlier versions of MATLAB, sparse matrix indexing could result in dangerous silent errors. You might check to see if you can reproduce the following MATLAB error on your machine:

  
>> A=sparse(100000,100000,1),
  
      A =
   
                   (100000,100000) 1


>> A(logical(A))=2, %Wrong result due to indexing bug, R2009b
   
          A =
   
                    (65408,14101) 2
                    (100000,100000) 1



Conversely, in R2010b, you at least get an explicit error message:

>> A(logical(A))=2
??? Maximum variable size allowed by the program is exceeded.
 

Subject: High-dimensional sparse array ??

From: Pier Ferd

Date: 11 Jan, 2011 15:09:05

Message: 18 of 33

Strange bug indeed. On my computer here is what I have :

>> A(logical(A))=2

A =

             (100000,100000) 2

>> A

A =

             (100000,100000) 2

>>

I think it is correct isn't it ? Anyway the only more recent version available is R2011a which is still in prerelease so I prefer to wait before downloading it.

I am trying to add a isndSparse function to your program to determine is a given array is in ndSparse format. Any idea ? (I notice issparse(a) would give me 0, i.e. 'no' for a ndSparse object)

Subject: High-dimensional sparse array ??

From: Matt J

Date: 11 Jan, 2011 15:57:06

Message: 19 of 33

"Pier Ferd" <plg255@hotmail.com> wrote in message <ighrqh$394$1@fred.mathworks.com>...
> Strange bug indeed. On my computer here is what I have :
>
> >> A(logical(A))=2
>
> A =
>
> (100000,100000) 2
>
> >> A
>
> A =
>
> (100000,100000) 2
>
> >>
>
> I think it is correct isn't it ?
==================

Yes, it's correct. I think you must be working on a 64-bit machine. The test I had run was on a 32-bit laptop, which allows smaller array sizes, index ranges, etc...



>
> I am trying to add a isndSparse function to your program to determine is a given array is in ndSparse format. Any idea ? (I notice issparse(a) would give me 0, i.e. 'no' for a ndSparse object)
===========

The community would probably prefer it if we move discusssion specifically about the FEX tool to the comments section of its webpage

http://www.mathworks.com/matlabcentral/fileexchange/29832-n-dimensional-sparse-arrays

In any case, I recommend that instead of modifying ndSparse.m, that you move ndSparse.m to a directory called @ndSparse/ (this directory should lie in a parent directory that is on the MATLAB path, but should not itself be added to the path). You can implement isndSparse, as well as any other methods you would like to add, in separate M-files in this directory. That way, they will not get overwritten if you need to download updates from me of ndSparse.m itself. Although, I'm not averse to adding an isndSparse method to the distribution.

Subject: High-dimensional sparse array ??

From: Matt J

Date: 11 Jan, 2011 16:58:06

Message: 20 of 33

"Matt J" wrote in message <ighuki$4sv$1@fred.mathworks.com>...
> "Pier Ferd" <plg255@hotmail.com> wrote in message <ighrqh$394$1@fred.mathworks.com>...
>
> >
> > I am trying to add a isndSparse function to your program to determine is a given array is in ndSparse format. Any idea ? (I notice issparse(a) would give me 0, i.e. 'no' for a ndSparse object)
> ===========

Sorry, I didn't think this through. You don't want to make isndSparse a method of the ndSparse class. You want to make it a plain ordinary external M-function. That way it will called regardless of the input type

function bool=isndSparse(obj)
   bool=isa(obj,'ndSparse');
end

Subject: High-dimensional sparse array ??

From: Pier Ferd

Date: 11 Jan, 2011 17:09:21

Message: 21 of 33

Thanks that function is a good complement to the ndSparse class.

I noticed while running my program that computations are several time slower when using ndSparse objects that full arrays.
Is this true also when working with sparse matrices instead of full matrices, i.e. is Matlab slower to manipulate sparse object ?
My program works 100% vectorially and does all sorts of operations on all elements of the array at the same time (as well as operations restricted to certain dimensions etc.). Does the sparsity of the objects I use affect Matlab speed only when working vectorially ?
 

Subject: High-dimensional sparse array ??

From: Matt J

Date: 11 Jan, 2011 18:45:05

Message: 22 of 33

"Pier Ferd" <plg255@hotmail.com> wrote in message <igi2s1$8ln$1@fred.mathworks.com>...
> Thanks that function is a good complement to the ndSparse class.
>
> I noticed while running my program that computations are several time slower when using ndSparse objects that full arrays.
> Is this true also when working with sparse matrices instead of full matrices, i.e. is Matlab slower to manipulate sparse object ?
========

It really depends on the operation and the sparsity. Things like matrix multiplication are obviously a lot faster for sparse matrices, whereas matrix inversion would often be slower, e.g.,

>> As=sprand(1000,1000,.01); Ands=ndSparse(As); Af=full(Ands);

>> tic, inv(Af); toc; tic; inv(As); toc; tic, inv(Ands); toc
Elapsed time is 0.362518 seconds.
Elapsed time is 1.356536 seconds.
Elapsed time is 1.329244 seconds.

As for ndSparse, keep in mind that it is written in M-code and acts as a wrapper for MATLAB's native sparse data type. That will lead to some overhead, in certain cases, as compared to full-matrix operations which are written purely in optimized builtin code.

Subject: High-dimensional sparse array ??

From: Matt J

Date: 11 Jan, 2011 18:55:06

Message: 23 of 33

"Matt J" wrote in message <igi8fh$9ok$1@fred.mathworks.com>...
> "Pier Ferd" <plg255@hotmail.com> wrote in message <igi2s1$8ln$1@fred.mathworks.com>...
> > Thanks that function is a good complement to the ndSparse class.
> >
> > I noticed while running my program that computations are several time slower when using ndSparse objects that full arrays.
>
>*SNIP*
>
> As for ndSparse, keep in mind that it is written in M-code and acts as a wrapper for MATLAB's native sparse data type. That will lead to some overhead, in certain cases, as compared to full-matrix operations which are written purely in optimized builtin code.
==============

That said, I'm certainly not *always* seeing slower computations from ndSparse than for full arrays. Summations seem to do quite well, for example:

As=sprand(10000,5000,.01);
Ands=reshape( ndSparse(As), 100,100,[] );
Af=full(Ands);



>> tic, sum(Af,1); toc; tic, sum(Ands,1); toc
Elapsed time is 0.145365 seconds.
Elapsed time is 0.011220 seconds.

>> tic, sum(Af,2); toc; tic, sum(Ands,2); toc
Elapsed time is 0.173583 seconds.
Elapsed time is 0.048333 seconds.

>> tic, sum(Af,3); toc; tic, sum(Ands,3); toc
Elapsed time is 0.171513 seconds.
Elapsed time is 0.029365 seconds.

It will again depend on what kind of computations we're talking about.

Subject: High-dimensional sparse array ??

From: Matt J

Date: 11 Jan, 2011 19:02:06

Message: 24 of 33

"Pier Ferd" <plg255@hotmail.com> wrote in message <igi2s1$8ln$1@fred.mathworks.com>...
> Thanks that function is a good complement to the ndSparse class.
>
>
> My program works 100% vectorially and does all sorts of operations on all elements of the array at the same time (as well as operations restricted to certain dimensions etc.). Does the sparsity of the objects I use affect Matlab speed only when working vectorially ?
===========

Even elementwise operations can do quite well, as compared to full matrices:

As=sprand(10000,1000,.01);
Ands=reshape( ndSparse(As), 100,100,[] );
Af=full(Ands);

>> tic, Af(1:30,:,:).*Af(1:30,:,:); toc; tic, Ands(1:30,:,:).*Ands(1:30,:,:); toc
Elapsed time is 0.092869 seconds.
Elapsed time is 0.026451 seconds.

Subject: High-dimensional sparse array ??

From: Pier Ferd

Date: 11 Jan, 2011 20:10:05

Message: 25 of 33

Yes it is thus all the more surprising that my computation originally took 50 sec with full arrays but now takes 350sec with sparse arrays. I will try with harder computations (i.e. originally longer) to see how this scales with the array size.

Subject: High-dimensional sparse array ??

From: Bruno Luong

Date: 11 Jan, 2011 20:25:05

Message: 26 of 33

"Pier Ferd" <plg255@hotmail.com> wrote in message <igidet$2gr$1@fred.mathworks.com>...
> Yes it is thus all the more surprising that my computation originally took 50 sec with full arrays but now takes 350sec with sparse arrays. I will try with harder computations (i.e. originally longer) to see how this scales with the array size.

Try to use the PROFILER to see where the computation takes time.

Bruno

Subject: High-dimensional sparse array ??

From: Pier Ferd

Date: 12 Jan, 2011 10:45:05

Message: 27 of 33

I used the profiler to see what was taking time. Clearly the time consumption is concentrated in

ndSparse.times
ndSparse.plus
ndSparse.power

and this is why using ndSparse objects takes so much time as compared to full arrays. I guess the native Matlab function times, plus and power are optimized and they thus take much shorter times to execute.
It would be interesting to optimize these ndSparse functions as I guess anybody interested in sparse arrays might have large ones on which operations must be undertaken and thus might go into this time consumming problem. I will look into it and tell you if I find a solution.

Subject: High-dimensional sparse array ??

From: Pier Ferd

Date: 12 Jan, 2011 11:20:06

Message: 28 of 33

Here is the profiler detailed result about ndSparse.time

http://img522.imageshack.us/img522/6446/picture1qjj.png

As can be seen, most of the time is spent in "Self time (built-ins, overhead, etc.)" while the time spent in just executing finalObject for ndSparse.time is about the time taken by the whole computation when using full arrays... Is there a way to compile or something to make this whole thing faster ? Otherwise I cannot use it for it slows down the program by a factor of 7 or 8....

Subject: High-dimensional sparse array ??

From: Matt J

Date: 12 Jan, 2011 14:54:05

Message: 29 of 33

"Pier Ferd" <plg255@hotmail.com> wrote in message <igk2p5$j5p$1@fred.mathworks.com>...
> Here is the profiler detailed result about ndSparse.time
>
> http://img522.imageshack.us/img522/6446/picture1qjj.png
>
> As can be seen, most of the time is spent in "Self time (built-ins, overhead, etc.)" while the time spent in just executing finalObject for ndSparse.time is about the time taken by the whole computation when using full arrays... Is there a way to compile or something to make this whole thing faster ? Otherwise I cannot use it for it slows down the program by a factor of 7 or 8....
=============

Pier - there's really no way to know what's going on without seeing more of your code. Clearly, though, ndSparse does not have a problem competing with full arrays across the board. My examples above showed this.

Since your code is spending so much time in finalObject (a fairly trivial function), my guess would be that your code acts by looping over small chunks the data array in a loop, i.e., your code is not very vectorized. This means that the wrapper routines like finalObject are being called a lot more often than they are meant to and end up taking more time than the actual processing of the data (via times, power, etc...). If I'm right, this goes against the philosophy of MATLAB programming, and you should seek to reorganize your computations in a more vectorized way. But again, I'd need to see your code...

Subject: High-dimensional sparse array ??

From: Pier Ferd

Date: 12 Jan, 2011 15:12:04

Message: 30 of 33

This is an interesting remark, but my code has absolutely no For loops nor any While. Is it possible that my code has some sort of loop then from another function ?
I only create large arrays and then do a succession of simple operations on it (multiplications, additions and powers, all element by element). Other than that I have a few "if" but that's it. However the size of the arrays and the number of operations to be done on it are both enormous so if each time the elements of an array are multiplied by something the code calls ndSparse.time and finalObject then it explains why these functions are called so many times. No loops, simply extremely involved formulas with thousands of multiplications, additions and powers in it.

I cannot give you the code as it spans a hundred matlab files but I can show you specific piece of it if needed.

Subject: High-dimensional sparse array ??

From: Matt J

Date: 12 Jan, 2011 15:46:04

Message: 31 of 33

"Pier Ferd" <plg255@hotmail.com> wrote in message <igkgc4$cvo$1@fred.mathworks.com>...
>
However the size of the arrays and the number of operations to be done on it are both enormous so if each time the elements of an array are multiplied by something the code calls ndSparse.time and finalObject then it explains why these functions are called so many times.
===========

It doesn't explain why finalObject is so time consuming, though. The amount of time required to execute finalObject should be nowhere near the time required to multiply an enormous full array by something.

Are you sure that the data your working with is actually sparse, and remains sparse as it gets transformed by your hundreds of mfiles?


> I cannot give you the code as it spans a hundred matlab files but I can show you specific piece of it if needed.
===================

That would be ideal. Extract a small segment of the code where you know the enormous full array is being processed faster than the corresponding ndSparse array and show how to set up input data to this block of code. Then we will have something in front of us to analyze!

Subject: High-dimensional sparse array ??

From: Iain Strachan

Date: 22 Jan, 2013 12:40:08

Message: 32 of 33

"Pier Ferd" <plg255@hotmail.com> wrote in message <idqhst$mo7$1@ginger.mathworks.com>...
> Hi all,
>
> As indicated by my title, I would really need to use multidimensional sparse arrays. Indeed the arrays I use are full of 0 and I cannot reduce them to simple matrices (i.e. the fact that they are multidimensional is very very important). Of course I notices that sparse() only accepts matrices as imput and even worse as Matlab says : "??? N-dimensional indexing allowed for Full matrices only.".
>
> Is there a way around this ? How can I create sparse arrays with dimensions larger than 2 ?

Hi - I realise this is about three years after the original question, but only stumbled upon it just now after discovering that the sparse matrix is limited to 2.

My suggestion is this: simply employ an index coding scheme in a regular sparse matrix, for example for the coordinates (i,j,k,l) reduce to 2 by (N*i+j, N*k+l) where N is determined to be the largest index in any of the dimensions. Hence you have a 4-d array as a sparse 2-D array of sparse 2-D arrays. Generalisation to higher dimensions is similar. The main problem you will run into is integer overflow if the dimensionality gets too large or the dimensions are too large.

Subject: High-dimensional sparse array ??

From: Matt J

Date: 22 Jan, 2013 14:48:09

Message: 33 of 33

"Iain Strachan" wrote in message <kdm1b8$cso$1@newscl01ah.mathworks.com>...
>
> My suggestion is this: simply employ an index coding scheme in a regular sparse matrix, for example for the coordinates (i,j,k,l) reduce to 2 by (N*i+j, N*k+l) where N is determined to be the largest index in any of the dimensions. Hence you have a 4-d array as a sparse 2-D array of sparse 2-D arrays. Generalisation to higher dimensions is similar. The main problem you will run into is integer overflow if the dimensionality gets too large or the dimensions are too large.
================

That's basically what this does

http://www.mathworks.com/matlabcentral/fileexchange/29832-n-dimensional-sparse-arrays

The integer overflow issues are already present in 2D sparse matrices (when using linear indexing). For moderate dimensional arrays, it is indeed not too bad.

Tags for this Thread

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us