Wie kann man die Effizienz meiner Python -Funktion mit spärlichen Matrizen verbessern? ⇐ Python

[Guest]

Ich möchte eine bestimmte Funktion in Python mit spärlichen Matrizen implementieren und sie so schnell wie möglich machen. Ich beschreibe ausführlich, was das Problem ist und wie ich es bisher implementiert habe. /strong> (Dimension wird festgelegt, Einträge festgelegt) spärliche Matrizen, die gemeinsam B jeweils der Größe 1000x1000 genannt werden (durchschnittliche Sparsamkeit, d. H. Anzahl der Einträge ungleich Null über alle Einträge, beträgt 0,0001 ) . Für einen bestimmten Vektor u (von Größe 1000 ) möchte ich c [j] = u @ b [j] @ u für jedes j = 0, ..., 999 berechnen und die Ausgabe sollte das numpy array c sein. Also sind die spärlichen Matrizen B [j] (im Tupel B gespeichert) behoben und U ist meine Funktionseingabe.
Meine bisherige Implementierung: Ich habe alle Matrizen vorkomputieren und sie als globale Variablen in meinem Programm behandeln. Ich habe mich entschlossen, sie als scipy.sparse matrices in csr_matrix format (ich habe gelesen, dass dies das beste Format ist, wenn ich nur Matrixvektorprodukte berechnen möchte) in einem Tupel . Um meine gewünschte Funktion zu berechnen, mache ich < /p>

Code: Select all

# precompute matrices, so treat them as global fixed variables
B = []
for j in range(1000):
sparse_matrix = ...compute it... # sparse csr_matrix of size 1000x1000
B.append(sparse_matrix)
B = tuple(B)

def func(u: np.ndarray) -> np.ndarray:
"""
u is a np.array of length N=1000
"""
return np.array([u.dot(B[k].dot(u.transpose())) for k in range(len(B))])

Frage: Ist dies das effizienteste, was es erhalten kann, oder sehen Sie den Raum für Verbesserungen in Bezug auf Geschwindigkeit, z. Ändern Sie die Struktur, wie ich die Matrizen sichere oder wie ich alle Vektor-Matrix-Vektor-Produkte berechne? Sehen Sie auch das Potenzial für eine Parallelisierung dieser Berechnung? Wenn ja, haben Sie einen Vorschlag, welche Bibliotheken/Funktionen ich mir ansehen sollte?
Danke im Voraus! stark> mit c [j] = u @ b [j] @ u Ich meine, ich möchte das Matrix-Vector-Produkt von B [j] und u und dann das dann berechnen inneres Produkt mit u . (Mathematisch u.Transponsed () * B * u )
Wenn es jemandem hilft. Hier ist ein kleines Benchmark -Programm, bei dem ich einige zufällige spärliche Matrizen erstelle und es an einem zufälligen Vektor bewertete. < /P>

Code: Select all

import numpy as np
from random import randint
from scipy.sparse import coo_matrix, csr_matrix
from time import time

# Create random tuple of sparse matrices
N = 1000
n = 100
B = []
for i in range(N):
data = np.random.uniform(-1, 1, n).tolist()
rows = [randint(0, N-1) for _ in range(n)]
cols = [randint(0, N-1) for _ in range(n)]
sparse_matrix = csr_matrix(coo_matrix((data, (rows, cols)), shape=(N, N)))
B.append(sparse_matrix)
B = tuple(B)

# My function
def func(u: np.ndarray) -> np.ndarray:
"""
u is a np.array of length N=1000
"""
return np.array([u.dot(B[k].dot(u.transpose())) for k in range(len(B))])

# random vector to evaluate function
u = np.random.uniform(-1, 1, N)

START = time()
func(u)
END = time()
print(f"Speed : {END - START}")
< /code>
>>> Speed : 0.005256175994873047