Wie Matrixprodukt auf (sparse) Bitmatrix effizient in Python

Question

Ordinary Matrixprodukt zwischen Bitfeld berechnen:

  1, 0, 0 
Matrix A = 1, 1, 1 
      0, 0, 1 

       1, 1, 0 
Transpose of A = 0, 1, 0 
       0, 1, 1 

C = Matrix A times (Transpose of Matrix A) 

    1, 1, 0 
C = 1, 3, 1 
    0, 1, 1 

A ist ein Bitfeld von 1 und 0. Die tatsächliche Matrix A ist groß und hat ungefähr 0,25% 1 Einträge und 99,75% Null Einträge.

C ist ein Array von Ganzzahl.

Wie berechnet man dies schnell ohne viel Speicher zu verwenden?

Derzeit verwende ich scipy's Sparse Matrix Multiplikation Routinen für komprimierte Sparse Zeilenmatrizen von Fließkomma 1.0 und 0.0 in Python. Ich versuche auch, c-Funktionen in mkl-Bibliothek direkt aufzurufen, um die Speichernutzung zu reduzieren.

Answer 1

Vorhandene Leistungsbibliotheken wie MKL verwenden immer float/double als Datentyp. Vergleicht man das Konvertieren von A in eine Float-CSR und dann den Aufruf von .dot() oder einigen MKL-Routinen, kann es sein, dass Sie Ihren eigenen bit-mat-mul Code schneller schreiben. Sie brauchen nicht einmal die Multiplikationsoperation. Es zählt nur die Bits.

bearbeiten

nach dem Kontext auf dem queation zu wissen, würde ich das folgende Verfahren vorschlagen.

1. Konvertieren Sie Ihr Array A in das CSR-Format und speichern Sie nur col-Indizes und row ptr;
2. Für jede Zeile i und Zeile j von A, zählen Sie die Anzahl der gemeinsamen col-Indizes und speichern Sie das Ergebnis in C (i, j) mit i < = j nur als C ist symmetrisch. Dies ist schnell, wenn col-Indizes sortiert werden.

Die dichte Matric C ist, was Sie wollen.

Angesichts der Größe (b x 750.000) und der Dichte (0,25%) von Ihrem A ist die Dichte von C 99.1%; Die durchschnittliche Länge jedes col Indizes ist 1875.

Also Ihr Problem wird die Anzahl der gemeinsamen Elemente von 2 1875-D-Vectoers für b*(b+1)/2 mal zählen.

Die Geschwindigkeit der for-Schleife scheint das einzige verbleibende Problem zu sein.