The spgemm operator computes the matrix product of two sparse matrices and produces a sparse matrix as the result.  It also includes options to use specialized arithmetic that permits matrix multiplication to be used to solve shortest-path network problems and other minimization or maximization problems.

spgemm(A, B [, 'min.+' | 'max.+'] [, right_replicate: true|false]);

The spgemm operator resides in the Linear Algebra library. Run the following query to load this library:

The spgemm operator calculates the matrix product

 and returns the result as a sparse matrix 

LaTeX Math Inline

.

• Here, a sparse matrix is an array of two dimensions where empty cells are treated as implied zeros. 

• The algorithm is optimized for input arrays where such implicit zeros predominate.

• The product does not contain actual zero values: any zeros generated become empty cells in the output.

• LaTeX Math Inline

   and

  LaTeX Math Inline

   must have a single attribute with the same type, which may be float or double.

• The dimension start, end, and chunk interval of the columns of A must equal those of the rows of B.

• LaTeX Math Inline

   and 

  LaTeX Math Inline

   may not be nullable.

If B has replicated distribution, spgemm can be faster (so long as right_replicate: is not false)

If B has col_cyclic distribution, spgemm can be slightly faster (so long as right_replicate: is not true)

Matrices with nullable attributes cannot be multiplied.  Use cast to change the nullability of attributes.

 To multiply a sparse 2×3 matrix and a sparse 3×2 matrix, do the following:

1. Create a 2×3 non-nullable sparse array:

   AFL% store(build(<val:double NOT NULL>[row=0:1; col=0:2],'[[(),1, 2],[(),4,()]]',true),A);

   
   The output is:

   {0,1} 1 {0,2} 2 {1,1} 4

2. Create a 3×2 non-nullable sparse array (including an explicit zero to demonstrate it is tolerated):

   AFL% store(build(<val:double NOT NULL>[row=0:2; col=0:1],'[[(),10],[(),0],[(),50]]',true),B);  

   
   The output is:

   {row,col} val {0,1} 10 {1,1} 0 {2,1} 50

3. Multiply 

    and 
   .
   AFL% spgemm(A, B) 

   
   The output is:

   {row,col} multiply {0,1} 100

   Notice that there are no explicit zeros in the output.

Spgemm has an optional third parameter which can be used to find solutions to combinatorial minimization (or maximization) problems such as shortest-path problems.  Transforming such problems into sparse-matrix form allows them to be solved in parallel on computer clusters.  For more on transforming shortest-path problems in to sparse matrix problems, the following references are recommended: 

Setting the third parameter to 'min.+' changes the matrix product from being computed with the usual '+,*' definitions, and substitutes an arithmetic where '+' is replaced by 'min' and '*' is replaced with '+'.   This 'min.+' arithmetic is also known as the tropical semiring in modern algebra.  The product C is then defined as:

The additive identity or "zero" in this system of arithmetic is 

.  Empty cells are treated as implied 

, and 

 is replaced by empty cells in the output.

The third parameter can also be 'max,+' (also known as the arctic semiring).  The product C is then defined as:

The additive identity or "zero" in this system of arithmetic is 

.  Empty cells are treated as implied 

, and 

 is replaced by empty cells in the output.

SciDB provides an example implementation of the Bellman-Ford Single-Source Shortest Path algorithm using the spgemm operator.  See /opt/scidb/<version>/bin/bellman_ford_example.sh

 Compute the Shortest Path from Vertex 0 in a Graph using bellman_ford_example.sh.  

1. Consider a directed graph with the following edges and associated weights: 

   1. 0→1 : 1

   2. 0→2 : 2

   3. 1→3 : 3

   4. 2→3 : 1

2. Store the graph as a (sparse) adjacency matrix, with dimensions v0 and v1, with the weights stored as attribute 'w' (these names are expected by the script) :

   bash$ iquery -aq "store(build(<w:float NOT NULL>[v0=0:3; v1=0:3],'[[(),1, 2,()],[(),(),(),3],[(),(),(),1],[]]',true),A);"

   
   The output is:

   {v0,v1} w {0,1} 1 {0,2} 2 {1,3} 3 {2,3} 1

3. Make sure the vector you're using as the result, MYRESULT, does not exist:

    bash$ iquery -aq "remove(MYRESULT)"

   
   The output is:

   ... Error description: Query processor error. Array 'public.MYRESULT' does not exist. ...

4. Run the script, specifying the matrix name A, the result vector MYRESULT, and the starting vertex 0, as the inputs:

    bash$ /opt/scidb/15.12/bin/bellman_ford_example.sh A MYRESULT 0

   
   The output is:

   Query was executed successfully NUM_V0_USED is 3 Query was executed successfully ... Query was executed successfully

5. Print MYRESULT:

   iquery -aq"scan(MYRESULT)" 

   
   The output is:

   {v1,dummy} multiply {0,0} 0 {1,0} 1 {2,0} 2 {3,0} 3

   Note that there were two paths from vertex 0 to vertex 3: the one through vertex 1 has length 4, while the one through vertex 2 has length 3, and the shorter one is listed.