Осциллирующее рассеянное матричное вырождение: a ** 16 медленнее, чем a * a * a * a * a * a * a * a * a * a * a * a * a * a * a * a?

Я делаю простой разреженный рост матрицы, a**16, используя scipy-0.17. (Обратите внимание, что не умножение по элементам). Однако на моих машинах (работает стабилизатор Debian и Ubuntu LTS) это в десять раз медленнее, чем использование цикла for или что-то глупое, как a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a. Это не имеет смысла, поэтому я предполагаю, что я делаю что-то неправильно, но что?

import scipy.sparse
from time import time

a=scipy.sparse.rand(2049,2049,.002)

print ("Trying exponentiation (a**16)")
t=time()
x=a**16
print (repr(x))
print ("Exponentiation took %f seconds\n" % (time()-t))

print ("Trying expansion (a*a*a*...*a*a)")
t=time()
y=a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a
print (repr(y))
print ("Expansion took %f seconds\n" % (time()-t))

print ("Trying a for loop (z=z*a)")
t=time()
z=scipy.sparse.eye(2049)
for i in range(16):
    z=z*a
print (repr(z))
print ("Looping took %f seconds\n" % (time()-t))

# Sanity check, all approximately the same answer, right? 
assert (abs(x-z)>=1e-9).nnz==0
assert (abs(x-y)>=1e-9).nnz==0

Ответы

Ответ 1

@hpaulj комментарий о количестве ненулевых значений. Когда вы вычисляете более высокие значения a, количество ненулевых элементов увеличивается. Для разреженных матриц время вычисления матрицы произведение увеличивается с числом ненулевых элементов.

Алгоритм, используемый для вычисления a**16, в действительности:

a2 = a*a
a4 = a2*a2
a8 = a4*a4
a16 = a8*a8

Теперь посмотрим на количество ненулевых элементов в этих матрицах для a = sparse.rand(2049, 2049, 0.002):

matrix      nnz    fraction nnz
  a        8396       0.0020
  a2      34325       0.0082
  a4     521593       0.1240
  a8    4029741       0.9598

В последнем продукте a16 = a8*a8 коэффициенты 96% отличны от нуля. вычисления этот продукт с использованием разреженного умножения матрицы медленный. Этот последний шаг занимает 97% времени для вычисления a**16.

С другой стороны, когда вы вычисляете a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a, разреженное умножение матрицы выполняется 15 раз, но одно факторов в каждом продукте всегда имеет небольшую долю (0,002) ненулевых значений, поэтому каждый продукт может быть выполнен разумно эффективно.

Это говорит о том, что существует, вероятно, оптимальная стратегия для вычисления продукта, балансируя количество умножений против разреженности факторов. Например, вычисление a2 = a*a; a16 = a2*a2*a2*a2*a2*a2*a2*a2 выполняется быстрее, чем a16 = a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a:

In [232]: %timeit a2 = a*a; a4 = a2*a2; a8 = a4*a4; a16 = a8*a8
14.4 s ± 199 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

In [233]: %timeit a16 = a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a
1.77 s ± 4.78 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

In [234]: %timeit a2 = a*a; a16 = a2*a2*a2*a2*a2*a2*a2*a2
1.42 s ± 3.16 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

Или, поскольку вы знаете, что конечный результат будет плотным, переключитесь на стандартные массивы numpy, начиная с начала или на каком-то промежуточном этапе, при котором плотное умножение матрицы будет более эффективным, чем разреженное умножение матрицы.