Scipy Sparse Matrix - Dense Vector Multiplication Performance - Blocks vs Large Matrix

Question

Ho un numero di matrici sparse scipy (attualmente in formato CSR) che ho bisogno di moltiplicare con un vettore 1D denso e denso. Il vettore è chiamato G:

print G.shape, G.dtype 
(2097152,) complex64 

Ogni matrice sparsa ha forma (16384,2097152) ed è molto scarsa. La densità è approssimativamente 4.0e-6. Ho una lista di 100 di queste matrici sparse chiamate spmats.

posso facilmente moltiplicare ciascuna matrice con G modo:

res = [spmat.dot(G) for spmat in spmats] 

Ciò si traduce in un elenco di vettori densi di forma (16384,) come previsto.

mia domanda è abbastanza perfomance critico, e quindi cercato un alternativo, che è per concatenare prima tutte le matrici sparse in una grande matrice scarsa, e quindi utilizzare solo una chiamata di dot() modo:

import scipy.sparse as sp 
SPMAT = sp.vstack(spmats, format='csr') 
RES = SPMAT.dot(G) 

Questo risulta in un vettore lungo RES che ha la forma (1638400,) ed è una versione concatenata di tutti i vettori di risultato in res sopra, come previsto. Ho controllato che i risultati sono identici.

Forse ho sbagliato completamente, ma mi aspettavo che il secondo caso fosse più veloce del primo, dal momento che ci sono molte meno chiamate numpy, allocazioni di memoria, creazione di oggetti python, loop python, ecc. Io non preoccuparsi del tempo necessario per concatenare le matrici sparse, solo il tempo per calcolare il risultato. Secondo %timeit, però:

%timeit res = [spmat.dot(G) for spmat in spmats] 
10 loops, best of 3: 91.5 ms per loop 
%timeit RES = SPMAT.dot(G) 
1 loops, best of 3: 389 ms per loop 

Ho controllato che non sto a corto di memoria in entrambe le operazioni, e niente pesce sembra essere in corso. Sono pazzo o è davvero strano? Questo significa che tutti i prodotti sparsi del vettore matrice dovrebbero essere fatti in blocchi, poche righe alla volta, per renderli più veloci? Per quanto ho capito, il tempo di moltiplicazione della matrice sparsa con un vettore denso dovrebbe essere lineare nel numero di elementi diversi da zero, che è invariato nei due casi precedenti. Cosa potrebbe fare questa differenza?

sono in esecuzione su una singola macchina nucleo Linux con 4GB ram, utilizzando EPD7.3

EDIT:

Ecco un piccolo esempio che riproduce il problema per me:

import scipy.sparse as sp 
import numpy as n 

G = n.random.rand(128**3) + 1.0j*n.random.rand(128**3) 

spmats = [sp.rand (128**2, 128**3, density = 4e-6, format = 'csr', dtype=float64) for i in range(100)] 
SPMAT = sp.vstack(spmats, format='csr') 

%timeit res = [spmat.dot(G) for spmat in spmats] 
%timeit RES = SPMAT.dot(G) 

ottengo:

1 loops, best of 3: 704 ms per loop 
1 loops, best of 3: 1.34 s per loop 

La differenza di prestazioni in questo caso non è così grande come con le mie matrici sparse che hanno una struttura (probabilmente a causa del caching) ma è ancora peggio concatenare le matrici.

Ho provato con entrambi scipy 10.1 e 12.0.

Answer 1

Non ho trovato una ragione per lo strano comportamento menzionato nella domanda, tuttavia ho trovato un modo per velocizzare il mio calcolo in modo significativo che potrebbe essere utile per altre persone.

Perché nel mio caso particolare sto calcolando il prodotto di una matrice sparsa float32 e un vettore denso di 64 complessi, posso moltiplicare separatamente i componenti reali e quelli immaginari. Questo mi fornisce un aumento di velocità 4x.

Questo richiede 2.35s con SPMAT.shape == (16384000, 2097152):

RES = SPMAT.dot(G) 

Mentre questo richiede solo 541ms:

RES = n.zeros((SPMAT.shape[0],),dtype=complex64) 
RES.real = SPMAT.dot(G.real); RES.imag = SPMAT.dot(G.imag) 

E il risultato è identico. Penso che forse la preallocazione n.zeros potrebbe non essere necessaria ma non so come altro fare questo.