Sparse Matrix multiplication like (maxmin) in C++ using Octave libraries

Question

I'm implementing a maxmin function, it works like matrix multiplication but instead of summing products it gets max of min between two numbers pointwise. An example of naive implementation is

double mx = 0;
double mn = 0;
for (i = 0; i < rowsC;i++)
{
    for(j = 0; j < colsC;j++)
    {
        mx = 0;
        for(k = 0; k < colsA; k++)
        { 
            if (a(i, k) < b(k, j))
                mn = a(i,k);
            else
                mn = b(k,j);

            if (mn > mx)
                mx = mn;
        } 
        c(i, j) = mx;
    }
}

I'm coding it as an Octave oct-file so i have to use oct.h data structure. The problem is that i want to implement a sparse version, but usually you need a reference to the next non zero element in a row or in a column like in this example (see 4.3 algorithm): http://www.eecs.harvard.edu/~ellard/Q-97/HTML/root/node20.html

There doing row_p->next gave the next nonzero element of the row (the same for the column). Is there a way to do the same with the octave SparseMatrix class? Or is there another way of implementing the sparse matrix multiplication i can adopt for my maxmin function?

Answer 1

I don't know if anyoe would ever be interested, but i managed to find a solution. The code of the solution is part of fl-core1.0 a fuzzy logic core package for Octave and it is released under LGPL license. (The code relies on some octave functions)

// Calculate the S-Norm/T-Norm composition of sparse matrices (single thread)
void sparse_compose(octave_value_list args)
{
    // Create constant versions of the input matrices to prevent them to be filled by zeros on reading.
    // a is the const reference to the transpose of a because octave sparse matrices are column compressed
    // (to cycle on the rows, we cycle on the columns of the transpose).
    SparseMatrix atmp = args(0).sparse_matrix_value();
    const SparseMatrix a = atmp.transpose();
    const SparseMatrix b = args(1).sparse_matrix_value();

    // Declare variables for the T-Norm and S-Norm values 
    float snorm_val;    
    float tnorm_val;    

    // Initialize the result sparse matrix
    sparseC = SparseMatrix((int)colsB, (int)rowsA, (int)(colsB*rowsA));

    // Initialize the number of nonzero elements in the sparse matrix c
    int nel = 0;
    sparseC.xcidx(0) = 0;

    // Calculate the composition for each element
    for (int i = 0; i < rowsC; i++)
    {
        for(int j = 0; j < colsC; j++)
        {

            // Get the index of the first element of the i-th column of a transpose (i-th row of a)
            // and the index of the first element of the j-th column of b
            int ka = a.cidx(i);
            int kb = b.cidx(j);
            snorm_val = 0;

            // Check if the values of the matrix are really not 0 (it happens if the column of a or b hasn't any value)
            // because otherwise the cidx(i) or cidx(j) returns the first nonzero element of the previous column
            if(a(a.ridx(ka),i)!=0 && b(b.ridx(kb),j)!=0)
            {
                // Cicle on the i-th column of a transpose (i-th row of a) and j-th column of b
                // From a.cidx(i) to a.cidx(i+1)-1 there are all the nonzero elements of the column i of a transpose (i-th row of a)
                // From b.cidx(j) to b.cidx(j+1)-1 there are all the nonzero elements of the column j of b
                while ((ka <= (a.cidx(i+1)-1)) && (kb <= (b.cidx(j+1)-1)))
                {

                    // If a.ridx(ka) == b.ridx(kb) is true, then there's a nonzero value on the same row
                    // so there's a k for that a'(k, i) (equals to a(i, k)) and b(k, j) are both nonzero
                    if (a.ridx(ka) == b.ridx(kb))
                    {
                        tnorm_val = calc_tnorm(a.data(ka), b.data(kb)); 
                        snorm_val = calc_snorm(snorm_val, tnorm_val);
                        ka++;
                        kb++;
                    }

                    // If a.ridx(ka) == b.ridx(kb) ka should become the index of the next nonzero element on the i column of a 
                    // transpose (i row of a)
                    else if (a.ridx(ka) < b.ridx(kb))           
                        ka++;
                    // If a.ridx(ka) > b.ridx(kb) kb should become the index of the next nonzero element on the j column of b
                    else
                        kb++;
                }
            }

            if (snorm_val != 0)
            {
                // Equivalent to sparseC(i, j) = snorm_val;
                sparseC.xridx(nel) = j;
                sparseC.xdata(nel++) = snorm_val;
            }
        }
        sparseC.xcidx(i+1) = nel;
    }

    // Compress the result sparse matrix because it is initialized with a number of nonzero element probably greater than the real one
    sparseC.maybe_compress();

    // Transpose the result
    sparseC = sparseC.transpose();
}