I looked at the rest of the algorithm, and Scipy and Matlab appear to be doing nearly the same thing. In Scipy there are three nested for loops as follows:

for j in range(n):

R[j,j] = sqrt(T[j,j])

for i in range(j-1,-1,-1):

s = 0

for k in range(i+1,j):

s = s + R[i,k]*R[k,j]

R[i,j] = (T[i,j] - s)/(R[i,i] + R[j,j])

While in Matlab it's two nested loops as follows:

    for j=1:n
        R(j,j) = sqrt(T(j,j));
        for i=j-1:-1:1
            k = i+1:j-1;
            s = R(i,k)*R(k,j);
            R(i,j) = (T(i,j) - s)/(R(i,i) + R(j,j));
        end
    end

The difference is that Matlab is replacing the inner loop by a Vector multiply of a slice of the matrix. This is where the speed difference may be. So if you're feeling adventurous you could try to do the same thing.

On Saturday, April 13, 2013 8:47:25 AM UTC-7, Vivek Kulkarni wrote:

Hi,
I am implementing spectral clustering for my course work and am using the sqrtm function to find the square root of a matrix . But its far too slow, my matrix is of size (1258,1258). Any suggestions on how I can speed things up or some other function that scipy supports which can be used.

I am implementing the algorithm as described here:
http://books.nips.cc/papers/files/nips14/AA35.pdf

Finding the square root of D^(-1) is way too slow for D^-1 of size (1258,1258).

Thanks.
Vivek.