should I use a matrix or a vector ? [Matlab]

Prev: menu list is not showing
Next: Hessian fmincon

From: Juliette Salexa on 12 Apr 2010 12:48

Hello,

I've been doing some tests to see whether it's more efficient to use a matrix (M) or a vector (V) to store elements that I will later on be reading.

(1) To use an element of M, matlab needs to search for *two* indices rather than just one.

(2)But to call the same element of V, matlab will need to search for *one* index , but also will need to do one multiplication and one addition [to do what it is that I want it to do]

I tested options (1) and (2) [you can see results below] , and it looks like (2) is better at first, but when iterated many times, (1) becomes better by more than 20 minutes.

*However* ... It's still hard for me to tell whether these results are artifacts of the fact that my cluster was doing other computations in the background, or if they had to do with the RAND function, etc.

If anyone knows more about the inner-workings of matlab and would know a clear reason why option (1) would be better than (2) or vice versa, I'd be interested to learn.

The test I tried to do is below:
==========================
M=rand(4).*(-1).^(round(rand(4))); %random matrix, but just as many positive as negative so that numbers don't explode

sum=0;
tic;
for m=1:7^11
sum=M(1+round(3*rand),1+round(3*rand))+sum;
end
toc;

M2=reshape(M,1,16);

tic;
for m=1:7^11
sum=M2((round(3*rand)+1-1)*4+round(3*rand)+1);
end
toc;

%7^6: (number of iterations in forloop)
%Elapsed time is 2.626146 seconds.
%Elapsed time is 2.969748 seconds.

%7^9:
% Elapsed time is 933.490330 seconds.
% Elapsed time is 927.935108 seconds.

%^11;
% Elapsed time is 46175.453762 seconds.
% Elapsed time is 47472.380431 seconds.

Option 1 looks better than option 2 by about 20 minutes (which will make a huge difference in my overall program), but that may be because of other computations running in the background, or because the anti-virus software starts running at 3am

Juliette

From: Matt J on 12 Apr 2010 13:24

"Juliette Salexa" <juliette.physicist(a)gmail.com> wrote in message <hpvis4$f53$1(a)fred.mathworks.com>...

> (1) To use an element of M, matlab needs to search for *two* indices rather than just one.
==================

In principal, not really. MATLAB can index a matrix 1-dimensionally, irrespective of the matrix's shape. E.g.,

>> M=rand(2)

M =

0.8147 0.1270
0.9058 0.9134

>> M(3)

ans =

0.1270

However, since you are working with sparse matrices, you have to be careful. Sparse matrices have overflow bugs in their one-dimensional indexing routines. That's incidentally why the following FEX tools were made

http://www.mathworks.com/matlabcentral/fileexchange/26181-robust-sparse-data-types

http://www.mathworks.com/matlabcentral/fileexchange/23488-sparse-sub-access

If you think you can save speed by doing 1-dimensional indexing, you probably want to use one of these tools for safety's sake. If you use mine (the first one), you will want to put things in vector form (a la your 2nd proposal). If you keep your data in matrix form, the code will pre-convert linear indices to (i,j) indices and you will gain nothing.

From: Juliette Salexa on 14 Apr 2010 17:34

Thanks Matt!

For this computation, the matrices are actually just dense 4x4's (not sparse matrices).

It seems from my tests shown in the first post that searching for 2 indices is actually faster than searching for one index and also doing one integer-multiplication and one integer-addition.

I will try what you suggested and index the matrices using only one index, and maybe that will speed it up anymore.

I was just wondering knew the answer at the top of their head so that I wouldn't have to just trust these tests =)

Thank you,
Juliette

From: Matt J on 14 Apr 2010 22:33

"Juliette Salexa" <juliette.physicist(a)gmail.com> wrote in message <hq5ccc$1vl$1(a)fred.mathworks.com>...
> Thanks Matt!
>
> For this computation, the matrices are actually just dense 4x4's (not sparse matrices).
>
> It seems from my tests shown in the first post that searching for 2 indices is actually faster than searching for one index and also doing one integer-multiplication and one integer-addition.
===============

The thing to realize is that all types of indexing operations in MATLAB must ultimately convert the index to a single linear one. This conversion will either happen internally in the builtin code (like version 1 in your test) or be done manually by you in M-code (like in your version 2). The builtin code will obviously do the conversion more optimally, which is why version 1 showed slightly higher speed.

The question is whether it was necessary in your particular situation to do the conversion manually. The answer to that question depends on where the indices originate from. If you generate the indices using a logical test for example like (A>0), then it would be best just to use the logical index array itself to do the matrix look-up. In certain circumstances, there are also more optimal ways to generate the single linear indices than what your version 2 uses. For example, you could have done
find(A>0), which will again do the index conversion in built-in code.

From: Matt J on 15 Apr 2010 10:53

| Next | Last
Pages: 1 2
Prev: menu list is not showing
Next: Hessian fmincon