MySQL matrix multiplication

11
votes

I am trying to write matrix multiplication for MySQL and am kinda stuck:

basically, my matrices are stored in format
[row#, column#, matrixID, value], so for example matrix [3 x 2] would be something like:

[row#, column#, matrixID, value]
  1      1        mat01    1
  1      2        mat01    2
  1      3        mat01    3
  2      1        mat01    4
  2      2        mat01    5
  2      3        mat01    6

being equivalent to: [[1 2 3],[4 5 6]]

following does calculation of single element of matrix1 * matrix2 quite well: 

   SELECT SUM(row1.`val` * col2.`val`)
   FROM matValues row1
   INNER JOIN  `matValues` col2
   WHERE row1.`row` = 1 AND row1.`mID`='matrix1' AND 
         col2.`mID`='matrix2' AND col2.`col` = 1 AND row1.col = col2.row

wrapping this into function and then using another function to iterate over row and column numbers might work, but I have problems with generating this set of numbers and iterating over them using SQL. Any advice / suggestions are welcome

3
mysqlsqlmathmatrixlinear-algebra
Is your question really 'How to generate a sequence of numbers in MySQL'? - raina77ow
MySQL is a database management system, not a linear algebra engine. You should be reading the contents into a more appropriate tool (like a Java or C++ application) performing the matrix manipulation there, and, if necessary, posting the results back to the database. - andand
ofc, simplest solution is using Java or C++ (or anything else), however I am dealing with very large matrices (basically large enough that fitting them into memory is out of question) and it makes matrix manipulation in reasonable speed quite complicated as it requires keeping only chunks in memory and IO overhead for very large number of reads and writes required to process matrix. As for generating sequence of numbers of MySQL, it is certainly one solution and I am unaware how to do it, better solution would be to feed pair of SELECTed rows into SQL function and return table as result. - Azolin

3 Answers

19
votes

Try:

select m1.`row#`, m2.`column#`, sum(m1.value*m2.value) 
from matValues m1
join matValues m2 on m2.`row#` = m1.`column#` 
where m1.matrixID = 'mat01' and m2.matrixID = 'mat02'
group by m1.`row#`, m2.`column#`

Example here.

(Replace 'mat01' and 'mat02' with suitable matrixID values.)

1
votes

You can do the entire calculation in SQL. You only give an example with a single matrix, which because it is not square, cannot be multiplied by itself.

Here is the idea:

SELECT mout.row, mout.col, SUM(m1.value*m2.value)
FROM (select distinct row from matValues cross join
      select distinct COL from matValues
     ) mout left outer join
     matValues m1
     on m1.row = mout.row left outer join
     matValues m2
     on m2.col = mout.col and
        m2.row = m1.col
0
votes

I know this is SQL-Server syntax, but it should give you a start on the corresponding MySql syntax. The sparse matrix nature seems to handle well.

   with I as (
      select * from ( values
        (1,1, 1),
        (2,2, 1), 
        (3,3, 1)
      ) data(row,col,value)
    )
    ,z_90 as (
      select * from ( values
        (1,2, 1),
        (2,1,-1), 
        (3,3, 1)
      ) data(row,col,value)
    )
    ,xy as (
      select * from ( values
        (1,2, 1),
        (2,1, 1), 
        (3,3, 1)
      ) data(row,col,value)
    )
    ,x_90 as (
      select * from ( values
        (1,1, 1),
        (2,3, 1), 
        (3,2,-1)
      ) data(row,col,value)
    )
    select
       'I * z_90' as instance,
       a.row,
       b.col,
       sum( case when a.value is null then 0 else a.value end
          * case when b.value is null then 0 else b.value end ) as value
    from I as a
    join z_90 as b on a.col = b.row
    group by a.row, b.col
    union all
    select
       'z_90 * xy' as instance,
       a.row,
       b.col,
       sum( case when a.value is null then 0 else a.value end
          * case when b.value is null then 0 else b.value end ) as value
    from z_90 as a
    join xy as b on a.col = b.row
    group by a.row, b.col
    union all
    select
       'z_90 * x_90' as instance,
       a.row,
       b.col,
       sum( case when a.value is null then 0 else a.value end
          * case when b.value is null then 0 else b.value end ) as value
    from z_90 as a
    join x_90 as b on a.col = b.row
    group by a.row, b.col

    order by instance, a.row, b.col

yields:

instance    row         col         value
----------- ----------- ----------- -----------
I * z_90    1           2           1
I * z_90    2           1           -1
I * z_90    3           3           1
z_90 * x_90 1           3           1
z_90 * x_90 2           1           -1
z_90 * x_90 3           2           -1
z_90 * xy   1           1           1
z_90 * xy   2           2           -1
z_90 * xy   3           3           1

However, I suggest you also check out performing this on your graphics card. NVIDIA has a good example of implementing matrix multiplication in theri C Programming Guide.