# 50049. Matrix Multiplication

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

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

1void 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                   *ptrA                  *ptrA             |                          |                         |             |                          |                         |             v                          v                         v             +---+---+---+              +---+---+---+             +---+---+---+A_elements| 5 | 5 | 5 |   A_rowind| 0 | 1 | 2 |  A_colind| 2 | 1 | 0 |             +---+---+---+              +---+---+---+             +---+---+---+                    \                         |                         /                                           matrix A                                        +---+---+---+                                        | 0 | 0 | 5 |                                        +---+---+---+                                        | 0 | 5 | 0 |                                        +---+---+---+                                        | 5 | 0 | 0 |                                        +---+---+---+          *ptrB                   *ptrB                  *ptrB             |                          |                         |             |                          |                         |             v                          v                         v             +---+---+---+              +---+---+---+             +---+---+---+B_elements| 1 | 2 | 3 |   B_rowind| 1 | 1 | 2 |  B_colind| 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:

12345678910111213141516171819202122232425262728293031323334353637#include <stdio.h>#include <stdlib.h>#include <assert.h>#include "matrix_multiplication.h"#define MAX 1000static 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;     int *ptrB;    ptrA = A_elements, ptrA = A_rowind, ptrA = A_colind;    ptrB = B_elements, ptrB = B_rowind, ptrB = 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:

1void 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 21 0 1


## Sample Output

0 15 010 5 00 0 0


## Compile

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


## Extra

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