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
-
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.
- The
-
AddValue Method:
- This method adds a value to the matrix. If the value is zero, it does not store anything.
-
GetMatrix Method:
- Returns the internal dictionary representation of the sparse matrix.
-
Multiply Method:
- Takes two
SparseMatrix
objects as input and returns their product as a newSparseMatrix
. - 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 ofmatA
matches the row ofmatB
, it computes the product. - The resulting value is added to the result matrix, ensuring to handle any existing value at that position correctly.
- Takes two
-
Print Method:
- Prints out the non-zero entries of the sparse matrix.
-
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.
- In the
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.