[SciPy-User] sqrtm is too slow for matrices of size 1000

[Paul Blelloch]

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.
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.scipy.org/pipermail/scipy-user/attachments/20130525/13e3d2e4/attachment.html>