<commit_before>import numpy
import logging
import scipy.sparse
import scipy.sparse.linalg
import scipy.linalg
from apgl.util.Util import Util 

class Nystrom(object):
    """
    A class to find approximations based on the Nystrom method.
    """

    def __init__(self):
        pass

    @staticmethod
    def eig(X, n):
        """
        Find the eigenvalues and eigenvectors of an indefinite symmetric matrix X.

        :param X: The matrix to find the eigenvalues of.
        :type X: :class:`ndarray`

        :param n: If n is an int, then it is the number of columns to sample otherwise n is an array of column indices. 
        """
        logging.warn("This method can result in large errors with indefinite matrices")

        if type(n) == int:
            inds = numpy.sort(numpy.random.permutation(X.shape[0])[0:n])
        else:
            inds = n
        invInds = numpy.setdiff1d(numpy.arange(X.shape[0]), inds)

        A = X[inds, :][:, inds]
        B = X[inds, :][:, invInds]
        
        Am12 = numpy.linalg.inv(scipy.linalg.sqrtm(A))
        #Am12 = Util.matrixPowerh(A, -0.5)
        S = A + Am12.dot(B).dot(B.T).dot(Am12)

        lmbda, U = numpy.linalg.eig(S)
        Ubar = numpy.r_[U, B.T.dot(U).dot(numpy.diag(1/lmbda))]
        Z = Ubar.dot(numpy.diag(lmbda**0.5))
        sigma, F = numpy.linalg.eig(Z.T.dot(Z))
        V = Z.dot(F).dot(numpy.diag(sigma**-0.5))

        return sigma, V

    @staticmethod
    def eigpsd(X, n):
        """
        Find the eigenvalues and eigenvectors of a positive semi-definite symmetric matrix.
        The input matrix X can be a numpy array or a scipy sparse matrix. In the case that
        n==X.shape[0] we convert to an ndarray. 

        :param X: The matrix to find the eigenvalues of.
        :type X: :class:`ndarray`

        :param n: If n is an int, then it is the number of columns to sample otherwise n is an array of column indices.

        :return lmbda: The set of eigenvalues 
        :return V: The matrix of eigenvectors as a ndarray
        """
        if type(n) == int:
            inds = numpy.sort(numpy.random.permutation(X.shape[0])[0:n])
        else:
            inds = n 
        invInds = numpy.setdiff1d(numpy.arange(X.shape[0]), inds)

        if numpy.sort(inds).shape[0] == X.shape[0] and (numpy.sort(inds) == numpy.arange(X.shape[0])).all():
            if scipy.sparse.issparse(X):
                X = numpy.array(X.todense())
            lmbda, V = numpy.linalg.eigh(X)
            return lmbda, V

        tmp = X[inds, :] 
        A = tmp[:, inds]
        B = tmp[:, invInds]

        if scipy.sparse.issparse(X): 
            A = numpy.array(A.todense())
            BB = numpy.array((B*B.T).todense())
        else:
            BB = B.dot(B.T)

        Am12 = scipy.linalg.sqrtm(numpy.linalg.pinv(A)) 
        #Am12 = Util.matrixPowerh(A, -0.5)
        S = A + Am12.dot(BB).dot(Am12)
        S = (S.T + S)/2

        lmbda, U = numpy.linalg.eigh(S)
          
        tol = 10**-10
        
        lmbdaN = lmbda.copy()
        lmbdaN[numpy.abs(lmbda) < tol] = 0
        lmbdaN[numpy.abs(lmbda) > tol] = lmbdaN[numpy.abs(lmbda) > tol]**-0.5
        
        V = X[:, inds].dot(Am12.dot(U)*lmbdaN)
        
        return lmbda, V

    @staticmethod 
    def matrixApprox(X, n):
        """
        Compute the matrix approximation using the Nystrom method.

        :param X: The matrix to approximate.
        :type X: :class:`ndarray`

        :param n: If n is an int, then it is the number of columns to sample otherwise n is an array of column indices.
        """
        if type(n) == int:<commit_msg>Use matrixPowerh which is faster and passes all tests. <commit_after>import numpy
import logging
import scipy.sparse
import scipy.sparse.linalg
import scipy.linalg
from apgl.util.Util import Util 

class Nystrom(object):
    """
    A class to find approximations based on the Nystrom method.
    """

    def __init__(self):
        pass

    @staticmethod
    def eig(X, n):
        """
        Find the eigenvalues and eigenvectors of an indefinite symmetric matrix X.

        :param X: The matrix to find the eigenvalues of.
        :type X: :class:`ndarray`

        :param n: If n is an int, then it is the number of columns to sample otherwise n is an array of column indices. 
        """
        logging.warn("This method can result in large errors with indefinite matrices")

        if type(n) == int:
            inds = numpy.sort(numpy.random.permutation(X.shape[0])[0:n])
        else:
            inds = n
        invInds = numpy.setdiff1d(numpy.arange(X.shape[0]), inds)

        A = X[inds, :][:, inds]
        B = X[inds, :][:, invInds]
        
        Am12 = numpy.linalg.inv(scipy.linalg.sqrtm(A))
        #Am12 = Util.matrixPowerh(A, -0.5)
        S = A + Am12.dot(B).dot(B.T).dot(Am12)

        lmbda, U = numpy.linalg.eig(S)
        Ubar = numpy.r_[U, B.T.dot(U).dot(numpy.diag(1/lmbda))]
        Z = Ubar.dot(numpy.diag(lmbda**0.5))
        sigma, F = numpy.linalg.eig(Z.T.dot(Z))
        V = Z.dot(F).dot(numpy.diag(sigma**-0.5))

        return sigma, V

    @staticmethod
    def eigpsd(X, n):
        """
        Find the eigenvalues and eigenvectors of a positive semi-definite symmetric matrix.
        The input matrix X can be a numpy array or a scipy sparse matrix. In the case that
        n==X.shape[0] we convert to an ndarray. 

        :param X: The matrix to find the eigenvalues of.
        :type X: :class:`ndarray`

        :param n: If n is an int, then it is the number of columns to sample otherwise n is an array of column indices.

        :return lmbda: The set of eigenvalues 
        :return V: The matrix of eigenvectors as a ndarray
        """
        if type(n) == int:
            inds = numpy.sort(numpy.random.permutation(X.shape[0])[0:n])
        else:
            inds = n 
        invInds = numpy.setdiff1d(numpy.arange(X.shape[0]), inds)

        if numpy.sort(inds).shape[0] == X.shape[0] and (numpy.sort(inds) == numpy.arange(X.shape[0])).all():
            if scipy.sparse.issparse(X):
                X = numpy.array(X.todense())
            lmbda, V = numpy.linalg.eigh(X)
            return lmbda, V

        tmp = X[inds, :] 
        A = tmp[:, inds]
        B = tmp[:, invInds]

        if scipy.sparse.issparse(X): 
            A = numpy.array(A.todense())
            BB = numpy.array((B*B.T).todense())
        else:
            BB = B.dot(B.T)
        
        #Following line is very slow 
        #Am12 = scipy.linalg.sqrtm(numpy.linalg.pinv(A)) 
        Am12 = Util.matrixPowerh(A, -0.5)
        S = A + Am12.dot(BB).dot(Am12)
        S = (S.T + S)/2

        lmbda, U = numpy.linalg.eigh(S)
          
        tol = 10**-10
        
        lmbdaN = lmbda.copy()
        lmbdaN[numpy.abs(lmbda) < tol] = 0
        lmbdaN[numpy.abs(lmbda) > tol] = lmbdaN[numpy.abs(lmbda) > tol]**-0.5
        
        V = X[:, inds].dot(Am12.dot(U)*lmbdaN)
        
        return lmbda, V

    @staticmethod 
    def matrixApprox(X, n):
        """
        Compute the matrix approximation using the Nystrom method.

        :param X: The matrix to approximate.
        :type X: :class:`ndarray`

        :param n: If n is an int, then it is the number of columns to sample otherwise n is an array of column indices.
        """
        if type(n) == int:
{'fraction_non_alphanumeric': 0.12547632008709853, 'fraction_numerical': 0.012792596624931955, 'mean_word_length': 1.9384246301479409, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 7, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1839657', 'n_tokens_mistral': 2683, 'n_tokens_neox': 2555, 'n_words': 701}