__author__ = 'chunk'

import numpy as np
import math


def calc_upper(U, b):
    n = len(U)
    assert len(b) == n
    x = [0.0] * n
    for i in reversed(range(n)):
        if U[i][i] == 0:
            raise Exception('u_ii == 0')
        x[i] = b[i]
        for j in reversed(range(i + 1, n)):
            x[i] -= U[i][j] * x[j]
        x[i] /= U[i][i]
    return x


def calc_lower(L, b):
    n = len(L)
    assert len(b) == n
    x = [0.0] * n
    for i in range(n):
        if L[i][i] == 0:
            raise Exception('l_ii == 0')
        x[i] = b[i]
        for j in range(i):
            x[i] -= L[i][j] * x[j]
        x[i] /= L[i][i]
    return x


def gen_hilbert(n):
    return np.array([1.0 / (i + j + 1) for i in range(n) for j in range(n)]).reshape((n, -1))


def gen_b(n, x=None):
    if x == None:
        x = [1] * n
    return np.dot(gen_hilbert(n), x)


def norm(l):
    s = 0
    for item in l:
        if np.absolute(item) > s:
            s = np.absolute(item)
    return s


def cholesky(A):
    n = len(A)
    for j in range(n):
        for k in range(j):
            A[j][j] -= (A[j][k] * A[j][k])
        A[j][j] = math.sqrt(A[j][j])

        for i in range(j + 1, n):
            for k in range(j):
                A[i][j] -= (A[i][k] * A[j][k])
            A[i][j] /= A[j][j]

    return np.array(A)


def calculate0(n):
    H = gen_hilbert(n)
    b = gen_b(n)
    L = cholesky(H)
    y = calc_lower(L, b)
    x = calc_upper(L.T, y)
    # validate:
    # print np.dot(H, x) - b
    return x, b - np.dot(H, x), [x[i] - 1.0 for i in range(n)]


def calculate1(n):
    H = gen_hilbert(n)
    b = gen_b(n)
    b_t = np.copy(b)
    b_t[-1] += math.pow(10, -7)
    L = cholesky(H)
    y = calc_lower(L, b_t)
    x = calc_upper(L.T, y)
    # validate:
    # print np.dot(H, x) - b
    return x, b - np.dot(H, x), [x[i] - 1.0 for i in range(n)]


def test():
    print gen_hilbert(3)
    print gen_b(5)

    U = [[1, -0.7, 0], [0, 1, -60], [0, 0, 155]]
    b = [0.7, -61, 155]
    print calc_upper(U, b)

    L = [[1, 0, 0], [-60, 1, 0], [0, -0.7, 1]]
    b = [1, -61, 0.7]
    print calc_lower(L, b)

    A = [[5, -1, -1], [-1, 3, -1], [-1, -1, 5]]
    print cholesky(A)


def test1():
    print "[origin(n=10)]"
    x, r, delta = calculate0(10)
    print "x:%s\nr:%s\ndelta:%s" % (x, r, delta)
    print "norm(r):%s\nnorm(delta):%s" % (norm(r), norm(delta))

    print "[disturbed(n=10)]"
    x, r, delta = calculate1(10)
    print "x:%s\nr:%s\ndelta:%s" % (x, r, delta)
    print "norm(r):%s\nnorm(delta):%s" % (norm(r), norm(delta))

    print "[n=8]"
    x, r, delta = calculate0(8)
    print "x:%s\nr:%s\ndelta:%s" % (x, r, delta)
    print "norm(r):%s\nnorm(delta):%s" % (norm(r), norm(delta))

    print "[n=12]"
    x, r, delta = calculate0(12)
    print "x:%s\nr:%s\ndelta:%s" % (x, r, delta)
    print "norm(r):%s\nnorm(delta):%s" % (norm(r), norm(delta))


if __name__ == '__main__':
    # test()
    test1()
    pass