Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Performance issue: scipy.linalg.solve_toeplitz is slow for T,x,b being matrices #8619

Open
djgarde opened this issue Mar 26, 2018 · 2 comments
Labels
defect A clear bug or issue that prevents SciPy from being installed or used as expected scipy.linalg

Comments

@djgarde
Copy link

djgarde commented Mar 26, 2018

I am trying to efficiently solve the following linear system in Python 3.6:

b = T x

where T is an N x N Toeplitz matrix and x, b are N x N matrices. It is much slower than both scipy.linalg.solve and numpy.linalg.solve (see the output from my test script for N=500).

A possible explanation is that scipy.linalg.solve_toeplitz uses a for-loop for matrix inputs to solve the individual linear systems with x, b being vectors (solving each column at a time). Unfortunately, i was unable to make the benchmark work from the original pull request adding this function.

Reproducing code example:

"""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 = T x, where T 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)
T = scipy.linalg.toeplitz(c, r)
b = T.dot(x)

# Validate various solutions
x_sol = []
x_sol.append(('numpy.linalg.solve(T, b)', numpy.linalg.solve(T, b)))
x_sol.append(('scipy.linalg.solve(T, b)', scipy.linalg.solve(T, 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)

Test output:

Method: numpy.linalg.solve(T, b) - error: 5.996096106604476e-11
Method: scipy.linalg.solve(T, b) - error: 5.5520852583734864e-11
Method: scipy.linalg.solve_toeplitz((c, r), b) - error: 2.761917504645538e-08
Timings:
[0.008001089096069336, 0.44705653190612793, 0.2655336856842041]

Scipy/Numpy/Python version information:

'0.19.1', '1.13.3', sys.version_info(major=3, minor=6, micro=3, releaselevel='final', serial=0)
@ilayn ilayn added defect A clear bug or issue that prevents SciPy from being installed or used as expected scipy.linalg labels Mar 27, 2018
@SebastianSemper
Copy link

I have some additional information on this long standing issue

import numpy as np
import scipy.linalg as spl
import timeit
import matplotlib.pyplot as plt

N = np.unique(np.exp(np.linspace(1, 5, 20)).astype(np.int64))
print(N)
n = 257

M = spl.toeplitz(np.random.randn(n))

resA = []
resB = []

for nn in N:
    x = np.random.randn(n, nn)
    x1 = np.asfortranarray(x)

    def A():
        spl.solve(M, x, check_finite=False)
    def B():
        spl.solve_toeplitz(M[:,0], x, check_finite=False)

    resA.append(np.mean(timeit.repeat(A, repeat=5, number=5)))
    resB.append(np.mean(timeit.repeat(B, repeat=5, number=5)))

plt.loglog(N, resA, label="solve")
plt.loglog(N, resB, label="solve_toeplitz")
plt.legend()
plt.show()

This produces the following results

Screenshot_20210308_164635

scipy has version '1.4.1' and numpy '1.18.5'.

@mdhaber
Copy link
Contributor

mdhaber commented Mar 8, 2021

Still true in master w/ OpenBLAS 0.3.7 built from source on Windows. And SciPy 1.6.1 w/ mkl 2020.2, both installed from conda.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
defect A clear bug or issue that prevents SciPy from being installed or used as expected scipy.linalg
Projects
None yet
Development

No branches or pull requests

4 participants