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

Question

У меня есть уравнение

Ax= К

Где A и B - трехдиагональные матрицы. Я хочу рассчитать матрицу

C=inv (A).B

Существуют разные x,s, которые дают разные y, s, поэтому вычисление C удобно.

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

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

Спасибо

Answer 1

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

Answer 2

scipy.linalg.solve_banded - это оболочка для LAPACK, которая, в свою очередь, должна вызывать MKL. Кажется, запустить 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