0
242
Views¿Cómo puedo vectorizar la multiplicación de matriz aproximada usando la suma de los productos externos?
Suponga que tengo dos matrices, A y B , y quiero calcular C = AB usando la suma de los productos externos. He escrito esta función para lograr eso, pero me pregunto si puedo eliminar el bucle for y vectorizarlo,
import numpy as np def mul_opx(A, B, pd): # Approx. matrix multiplication using outer product n, m = A.shape p = B.shape[1] C = np.zeros((n,p), dtype=A.dtype) dum = np.zeros_like(C) for t in range(m): dum = np.outer(A[:,t],B[t,:]) / pd[t] C = C + dum C = C / m return C d = 1000 A = np.arange(d**2).reshape((d,d)) B = np.arange(d**2).reshape((d,d)) # Full Matrix Multiplication C = A @ B # Approximate Matrix Multiplication # choosing half random vectors/rows from A/B k = np.random.choice(d, int(d/2)) Ap = A[:,k] Bp = B[k,:] # Unifrom probability vector pd_uniform = np.full(d,1/d) # Approximate product C_hat = mul_opx(Ap,Bp, pd_uniform[k])Este tipo de producto es útil cuando las dimensiones de la matriz son muy grandes, digamos 10^6 x 10^6
1 answers
Answer question0
Como otros han mencionado, este podría ser un buen caso de uso para einsum . Escribir su operación en ese idioma se puede hacer con
np.einsum( 'ij,ik->jk',A,B) Índice i repetido para la suma y j k no repetido para el producto exterior. Un punto de referencia rápido parece mostrar una aceleración de 2x en comparación con la respuesta propuesta de @Tomer. Por supuesto, esto dependerá del tamaño de entrada y te dejo ver cómo se generaliza a tamaños lineales en el rango de 10 ^ 6, la huella de memoria también debería ser mejor con el einsum.
