Rohit Agarwal's Notes

Sparse matrix multiplication using SQL

07 Jun 2013

a and b are two sparse matrices. We want to perform a * b as shown below:

0   1   0   0   9                1   0   0                0   0   0
0   0   3   0   0       \ /      0   0   0      -----     0  21   0
0   0   0   2   0        *       0   7   0      -----     0   0   4
0   0   0   0   0       / \      0   0   2                0   0   0
                                 0   0   0

We can represent a sparse matrix in a relational database as a table matrix_name(row_num, col_num, value). Each non-zero cell in the matrix is represnted as a record (i, j, value) in the table.

Here's how to do the multiplication. First, create the tables:

CREATE TABLE a (
row_num INT,
col_num INT,
value INT,
PRIMARY KEY(row_num, col_num)
); 

CREATE TABLE b (
row_num INT,
col_num INT,
value INT,
PRIMARY KEY(row_num, col_num)
); 

Next, insert values into the tables:

INSERT INTO a VALUES
(1, 2, 1),
(1, 5, 9),
(2, 3, 3),
(3, 4, 2);

INSERT INTO b VALUES
(1, 1, 1),
(3, 2, 7),
(4, 3, 2);

Finally, perform the multiplication using the following query:

SELECT a.row_num, b.col_num, SUM(a.value*b.value)
FROM a, b
WHERE a.col_num = b.row_num
GROUP BY a.row_num, b.col_num;

2|2|21
3|3|4

To see how this query works, remember the formula for cell (i,j) of the product. It is the sum of a(i,k)*b(k,j) for all k. The JOIN condition a.col_num = b.row_num makes sure that both a.value and b.value has the same k. The GROUP BY clause makes sure that we sum over all k's.

comments powered by Disqus