Sparse Matrix mit Sparse Vector multiplikation.



  • Hallo,
    ich bräuchte eine möglichst schnelle Methode um eine Sparse Matrix (ca 3% der Einträge besetzt) mit einem Sparse Vector (ca 1% besetzt) zu Multiplizieren. Die Matrix ist ca. 40.000 x 25.000.

    Meine jetzige einfache SparseMatrix - Vektor multiplikation sieht so aus:

    • Aufbau der Sparse Matrix: speichere zu jedem Wert die Position an der er in der Matrix steht. (Zeilenweise hintereinander)
    • Bei der Multiplikation: durchlaufe alle Elemente in einer Zeile der Matrix und multipliziere sie mit den entsprechenden Elementen des Vektors (ein "stl-vektor").

    Leider wird dabei nicht ausgenutzt, dass der Vektor auch sparse ist.

    Hat jemand einen Tipp wie ich das schneller bekomme?
    Oder gute Links zum Thema "Dünn Besetzten" Multiplikation?
    Und wie mache ich eine Cache-Optimierung?

    danke,
    Stefan



  • ich wuerde die besetzen vektorelemente durchlaufen und pro solchem die besetzen elemente der entsprechenden matrixspalte.



  • So ähnlich dachte ich mir das auch.

    In dem Vektor kann ich dann mit einem Zeiger über die Besetzten Elemente laufen. Das problem ist, wie findet man effizient das entsprechende Element aus der Matrix?

    Mir fällt momentan nichts besseres ein als in der Matrix soweit nachvorne zu laufen bis das zum Vektor passende Element gefunden ist, siehe PseudoCode:

    //Anordnung von Matrix & Vektor:
    m m m            x
    m m m     v      x
    m m m  *  v   =  x
    m m m     v      x
    m m m            x
    
    for (alle MatrixZeilen ) {
      VektorIterator = anfang;
      MatrixIterator = anfang;
    
      //Durchlaufe alle besetzten Elemente im Vector:
      for ( VektorIterator ++ ) {
    
        while ( MatrixSpalte < VektorZeile )
          MatrixIterator ++;
        if ( MatrixSpalte == VektorZeile )
          //gefunden!! Multipliziere Elemente
      }
    
    }
    

    Diese While schleife ist halt tödlich. Damit ist meine alte Methode (siehe erstes post) die den vollen Vektor einfach direkt über das Element[] anspricht wahrscheinlich schneller.

    Ich weis dass es geht die "Schwachbesetztheit" von beiden zur Beschleunigung zu benutzen.
    Aber leider finde ich keine Information wie das gehen könnte. 🙄



  • du musst die teile halt entsprechend organisieren. du musst pro matrixspalte einen vektor aus paaren (zeile, wert) haben.
    dann

    sparsevektor v
    sparsematrix m
    for(vektoriterator vi = v.begin; vi!=v.end; ++vi){
      for(spalteniterator si = matrix.spalte(vi.first).begin; si!=end; ++si){
        ergebnismap[si.first]+=si.second*vi.second
      }
    }
    

    danach sollte ergebnismap das ergebnis als sparsevektor enthalten.



  • That's it!! 😃

    wie konnt ich das bloß übersehen!! War wohl zu sehr auf "Zeile mal Spalte" fixiert.;)

    Werde das die Tage mal umsetzen und eventuell mal berichten wie schnell es läuft. 🙂


Log in to reply