Как я могу решить систему линейных уравнений в python быстрее, чем с помощью numpy.linalg.lstsq?

Question

Я пытаюсь решить линейную систему, охватывающую несколько сотен тысяч и двухсот тысяч уравнений с помощью numpy.linalg.lstsq, но занимает слишком много времени.Что я могу сделать, чтобы ускорить это?

Матрица разрежена с сотнями столбцов (размеры приблизительно 150 000 x 140), и система переопределена.

Answer 1

Если ваша матрица коэффициентов редка, используйте "spsolve" из "scipy.sparse.linalg".

Answer 2

Вот немного импровизированной хитрости, которая значительно ускоряет вычисления на случайных данных указанных размеров.

Я даже не представляю, насколько это численно звучит.

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