How can I make CONDEST run faster for a large (2,000,000x2,000,000) sparse (density 1e-6) SPD matrix in MATLAB R2011b (7.13)?

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.

Answer 1

[MathWorks Support Team]

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).