Инверсия трехдиагональная матрица

Question

Я имею уравнение

Ax = По

где А и В являются трехдиагональными. Я хочу, чтобы вычислить матрицу

C = Inv (A) .B

существуют различные X, S, который даст различный у, з, следовательно, вычисление C удобно.

Может кто-нибудь, пожалуйста, скажите мне более быстрый способ вычисления инверсии. Я использую Python 3.5 и предпочитаю использовать любой метод из numpy. Если это невозможно, я могу использовать scipy или cython в качестве второго и третьего вариантов.

Я видел другие подобные вопросы, но они не полностью соответствуют моей проблеме.

Спасибо

Answer 1

Есть много методов, чтобы сделать это, в любом случае один из самых простых является алгоритм матрицы Трехдиагональная см Wiki page. Этот алгоритм работает в O (n) времени, в Numpy есть простая реализация в следующем Github link. Однако, вы можете думать, чтобы реализовать самостоятельно одним из известных алгоритмов, например, что-то вроде LU factorization

Answer 2

scipy.linalg.solve_banded является оболочкой для LAPACK, которая должна в МКЛ очередь вызовов. Кажется, что работает O (N). Для тривиального примера, чтобы показать синтаксис

a = np.array([[1,2,0,0], [-1,2,1,0], [0,1,3,1], [0,0,1,2]]) 
    x = np.array([1,2,3,4]) 
    b = np.dot(a,x) 
    ab = np.empty((3,4)) 
    ab[0,1:] = np.diag(a,1) 
    ab[1,:] = np.diag(a,0) 
    ab[2,:-1] = np.diag(a,-1) 
    y = solve_banded((1,1),ab,b) 
    print y