Extensions for CVS, CRS and CCS

The CVSExtensions, CRSExtensions and CCSExtensions serve as my placeholders for compressed matrix operations. This article focuses on matrix-vector multiplication.

There are many online sources that teach how matrix-vector multiplication is done.

• https://www.varsitytutors.com/hotmath/hotmath_help/topics/multiplying-vector-by-a-matrix.html
• http://mathinsight.org/matrix_vector_multiplication

And there are even websites that show you how to do it programmatically.

• http://www.mathcs.emory.edu/~cheung/Courses/561/Syllabus/3-C/sparse.html
• http://matrix.reshish.com/multiplication.php

All of these gave me enough inspiration and motivation to create the MatrixVectorProduct() methods for CVS, CRS and CCS.

CVSExtensions

In some ways, CVS is almost coordinate-wise. Besides the outer loop on the distinct values, observe that the inner loop pretty much resembles the IDOKSparseMatrixExtensions.MatrixVectorProduct()'s loop on the DOK.

CVSExtensions.cs
using System.Collections.Generic;

namespace Mendz.Library.Matrices
{
    public static class CVSExtensions
    {
        public static IList<P> MatrixVectorProduct<T, V, P>(
            this CVS<T> cvs, IList<V> vector)
        {
            (List<T> value, 
             List<List<int>> linearIndex, 
             MatrixLinearIndexMode linearIndexMode, 
             (int rows, int columns) size) = cvs;
            int rows = size.rows;
            P[] product = new P[rows];
            for (int i = 0; i < value.Count; i++)
            {
                dynamic entry = value[i];
                foreach (var li in linearIndex[i])
                {
                    (int row, int column) = 
                        MatrixCoordinates.ToCoordinates(size, li, linearIndexMode);
                    product[row] += entry * vector[column];
                }
            }
            return product;
        }
    }
}

With CVS, it is very important that the MatrixLinearIndexMode used by the "compression" is also used when "decompressing" the linear indexes (MatrixCoordinates.ToCoordinates(size, li, linearIndexMode)). This makes sure that the resulting coordinates would match the original. This feature in MatrixVectorProduct() allows it to support CVS in either row-major order or in column-major order.

In matrix-vector multiplication, the product's length is determined by the number of rows in the matrix. The number of rows cannot be derived from value or linearIndex. This is the reason why size is the fourth value in the CVS tuple.

Observe that the actual operation (product[row] += entry * vector[column];) is dynamic via this line: dynamic entry = value[i];. This solves the generics operator problem, a .Net limitation where generics constraints for "primitive" types or operators are not supported (wishing for "where T : operator(* / + - %)" or something like "where T : int, long, double, decimal, float, ...").

CRSExtensions

Matrix-vector multiplication with CRS is pretty well studied. CRSExtensions' implementation uses the classic 2 loops solution.

CRSExtensions.cs
using System.Collections.Generic;

namespace Mendz.Library.Matrices
{
    public static class CRSExtensions
    {
        public static IList<P> MatrixVectorProduct<T, V, P>(
            this CRS<T> crs, IList<V> vector)
        {
            (List<T> value, 
             List<int> rowPointer, 
             List<int> columnIndex, 
             (int rows, int columns) size) = crs;
            int rows = size.rows;
            P[] product = new P[rows];
            for (int j = 0; j < rows; j++)
            {
                for (int i = rowPointer[j]; i < rowPointer[j + 1]; i++)
                {
                    product[j] += value[i] * (dynamic)vector[columnIndex[i]];
                }
            }
            return product;
        }
    }
}

In matrix-vector multiplication, the product's length is determined by the number of rows in the matrix. The number of rows cannot be derived from value, rowPointer or columnIndex (or perhaps you can via rowPointer.Count - 1). This is the reason why size is the fourth value in the CRS tuple.

Observe that the actual operation (product[j] += value[i] * (dynamic)vector[columnIndex[i]];) is dynamic. This solves the generics operator problem, a .Net limitation where generics constraints for "primitive" types or operators are not supported.

CCSExtensions

Matrix-vector multiplication with CCS is pretty well studied. CCSExtensions' implementation uses the classic 2 loops solution.

CCSExtensions.cs
using System.Collections.Generic;
using System.Linq;

namespace Mendz.Library.Matrices
{
    public static class CCSExtensions
    {
        public static IList<P> MatrixVectorProduct<T, V, P>(
            this CCS<T> ccs, IList<V> vector)
        {
            (List<T> value, 
             List<int> columnPointer, 
             List<int> rowIndex, 
             (int rows, int columns) size) = ccs;
            P[] product = new P[size.rows];
            for (int j = 0; j < size.columns; j++)
            {
                dynamic v = vector[j];
                for (int i = columnPointer[j]; i < columnPointer[j + 1]; i++)
                {
                    product[rowIndex[i]] += value[i] * v;
                }
            }
            return product;
        }
    }
}

In matrix-vector multiplication, the product's length is determined by the number of rows in the matrix. The number of rows cannot be derived from value, columnPointer or rowIndex. This is the reason why size is the fourth value in the CCS tuple.

Observe that the actual operation (product[row] += value[i] * v;) is dynamic via this line: dynamic v = vector[j];. This solves the generics operator problem, a .Net limitation where generics constraints for "primitive" types or operators are not supported.