CSR Matrix - Matrix mnożenie

Question

Mam dwie macierze kwadratowe A i B

muszę konwertować B do CSR Format i określić produktowi C

A * B_csr = C 

Znalazłem wiele informacji w Internecie dotyczących CSR Matrix - Vector multiplication. Algorytm to:

for (k = 0; k < N; k = k + 1) 
    result[i] = 0; 

for (i = 0; i < N; i = i + 1) 
{ 
    for (k = RowPtr[i]; k < RowPtr[i+1]; k = k + 1) 
    { 
    result[i] = result[i] + Val[k]*d[Col[k]]; 
    } 
} 

Wymagam jednak mnożenia Matrix - Matrix.

Co więcej, wydaje się, że większość algorytmów stosuje mnożenie A_csr - vector tam, gdzie potrzebuję A * B_csr. Moim rozwiązaniem jest przetransponowanie dwóch macierzy przed konwersją, a następnie przeniesienie produktu końcowego.

Czy ktoś może wyjaśnić, jak obliczyć produkt Matrix - CSR Matrix i/lub produkt CSR Matrix - Matrix?

Answer 1

Oto proste rozwiązanie w Pythonie dla Dense Matrix X CSR Matrix. Powinno to być oczywiste.

def main(): 
    # 4 x 4 csr matrix 
    # [1, 0, 0, 0], 
    # [2, 0, 3, 0], 
    # [0, 0, 0, 0], 
    # [0, 4, 0, 0], 
    csr_values = [1, 2, 3, 4] 
    col_idx = [0, 0, 2, 1] 
    row_ptr = [0, 1, 3, 3, 4] 
    csr_matrix = [ 
     csr_values, 
     col_idx, 
     row_ptr 
     ] 

    dense_matrix = [ 
     [1, 3, 3, 4], 
     [1, 2, 3, 4], 
     [1, 4, 3, 4], 
     [1, 2, 3, 5], 
     ] 

    res = [ 
     [0, 0, 0, 0], 
     [0, 0, 0, 0], 
     [0, 0, 0, 0], 
     [0, 0, 0, 0], 
     ] 

    # matrix order, assumes both matrices are square 
    n = len(dense_matrix) 

    # res = dense X csr 
    csr_row = 0 # Current row in CSR matrix 
    for i in range(n): 
    start, end = row_ptr[i], row_ptr[i + 1] 
    for j in range(start, end): 
     col, csr_value = col_idx[j], csr_values[j] 
     for k in range(n): 
     dense_value = dense_matrix[k][csr_row] 
     res[k][col] += csr_value * dense_value 
    csr_row += 1 

    print res 


if __name__ == '__main__': 
    main() 

CSR Matrix X Dense Matrix jest tak naprawdę ciągiem CSR Matrix X Vector produktu dla każdego wiersza macierzy gęstej prawo? W związku z tym rozszerzenie powyższego kodu powinno być naprawdę łatwe.

Idąc dalej, sugeruję, aby samemu nie kodować tych procedur. Jeśli używasz C++ (na podstawie tagu), możesz na przykład spojrzeć na Boost ublas lub Eigen. Interfejsy API mogą początkowo wydawać się nieco zagadkowe, ale naprawdę warto na dłuższą metę. Po pierwsze, uzyskasz dostęp do znacznie większej funkcjonalności, której prawdopodobnie będziesz potrzebować w przyszłości. Po drugie te wdrożenia będą lepiej zoptymalizowane.