50049. Matrix Multiplication

I'm a slow walker, but I never walk backwards.

Task Description

Write a function matrix_multiplication to multiply two $S$ by $S$ sparse matrices.

We represent a sparse matrix with three vectors. The first vector has the non-zero elements of the matrix. The second and the third vectors represent the row and column indices of the corresponding non-zero elements. Both the row and column indices are between $0$ and $S - 1$.

For example, $N$ non-zero elements are in the first vector $\textit{A_elements}\lbrack N]$, the row indices are in the second vector $\textit{A_rowind}\lbrack N]$, and the column indices are in the third vector $\textit{A_colind}\lbrack N]$. Similarly we define three vectors for matrix $B$, where $M$ is the number of non-zero elements in $B$.

The prototype of matrix_multiplication is as follows

1
void matrix_multiplication(int N, int** ptrA, int M, int** ptrB, int S, int *result);

ptrA points to an array holding three pointers, which point to array $\textit{A_elements}$, array $\textit{A_rowind}$ and $\textit{A_colind}$. Similarly, ptrB points to an array holding three pointers, which point to array $\textit{B_elements}$, array $\textit{B_rowind}$ and array $\textit{B_colind}$.

You should multiply matrix A and matrix B, and put the answer into the result array in a row by row, column by column manner.

For example
 
N = 3, M = 3, S = 3
 
 
         *ptrA[0]                   *ptrA[1]                  *ptrA[2]
             |                          |                         |
             |                          |                         |
             v                          v                         v
             +---+---+---+              +---+---+---+             +---+---+---+
A_elements[3]| 5 | 5 | 5 |   A_rowind[3]| 0 | 1 | 2 |  A_colind[3]| 2 | 1 | 0 |
             +---+---+---+              +---+---+---+             +---+---+---+
                    \                         |                         /
                                           matrix A
                                        +---+---+---+
                                        | 0 | 0 | 5 |
                                        +---+---+---+
                                        | 0 | 5 | 0 |
                                        +---+---+---+
                                        | 5 | 0 | 0 |
                                        +---+---+---+
 
         *ptrB[0]                   *ptrB[1]                  *ptrB[2]
             |                          |                         |
             |                          |                         |
             v                          v                         v
             +---+---+---+              +---+---+---+             +---+---+---+
B_elements[3]| 1 | 2 | 3 |   B_rowind[3]| 1 | 1 | 2 |  B_colind[3]| 1 | 0 | 1 |
             +---+---+---+              +---+---+---+             +---+---+---+
                    \                         |                         /
                                           matrix B
                                        +---+---+---+
                                        | 0 | 0 | 0 |
                                        +---+---+---+
                                        | 2 | 1 | 0 |
                                        +---+---+---+
                                        | 0 | 3 | 0 |
                                        +---+---+---+  
 
             +---+----+---+----+---+---+---+---+---+
result[3 * 3]| 0 | 15 | 0 | 10 | 5 | 0 | 0 | 0 | 0 |
             +---+----+---+----+---+---+---+---+---+

The main.c program is as follow:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "matrix_multiplication.h"
#define MAX 1000
static int A_elements[MAX], A_rowind[MAX], A_colind[MAX];
static int B_elements[MAX], B_rowind[MAX], B_colind[MAX];
int main(int argc, char const *argv[])
{   
    int N, M, S;
    assert(scanf("%d %d %d", &N, &M, &S) == 3);
 
    int *ptrA[3];
    int *ptrB[3];
    ptrA[0] = A_elements, ptrA[1] = A_rowind, ptrA[2] = A_colind;
    ptrB[0] = B_elements, ptrB[1] = B_rowind, ptrB[2] = B_colind;
 
    for(int i = 0; i < N; ++i)
        assert(scanf("%d", &A_elements[i]) == 1);
    for(int i = 0; i < N; ++i)
        assert(scanf("%d", &A_rowind[i]) == 1);   
    for(int i = 0; i < N; ++i)
        assert(scanf("%d", &A_colind[i]) == 1);           
    for(int i = 0; i < M; ++i)
        assert(scanf("%d", &B_elements[i]) == 1);
    for(int i = 0; i < M; ++i)
        assert(scanf("%d", &B_rowind[i]) == 1);   
    for(int i = 0; i < M; ++i)
        assert(scanf("%d", &B_colind[i]) == 1);
 
    int *result = malloc(S*S*sizeof(int));
    matrix_multiplication(N, ptrA, M, ptrB, S, result);
    for (int i = 0; i < S; ++i)
        for (int j = 0; j < S; ++j)
              printf("%d%c", result[i * S + j], " \n"[j == S - 1]);
    return 0;
}

The header file matrix_multiplication.h is as follows:

1
void matrix_multiplication(int N, int** ptrA, int M, int** ptrB, int S, int *result);

Input Format

The first line of input contains three integers $N$, $M$, $S$($0 \lt N, M \leq 1000, 0 \lt S \leq 1000$), and the following six lines are $\textit{A_elements}\lbrack N], \textit{A_rowind}\lbrack N], \textit{A_colind}\lbrack N]$ with $N$ integers and $\textit{B_elements}\lbrack M], \textit{B_rowind}\lbrack M], \textit{B_colind}\lbrack M]$ with $M$ integers.

Output Format

Print the $S$ by $S$ matrix.

Sample Input

3 3 3
5 5 5
0 1 2
2 1 0
1 2 3
1 1 2
1 0 1

Sample Output

0 15 0
10 5 0
0 0 0

Compile

gcc -std=c99 -O2 -c main.c -lm
gcc -std=c99 -O2 -c matrix_multiplication.c -lm
gcc -std=c99 -O2 matrix_multiplication.o main.o -lm

Extra

Morris 第 11 組測資 $N = 30000, \; M = 30000, \; S = 1000$

Discussion