2d Matrix als 1-d matrix Formatieren und multipliziert

Question

Bei der Verarbeitung von n×n-Matrizen, bei denen viele Eintrage gleich 0 sind, ist es für große n sinnvoll, statt eines 2-dimensionalen Arrays mit Einträgen vom Typ double drei eindimensionale Arrays zu verwenden. Genauer verwendet man für eine quadratische Matrix mit m Einträgen, die ungleich 0 sind,

• ein Array I vom Typ int fur die Zeilennummern der Eintr age ungleich 0,
• ein Array J vom Typ int fur die Spaltennummern der Eintrage ungleich 0 und
• ein Array W vom Typ double fur die Eintrage ungleich 0.

Für die Matrix

M =

2.5 0.0 1.3
0.0 0.0 2.7
1.2 0.0 0.0

mit m = 4 würde man zum Beispiel die folgenden drei eindimensionalen Arrays erhalten:

• I = [1, 1, 2, 3]
• J = [1, 3, 3, 1]
• W = [2.5, 1.3, 2.7, 1.2]

Schreiben Sie ein Programm, welches eine Funktion/Methode implementiert, welche zwei n × n-Matrizen, die jeweils als drei ein dimensionale Arrays vorliegen, miteinander multipliziert. Das Produkt derbeiden Matrizen soll wieder direkt in drei ein dimensionalen Arrays abgelegt werden.

Ansatz/Problem:

Mein Code:

for(i=0;i<n;i++)
  {
      for(j=0;j<n;j++)
      {
        if(a[i][j]!=0)
                      {
              I1[k]=i;
              J1[k]=j;
              W1[k]=a[i][j];
              k++;
          }

      }
  }

for(i=0;i<n;i++)
  {
      for(j=0;j<n;j++)
      {
        if(b[i][j]!=0)
          {
              I2[m]=i;
              J2[m]=j;
              W2[m]=b[i][j];
              m++;
          }

  }
  }

      l=n*n;
  int p = 1;
  auto start = high_resolution_clock::now();
      printf("\noutput of c \nThe values of C are \n");
      ;
      for (int f = 0; f<l ; f++)
      {
          W3[f]=0;
      }

      for (int f =0; f<k ; f++)
      {
          for (int g=0; g<m; g++)
          {
              if (J1[f] == I2[g])
              {
                  int z=0;
                  for(int a = 0 ; a<p ; a++)
                  {
                      if((I1[f]==I3[a])&& (J2[g]== J3[a]))
                      {
                          W3[a]+=W1[f] * W2[g];
                          z++;
                      }
                  }
                  if(z == 0)
                  {
                      I3[p]=I1[f] ;
                      J3[p]=J2[g] ;
                      W3[p]=W1[f]*W2[g];
                      p++;
                  }
              }
          }
      }

erst diese program geht nur für 100 n zahl. Über 100 diese Programm rennt nicht.

Kann ich ein Programm mit einer anderen Methoden erzeugen?

Answer 1

Antwort mit KI erzeugt

Matrixmultiplikation von zwei n × n-Matrizen in speicher-effizientem Format

Wenn es um die Multiplikation von großen, dünn besetzten (sparse) Matrizen geht, ist die Speicherung in drei eindimensionalen Arrays (\(I\), \(J\) und \(W\)) tatsächlich eine effiziente Methode. Der vorgeschlagene Codeansatz zeigt einen Versuch, zwei solcher Matrizen zu multiplizieren, stößt jedoch auf Leistungsgrenzen bei größeren Matrizen. Hier ist ein strukturierter und optimierter Ansatz zur Bearbeitung dieser Aufgabe.

Um zwei Matrizen \(A\) und \(B\) zu multiplizieren, um Matrix \(C\) zu erhalten, wobei \(A\), \(B\) und \(C\) in den Arrays \(I\), \(J\) und \(W\) für ihre nicht-Null-Werte gespeichert sind, können wir folgende Schritte durchführen:

1. Initialisiere die Ausgabe-Arrays \(I3\), \(J3\) und \(W3\) ohne vorgegebene Größe, die während der Berechnung wachsen werden.

2. Gehe jedes Element von \(A\) durch, repräsentiert durch die Kombination der Arrays \(I1\), \(J1\), \(W1\).

3. Für jedes Element in \(A\), suche die entsprechenden Elemente in \(B\) (repräsentiert durch \(I2\), \(J2\), \(W2\)), die bei der Multiplikation zur Summe des Ergebnisses beitragen könnten.

4. Aktualisiere oder füge den Wert in \(W3\) hinzu, während du auch die korrekten Indizes in \(I3\) und \(J3\) speicherst.

Python-Beispielcode

Der folgende Python-Code implementiert die oben genannten Schritte:

python
def sparse_matrix_multiplication(I1, J1, W1, I2, J2, W2, n):
    i3, j3, w3 = [], [], []
    product_dict = {}

    for index_a in range(len(I1)):
        for index_b in range(len(I2)):
            if J1[index_a] == I2[index_b]: 
                result_pos = (I1[index_a], J2[index_b])
                product = W1[index_a] * W2[index_b]

                if result_pos in product_dict:
                    product_dict[result_pos] += product
                else:
                    product_dict[result_pos] = product

    # Konvertiere das Wörterbuch zurück in die drei Listen
    for pos, value in product_dict.items():
        i3.append(pos[0])
        j3.append(pos[1])
        w3.append(value)

    return i3, j3, w3

# Beispieldaten
I1, J1, W1 = [1, 1, 2, 3], [1, 3, 3, 1], [2.5, 1.3, 2.7, 1.2]
I2, J2, W2 = [1, 1, 2, 3], [1, 3, 3, 1], [2.5, 1.3, 2.7, 1.2]
n = 3

I3, J3, W3 = sparse_matrix_multiplication(I1, J1, W1, I2, J2, W2, n)

print("I3:", I3)
print("J3:", J3)
print("W3:", W3)

Diese Implementierung nutzt Python-Dictionaries, um die Notwendigkeit der Suche im Ergebnis (\(I3\), \(J3\)) zu reduzieren und Kollisionen (gleiche Positionszuweisungen) effizienter zu behandeln, was den Code auch für große \(n\) gut skalieren lässt.