如何在python中求解线性方程组比使用numpy.linalg.lstsq更快?

Question

我正在尝试用numpy.linalg.lstsq求解一个跨越十万到二十万方程的线性系统，但花了太长时间。我能做些什么来加快速度？

矩阵稀疏，有数百列(维度约为 150 000 x 140(，系统已过度确定。

Answer 1

这里有一些即兴的技巧，可以大大加快对指定维度的随机数据的计算速度。

不过，我不知道这在数字上听起来有多好。

import numpy as np
from time import perf_counter
def lstsq(A, b):
AA = A.T @ A
bA = b @ A
D, U = np.linalg.eigh(AA)
Ap = (U * np.sqrt(D)).T
bp = bA @ U / np.sqrt(D)
return np.linalg.lstsq(Ap, bp, rcond=None)
# create random data
A = np.random.random((150_000, 140))
b = np.random.random((150_000,))
# use solver directly
t = perf_counter()
x, *info = np.linalg.lstsq(A, b, rcond=None)
s = perf_counter()
print('direct method:     ', s-t, 'seconds')
# use equivalent reduced system
t = perf_counter()
x_acc, *info_acc = lstsq(A, b)
s = perf_counter()
print('accelerated method:', s-t, 'seconds')
print('results equal:', np.allclose(x, x_acc))

示例运行：

direct method:      3.032766239999546 seconds
accelerated method: 0.20947745100056636 seconds
results equal: True

Answer 2

如果你的系数矩阵是稀疏的，请使用"scipy.sparse.linalg"中的"spsolve"。