I am trying to efficiently solve the following linear system in Python 3.6:
b = A x
where A is an N x N Toeplitz matrix (that is, the left-to-right diagonals are constant) and x, b are N x N matrices. The Durbin-Levinson implemented in Scipy as scipy.linalg.solve_toeplitz should efficiently solve the above system utilizing the structure of A, and indeed it does this when x,b are vectors.
However, when x, b are matrices it is much slower than both scipy.linalg.solve and numpy.linalg.solve (see output from my test-script)
Execution time is critical in my application. What are my options for speeding up the process and perhaps utilizing the Toeplitz structure?
A possible explanation for scipy.linalg.solve_toeplitz being slow is that it uses a slow for-loop for matrix inputs to solve the individual linear systems with x, b being vectors (solving each column at a time).
"""This script serves to benchmark several methods for solving a
linear equation involving a Toeplitz matrix and determine which one is
faster.
We consider the equation: b = A x, where A is Toeplitz, b and x are matrices and we wish to
solve for x.
"""
import numpy as np
import numpy.linalg
import scipy.linalg
import time
N = 500
np.random.seed(1)
# Construct random vectors/matrices
x = np.random.rand(N, N)
c,r = np.random.rand(2, N)
A = scipy.linalg.toeplitz(c, r)
b = A.dot(x)
# Validate various solutions
x_sol = []
x_sol.append(('numpy.linalg.solve(A, b)', numpy.linalg.solve(A, b)))
x_sol.append(('scipy.linalg.solve(A, b)', scipy.linalg.solve(A, b)))
x_sol.append(('scipy.linalg.solve_toeplitz((c, r), b)', scipy.linalg.solve_toeplitz((c, r), b)))
for solution in x_sol:
print("Method: {} - error: {}".format(solution[0], numpy.linalg.norm(solution[1] - x)))
# Time the solutions
x_time = []
for solution in x_sol:
t_start = time.time()
eval(solution[0])
t_end = time.time()
x_time.append(t_end - t_start)
print("Timings:")
print(x_time)
Script output:
Method: numpy.linalg.solve(A, b) - error: 4.8794411236474704e-11
Method: scipy.linalg.solve(A, b) - error: 4.824494916488265e-11
Method: scipy.linalg.solve_toeplitz((c, r), b) - error: 2.7607739766053664e-08
Timings:
[0.08000469207763672, 0.03300189971923828, 0.6740384101867676]
Documentation: https://docs.scipy.org/doc/scipy-0.17.0/reference/generated/scipy.linalg.solve_toeplitz.html
