Sparse matrix and savings

I have a complex matrix which has non zero values only in specific region of the matrix. And most of the remaining part is equal to zero(see the image).The size of the matrix is m x n where m >>>> n eg. 4096 x 256 and I want to carry out element by element multiplication with another complex matrix of same size that has a specific pattern.But here's the problem since the complex matrix has majority of its elements zero (some real some imaginary and sometimes both)I want to store it in sparse form and multiply only the elements which are non zero with that of the pattern_matrix at those positions of non-zero elements in the complex sparse matrix. How do I do it efficiently and save complex multiplications without degradation in quality?

PSEUDO CODE
for 1:value
  while(condition is true)
    Sparse_Matrix = Sparse_Matrix.*Pattern_Matrix(value)
    Another_Matrix(count,:) = sum(Sparse_Matrix)
    Increment count
  end of while loop
  Some operations;
end of For loop

[Walter Roberson]

Please do not close questions that have an answer.

Answer 1

[James Tursa]

I don't fully understand your pseudo code, particularly your use of value when indexing into Pattern_Matrix(value). If you just want to do element-by-element multiplication with only those non-zero element spots in the sparse matrix, then you can do this:

g = Sparse_Matrix ~= 0; % index spots where you want to do the multipies
Sparse_Matrix(g) = Sparse_Matrix(g) .* Pattern_Matrix(g); % do the multiplies in only those spots

You could also just do it directly as follows (probably faster than above method), but NaN's and Inf's in the non-zero spots will propagate:

Sparse_Matrix = Sparse_Matrix .* Pattern_Matrix;

[D_coder]

As I already mentioned sparse matrix is a complex matrix , how would i do the operation which you mentioned for a complex matrix. Also pattern_matrix with a value signifies that for every iteration of for loop the pattern_matrix is difference. For every change in pattern matrix , there is very less changes in those images attached. How do I propagate changes from one iteration of for loop without multiplying the part that remains same for the iteration.

[Steven Lord]

For your first question: the .* operator knows how to handle full real, full complex, sparse real, and sparse complex matrices perfectly well. Just call the .* operator.

I'm not sure what you mean by your second question, about propagating changes. Can you show a concrete example with a small matrix, say something in the 5-by-5 to 10-by-10 range?

rng default
Sparse_Matrix = sprand(10, 10, 0.1)

Show us a sample Pattern_Matrix compatible with Sparse_Matrix and show exactly what you expect to receive using Sparse_Matrix and your sample Pattern_Matrix. [I used "rng default" so all of us will create the same pseudorandom SparseMatrix.]

[D_coder]

First part: My concern is for g = Sparse_Matrix ~= 0 operation on complex Sparse_Matrix. I will have to check if real part is zero then I will multiply only the imaginary part of sparse_matrix with pattern_matrix and if imaginary part is zero I will multiply only the real part of the sparse matrix with the pattern matrix and if whole complex element of sparse_matrix is zero than I will avoid multiplication Second part: the pattern matrix(value) is different for every iteration of for loop , so everytime it gets multiplied by the sparse matrix there is some changes in the sparse matrix but those changes in the sparse - image are minute as compared to the whole image. So when moving from one iteration of for loop to other I want to propagate only those changes , I mean compare the previous sparse matrix and current sparse matrix elements and multiply only the elements of sparse matrix to the corresponding pattern matrix element if there is going to be some significant change as decided .

[Steven Lord]

First part: My concern is for g = Sparse_Matrix ~= 0 operation on complex Sparse_Matrix. I will have to check if real part is zero then I will multiply only the imaginary part of sparse_matrix with pattern_matrix and if imaginary part is zero I will multiply only the real part of the sparse matrix with the pattern matrix and if whole complex element of sparse_matrix is zero than I will avoid multiplication

Why do you think YOU need to handle that checking? Let MATLAB do it.

% Make some sample matrices
rng default
n = 20;
AR = sprand(n, n, 0.1);
AI = sprand(n, n, 0.1);
BR = sprand(n, n, 0.1);
BI = sprand(n, n, 0.1);
A = AR + 1i*AI;
B = BR + 1i*BI;

Let's perform elementwise multiplication using the sample matrices I created above.

% complex-complex elementwise multiplication works
XCC = A.*B

% complex-real works too
XCR = A.*BR

% real-complex is no problem
XRC = AR.*B

% real-imaginary works as well
XRI = AR.*(1i*B)

You can see that XCC has non-zero elements only where you'd expect there to be a non-zero element, only places where both A and B are non-zero.

patternCC = (A ~= 0) & (B ~= 0)

Second part: the pattern matrix(value) is different for every iteration of for loop , so everytime it gets multiplied by the sparse matrix there is some changes in the sparse matrix but those changes in the sparse - image are minute as compared to the whole image. So when moving from one iteration of for loop to other I want to propagate only those changes , I mean compare the previous sparse matrix and current sparse matrix elements and multiply only the elements of sparse matrix to the corresponding pattern matrix element if there is going to be some significant change as decided.

This still is not clear to me. Let's assume the A and B matrices from the example earlier in my comment are Sparse_Matrix and pattern_matrix respectively. XCC is their elementwise product. What EXACTLY do you want to be propagated? Don't answer in words, show us (by copying and pasting the code you've written that decides what is "significant", by listing the indices in the matrix XCC that need to propagate, or by displaying the new Sparse_Matrix) what the new Sparse_Matrix should be.

[D_coder]

for my first part: I want to handle this checking my self to save the multiplications. I want to do this checking efficiently. Is there is a way to do checking in a single line? if real part of sparse_matrix is equal to zero multiply only the imaginary part with pattern_matrix if imaginary part is equal to zero than only multiply the real part if real and imaginary part is zero donot multiply. Second part:

starts here:
PSEUDO CODE:FIRST PART
A %sparse_matrix
B %pattern matrix
%I want to do the operation below in a single line efficiently
if real(A) equal to zero: imag(A).*B , if imag(A) equal to zero: real(A).*B , if A equal to zero donot mutliply

second part 
for i running from 1 to value
p = parameter that will decide how many previous iterations to be checked with (for simpliciity lets take 2 of previous itertions)
A = A.*B
carry out first iteration
check if i-1 = 0 and i-2 <=0
then carry second iteration i+1
check if i-1  = 0 if not then compare each element of i+1 with i and if there are any changes store the elements and positions that dont change or those change
Compare each element of A(i+2) with A(i+1) and A(i) and check if there are any significant changes occuring (the resolution of change needs to be specified)
If no significant changes in some elements (as defined by resolution) of A(i+2) as compared to A(i+1) and A(i) donot carry out further multiplications replace it with stored values
Update the stored value

[James Tursa]

What is the main concern for you? Execution time? Or memory usage? The problem with checking whether a real or imaginary part of a complex variable is zero in MATLAB is that it causes a data copy to take place. The time and resources needed for this data copy could outweigh any savings you would get by not doing the multiply. So it might be faster to just do the entire multiply (particularly since this is a multi-threaded operation) unless there are NaN or Inf issues you want to avoid. If you still think this is critical then a mex routine could avoid the data copy, but that means programming in C which you might not want to do.

[Stephen23]

" I want to handle this checking my self to save the multiplications. I want to do this checking efficiently."

Why do you imagine that MATLAB does this multiplication inefficiently?

[D_coder]

My main concern is to save the multiplications. For the time being I am not concerned with the execution time,

[Walter Roberson]

Remember to detect the cases where one or both operands to the potential multiplication are integers in which case you can convert the multiplications to repeated additions. And remember to put in a cache to detect multiplications that have already been done so you can retrieve the result instead of calculating it.

Since, after all, all you care about is the absolute number of multiplications, not about execution time or memory usage.