Sparse matrix multiplication problem in c#

General
1

Sparse matrix multiplication is an operation that involves multiplying two matrices that contain a significant number of zero elements. The key to efficiently handling sparse matrices is to only operate on the non-zero elements, which can save both time and space.

Sparse Matrix Representation

We’ll represent the sparse matrix using a list of tuples or a dictionary, where each entry contains the row index, column index, and the value. This way, we only store the non-zero elements.

C# Implementation

Here’s a simple C# implementation to multiply two sparse matrices:

using System;
using System.Collections.Generic;

public class SparseMatrix
{
    // A dictionary to store non-zero elements
    private Dictionary<(int, int), int> matrix;

    public SparseMatrix()
    {
        matrix = new Dictionary<(int, int), int>();
    }

    public void AddValue(int row, int col, int value)
    {
        if (value != 0)
        {
            matrix[(row, col)] = value;
        }
    }

    public Dictionary<(int, int), int> GetMatrix()
    {
        return matrix;
    }

    public static SparseMatrix Multiply(SparseMatrix matA, SparseMatrix matB)
    {
        SparseMatrix result = new SparseMatrix();
        var matrixA = matA.GetMatrix();
        var matrixB = matB.GetMatrix();

        foreach (var a in matrixA)
        {
            int rowA = a.Key.Item1;
            int colA = a.Key.Item2;
            int valueA = a.Value;

            foreach (var b in matrixB)
            {
                int rowB = b.Key.Item1;
                int colB = b.Key.Item2;
                int valueB = b.Value;

                if (colA == rowB) // valid multiplication condition
                {
                    int newRow = rowA;
                    int newCol = colB;
                    int newValue = valueA * valueB;

                    // Add the product to the result matrix
                    result.AddValue(newRow, newCol, 
                        result.GetMatrix().GetValueOrDefault((newRow, newCol), 0) + newValue);
                }
            }
        }

        return result;
    }

    public void Print()
    {
        foreach (var entry in matrix)
        {
            Console.WriteLine($"({entry.Key.Item1}, {entry.Key.Item2}) = {entry.Value}");
        }
    }
}

public class Program
{
    public static void Main(string[] args)
    {
        SparseMatrix matA = new SparseMatrix();
        SparseMatrix matB = new SparseMatrix();

        // Matrix A
        matA.AddValue(0, 0, 1);
        matA.AddValue(0, 2, 2);
        matA.AddValue(1, 1, 3);

        // Matrix B
        matB.AddValue(0, 1, 4);
        matB.AddValue(2, 0, 5);
        matB.AddValue(1, 2, 6);

        SparseMatrix result = SparseMatrix.Multiply(matA, matB);
        
        Console.WriteLine("Resulting Sparse Matrix:");
        result.Print();
    }
}

Explanation

  1. SparseMatrix Class:

    • The SparseMatrix class holds a dictionary where the keys are tuples representing (row, column) pairs and the values are the non-zero elements of the matrix.

  2. AddValue Method:

    • This method adds a value to the matrix. If the value is zero, it does not store anything.

  3. GetMatrix Method:

    • Returns the internal dictionary representation of the sparse matrix.

  4. Multiply Method:

    • Takes two SparseMatrix objects as input and returns their product as a new SparseMatrix.
    • For each non-zero element in the first matrix (matA), it checks for compatible non-zero elements in the second matrix (matB). If the column of matA matches the row of matB, it computes the product.
    • The resulting value is added to the result matrix, ensuring to handle any existing value at that position correctly.

  5. Print Method:

    • Prints out the non-zero entries of the sparse matrix.

  6. Program Class:

    • In the Main method, we create two sparse matrices, populate them with some values, and then multiply them. Finally, it prints the resulting sparse matrix.

Usage

  • You can modify the matrices in the Main method to test different configurations. This implementation efficiently handles the multiplication of sparse matrices by focusing only on non-zero elements.