MATLAB: How to make CONDEST run faster for a large (2,000,000×2,000,000) sparse (density 1e-6) SPD matrix in MATLAB R2011b (7.13)

22normcholcholeskycondcondestMATLABnormsparse

I am using CONDEST to find the condition number of a large (2000000 square) sparse (density 1e-6) matrix that I know to be symmetric positive definite. The operation takes a while and uses a lot of memory. I would like to find a faster method to use in my situation.

Best Answer

If you know that your matrix is SPD, you can use the lower triangular Cholesky factor rather than the LU decomposition method employed by CONDEST and use this to build a modified version of CONDEST. The following function, MYCONDEST, implements this method:
function [c, v] = mycondest(A,t)
if nargin < 2, t = []; end
[L,~,~] = chol(A,'lower','vector');
[Ainv_norm, ~, v] = normest1(@condestf,t); 
A_norm = norm(A,1);
c = Ainv_norm*A_norm;
v = v/norm(v,1);
      function f = condestf(flag, X)
         if isequal(flag,'dim')
             f = max(size(L));
         elseif isequal(flag,'real')
             f = isreal(L);
         elseif isequal(flag,'notransp')
             f = L'\(L\X);
         elseif isequal(flag,'transp')
             f = L'\(L\X);
         end
     end
end
You can download the attached M-file for this function.
Note that you can check if you can tolerate the Cholesky factorization by using symbfact:
count = symbfact(A);
sum(count)
This tells you exactly how many elements are in the factor, and therefore the amount of memory required to store it. On a 64-bit machine, the amount of memory required to store any double sparse matrix A is 16*nnz(A) + 8*size(A,2) + 8 (this is the number of bytes displayed by whos).
Related Question