FGM

#Fast Gradient method

import numpy as np
import time
from scipy.sparse import csr_matrix

prograph = open('probability graph.txt')
starttime = time.time()

def read(graph): #matrix reading
    global n
    n = int(graph.readline()) 
    data = [[] for i in range(n)]
    for i in range(n):
        data[i] = list(map(float, graph.readline().split()))
        data[i][i] -= 1
    data = np.array(data)
    data = data.T
    ones = np.array([1 / n] * n)
    data = np.row_stack((data, ones))
    data = csr_matrix(data)
    return data

def norma(vector): #2-norma
    return np.linalg.norm(vector, 2)

def f(x): #f(x) - permanent function
    return 0.5 * norma(A.dot(x) - b) ** 2

def grad(x): #return gradient of f(x) = 0.5 * norma(A * x) ** 2
    return A.T.dot(A.dot(x) - b)

def f_(xnew, x, L, gradi): #f(x) - inspection function
    return f(x) + np.dot(gradi, xnew - x) + (L * norma(xnew - x) ** 2 / 2)

def main():
    global A, n, x, b
    A = read(prograph)
    k = 0
    b = np.array([0] * (n + 1))
    b[-1] = 1.0
    b = b / n
    x = np.array([0] * n)                 #PageRank vector
    x[0] = 1.0
    EPS = 10 ** (-3)                      #accuracy
    L = 10
    firstage = time.time()
    print(firstage - starttime)
    y = x.copy()
    z = x.copy()
    ynew = (2 * z + k * x) / (k + 2)
    grady = grad(ynew)
    xnew = ynew - grady / L
    znew = z - (k + 2) * grady / (2 * L)
    k += 1
    while f(x) > EPS:
        while f_(xnew, ynew, L, grady) < f(xnew):
            L *= 2
            grady = grad(ynew)
            xnew = ynew - grady / L
            znew = z - (k + 2) * grady / (2 * L)
        x, y, z = xnew, ynew, znew
        grady = grad(ynew)
        L /= 2
        k += 1
        ynew = (2 * z + k * x) / (k + 2)
        xnew = ynew - grady / L
        znew = z - (k + 2) * grady / (2 * L)
    x = x / x.sum()
    print(f(x))
    print(time.time() - firstage)

main()