Prev: How to show coordinates with ginput while moving cursor?
Next: problem with mex file and mexw32 file
From: Avneep Dhanju on 6 Jan 2010 02:14
I am writing a function to reduce a large sparse matrix. The function is such that it takes a sparse matrix (say A) as its input and returns a sparse matrix (say B) which is half the size of the input matrix (along both axes) and the average of a neighborhood of 4 elements of A is the value of each element of B. For example, if A is 6-by-6 matrix (this is just for convenience, actually the size of A is very large) then B is 3-by-3 with B(1,1)=(A(1,1)+A(1,2)+A(2,1)+A(2,2))/4, B(1,2)=(A(1,3)+A(1,4)+A(2,3)+A(2,4))/4 and so on.

Now, I have read Tim Davis' explanation on Loren's blog. I understand that creating a sparse matrix out of three vectors is very efficient. I need help to implement that idea on this problem. What I don't understand is the size of the 3 vectors. For argument's sake say the input matrix is of the size 65536-by-65536. The output matrix will be 32768-by-32768. What should be the size of the vectors i, j and x in this case? Since the command B=sparse(i,j,x,n,n) will give B(i(k), j(k))=x(k), does that mean i, j and x need to be 32768*32768-by-1 vectors (which is not probable as I think I did not understand this part)? Can anyone please help me understand this concept?

Further, how to construct x as a loop like this over
x(k)=(A(m,(2*n)-1)+A(m,2*n)+A(2*m,(2*n)-1)+A(2*m,2*n))/4;
takes forever to run.

Any help will be much appreciated.
From: Matt J on 6 Jan 2010 06:34
"Avneep Dhanju" <avneepdhanju(a)gmail.com> wrote in message <hi1d7t$jr7$1(a)fred.mathworks.com>...

> Now, I have read Tim Davis' explanation on Loren's blog. I understand that creating a sparse matrix out of three vectors is very efficient. I need help to implement that idea on this problem. What I don't understand is the size of the 3 vectors. For argument's sake say the input matrix is of the size 65536-by-65536. The output matrix will be 32768-by-32768. What should be the size of the vectors i, j and x in this case?
==============================

I don't think there's a simple relationship. It depends very much on the values of the matrix.

Do you really need that much efficiency, however? The function below should be reasonably fast,

B=downsamp2d(A,[2,2]);



function M=downsamp2d(M,bindims)
%DOWNSAMP2D - simple tool for 2D downsampling
%
% M=downsamp2d(M,bindims)
%
%in:
%
% M: a matrix
% bindims: a vector [p,q] specifying pxq downsampling
%
%out:
%
% M: the downsized matrix

p=bindims(1); q=bindims(2);
[m,n]=size(M); %M is the original matrix

M=sum( reshape(M,p,[]) ,1 );
M=reshape(M,m/p,[]).'; %Note transpose

M=sum( reshape(M,q,[]) ,1);
M=reshape(M,n/q,[]).'; %Note transpose

M=M/(p*q);
From: Matt J on 6 Jan 2010 09:13
"Matt J " <mattjacREMOVE(a)THISieee.spam> wrote in message <hi1sft$o45$1(a)fred.mathworks.com>...
> "Avneep Dhanju" <avneepdhanju(a)gmail.com> wrote in message <hi1d7t$jr7$1(a)fred.mathworks.com>...
>
> > Now, I have read Tim Davis' explanation on Loren's blog. I understand that creating a sparse matrix out of three vectors is very efficient. I need help to implement that idea on this problem. What I don't understand is the size of the 3 vectors. For argument's sake say the input matrix is of the size 65536-by-65536. The output matrix will be 32768-by-32768. What should be the size of the vectors i, j and x in this case?
> ==============================
>
> I don't think there's a simple relationship. It depends very much on the values of the matrix.
>
> Do you really need that much efficiency, however? The function below should be reasonably fast,
>
> B=downsamp2d(A,[2,2]);

Forget this approach. I just checked and it doesn't handle sparse large matrices well. How about the following:

%data

d=65536;
A=sprand(d,d,.001);

%engine
tic;
D=kron(speye(d/2),[1,1]/2);
B=(D*A)*D.' ;
toc,
%Elapsed time is 0.579553 seconds.


Quick enough?
From: Avneep Dhanju on 6 Jan 2010 18:14
Thanks for your reply.

I do understand that this is a very fast way of creating a reduced matrix, but my concern is the values of the newly created matrix. I mean do they contain the average of four pixel neighborhood of the original array? Looping over the original sparse matrix does not give an answer. It simply loops forever.

I was wondering whether there exists a way to get the index vectors of an already created sparse matrix. I mean that would be pretty helpful as we can create the index and value vectors of the new reduced sparse matrix.

Thanks again and waiting for ur help.

"Avneep Dhanju" <avneepdhanju(a)gmail.com> wrote in message <hi1d7t$jr7$1(a)fred.mathworks.com>...
> I am writing a function to reduce a large sparse matrix. The function is such that it takes a sparse matrix (say A) as its input and returns a sparse matrix (say B) which is half the size of the input matrix (along both axes) and the average of a neighborhood of 4 elements of A is the value of each element of B. For example, if A is 6-by-6 matrix (this is just for convenience, actually the size of A is very large) then B is 3-by-3 with B(1,1)=(A(1,1)+A(1,2)+A(2,1)+A(2,2))/4, B(1,2)=(A(1,3)+A(1,4)+A(2,3)+A(2,4))/4 and so on.
>
> Now, I have read Tim Davis' explanation on Loren's blog. I understand that creating a sparse matrix out of three vectors is very efficient. I need help to implement that idea on this problem. What I don't understand is the size of the 3 vectors. For argument's sake say the input matrix is of the size 65536-by-65536. The output matrix will be 32768-by-32768. What should be the size of the vectors i, j and x in this case? Since the command B=sparse(i,j,x,n,n) will give B(i(k), j(k))=x(k), does that mean i, j and x need to be 32768*32768-by-1 vectors (which is not probable as I think I did not understand this part)? Can anyone please help me understand this concept?
>
> Further, how to construct x as a loop like this over
> x(k)=(A(m,(2*n)-1)+A(m,2*n)+A(2*m,(2*n)-1)+A(2*m,2*n))/4;
> takes forever to run.
>
> Any help will be much appreciated.
From: Matt J on 6 Jan 2010 20:25
"Avneep Dhanju" <avneepdhanju(a)gmail.com> wrote in message <hi35fr$mkv$1(a)fred.mathworks.com>...
> Thanks for your reply.
>
> I do understand that this is a very fast way of creating a reduced matrix, but my concern is the values of the newly created matrix. I mean do they contain the average of four pixel neighborhood of the original array?
====================

Yes, they do. If you need convincing, you can try the technique on a small matrix for which you can easily display and inspect the result.

>
> I was wondering whether there exists a way to get the index vectors of an already created sparse matrix. I mean that would be pretty helpful as we can create the index and value vectors of the new reduced sparse matrix.
===============

You can use the [i,j,v]=find(A) to find the non-zero elements of A and their coordinates. However, I think it is a cumbersome approach. You than have to group the (i,j) together and determine which belong to a common 2x2 pixel neighborhood. Is the speed-up really worth it to you when my approach will do the same thing in 2 lines of code and in seconds or less?
 |  Next  |  Last
Pages: 1 2
Prev: How to show coordinates with ginput while moving cursor?
Next: problem with mex file and mexw32 file