## Big Sparse Matrix Implementation

In my last blog post I described the design of a big sparse matrix of int. Here’s some of the key implementation. The definition starts with:

class BigArrayOfArraysOfInts
{
private int levelOneArrayLength;
. . .

The master array can be visualized in several ways. See the image below for how I conceptualize master. The image is the result of the following code:

BigArrayOfArraysOfInt theMatrix =
new BigArrayOfArraysOfInt(8);
theMatrix.CreateNewRow(0,4);
theMatrix.CreateNewRow(4,5);
theMatrix.SetValue(4,3,7);

The overall length field is the virtual number of rows in the matrix, 8 in this example. The level one array length is the number of blocks in the structure which is hard-coded to 3. Notice that the last block only has length 2 because that’s all that’s needed. The constructor does most of the work:

public BigArrayOfArraysOfInt(int length)
{
this.length = length;
this.levelOneArrayLength = 3;

int remainder = this.length % this.levelOneArrayLength;
if (remainder == 0)
{
levelZeroArrayLength = (this.length / this.levelOneArrayLength) + 0;
this.master = new int[levelZeroArrayLength][][];
for (int i = 0; i < levelZeroArrayLength; ++i)
{
master[i] = new int[this.levelOneArrayLength][];
}
}
else
{
levelZeroArrayLength = (this.length / this.levelOneArrayLength) + 1;
this.master = new int[levelZeroArrayLength][][];
for (int i = 0; i < levelZeroArrayLength – 1; ++i)
{
master[i] = new int[this.levelOneArrayLength][];
}
master[levelZeroArrayLength – 1] = new int[remainder][];
}
} // ctor()

I use the length parameter and the fixed level one length to determine how big the master array is and then allocate. The CreateNewRow method is:

public void CreateNewRow(int row, int rowLength)
{
int levelZeroIndex = row / this.levelOneArrayLength; ;
int levelOneIndex = row % this.levelOneArrayLength;
this.master[levelZeroIndex][levelOneIndex] = new int[rowLength];
}

The code looks asymmetric and took me a while to figure it out. The SetValue method is:

public void SetValue(int row, int col, int value)
{
int levelZeroIndex = row / this.levelOneArrayLength;
int levelOneIndex = row % this.levelOneArrayLength;
this.data[levelZeroIndex][levelOneIndex] [col] = value;
}

As I described in the previous post, I could have implemented the IEnumerable interface so I could traverse the sparse matrix in an elegant way but I prefer to work at a lower level of abstraction. For example:

public void Display()
{
int virtualRow = 0;
for (int i = 0; i < this.master.Length; ++i)
{
Console.WriteLine(“==== Block ” + i + ” ===”);
int[][] currRow = master[i];

for (int j = 0; j < currRow.Length; ++j)
{
Console.Write(“[“);
if (virtualRow < 10) Console.Write(” “);
Console.Write(virtualRow + “] “);
++virtualRow;
Console.Write(j + ” -> “);
int[] data = currRow[j];
if (data == null)
{
Console.WriteLine(” X”);
continue;
}
for (int k = 0; k < data.Length; ++k)
{
Console.Write(” ” + data[k]);
}
Console.WriteLine(“”);
}
Console.WriteLine(“================\n”);
}
}

The virtualRow is a counter that indicates the row number if te sparse matrix were one big matrix. Variabe i traverse the master array. Variable j traverses each level one array. And variable k traverse the “column” arrays.

﻿