Speed ​​up sparse matrix calculations

Question

Is it possible to speed up the calculation of large sparse matrices, for example. optimal brackets?

I ask: can I speed up the following code by forcing Matlab to perform operations in the specified order (for example, from right to left or something like that)?

I have a sparse square symmetric matrix H that was previously factorized, and a sparse vector M with a length equal to dimension H. What I want to do is this:

EDIT:. Additional information: H usually 4000x4000. The calculations of z and c are performed approximately 4000 times, while the calculation of dVa and dVaComp is performed 10 times for every 4000 cycles, thus 40,000. (DVa and dVaComp are solved iteratively, where P_mis is updated).

Here M*c*M' , will become a sparse matrix with 4 nonzero entries. In Matlab:

 [LUP] = lu(H); % H is sparse (thus also L, U and P) % for i = 1:4000 % Just to illustrate M = sparse([bf bt],1,[1 -1],n,1); % Sparse vector with two non-zero elements in bt and bf z = -M'*(U \ (L \ (P * M))); % M^t*H^-1*M = a scalar c = (1/dyp + z)^-1; % dyp is a scalar % while (iterations < 10 && ~=converged) dVa = - (U \ (L \ (P * P_mis))); dVaComp = (U \ (L \ (P * M * c * M' * dVa))); % Update P_mis etc. % end while % end for 

And for the record: Despite the fact that I use the inversion of H many times, it does not accelerate its preliminary calculation.

Thanks =)

Answer 1

Here are a few things that I don’t quite understand:

• Team M = sparse([tf],[1 -1],1,n,1); cannot be right; you say that in rows t,f and in columns 1,-1 should be 1 ; column -1 obviously cannot be right.
• The result of dVaComp is the full matrix due to multiplication by P_mis , while you say that it should be sparse.

Leaving these issues aside for now, I see a few minor optimizations:

• You use inv(H)*M twice so that you can pre-compute this.
• negation of dVa can be deduced from the cycle.
• if you do not explicitly need dVa , leave the variable assignment as well.
• inversion of a scalar tool dividing 1 by this scalar (calculation of c ).

Introducing the changes and trying to compare is enough (I used only 40 iterations to keep the total time small):

 %% initialize clc N = 4000; % H is sparse, square, symmetric H = tril(rand(N)); H(H<0.5) = 0; % roughly half is empty H = sparse(H+H.'); % M is sparse vector with two non-zero elements. M = sparse([1 N],[1 1],1, N,1); % dyp is some scalar dyp = rand; % P_mis = full vector P_mis = rand(N,1); %% original method [L, U, P] = lu(H); tic for ii = 1:40 z = -M'*(U \ (L \ (P*M))); c = (1/dyp + z)^-1; for jj = 1:10 dVa = -(U \ (L \ (P*P_mis))); dVaComp = (U \ (L \ (P*M * c * M' * dVa))); end end toc %% new method I [L,U,P,Q] = lu(H); tic for ii = 1:40 invH_M = U\(L\(P*M)); z = -M.'*invH_M; c = -1/(1/dyp + z); for jj = 1:10 dVaComp = c * (invH_M*M.') * ( U\(L\(P*P_mis)) ); end end toc 

This gives the following results:

 Elapsed time is 60.384734 seconds. % your original method Elapsed time is 33.074448 seconds. % new method 

Answer 2

You might want to use the extended syntax for lu when factorizing the (sparse) matrix H :

 [L,U,P,Q] = lu(H); 

An additional permutation matrix Q reorders the columns to increase the sparseness of the factors L,U (while the permutation matrix P only reorders the rows for partial rotation).

The specific results depend on the sparseness pattern H , but in many cases the use of good column permutation significantly reduces the number of nonzero factorization, decreasing memory usage and increasing speed.

Read more about lu syntax here .