Fast Sparse Matrix expansion and population without converting to CoordinateFormat

[MissedSte4k]

Hi,
I have this problem I've been trying to solve for a while, maybe someone will have any ideas. I have massive SparseMatrix'es that I want to expand and populate the expanded parts. At first I tried doing expansion and population using SetSubMatrix() and SparseCompressedRowMatrixStorage.At(). The implementation worked until the size reached something around 50k x 50k. At that point the expansion by 1k took about 5min. I won't expand into all the tings and combinations I've tried to make this approach work, but the final approach after a lot of research I have managed to do is this:

TLDR: convert entire matrix to Coordinate Format -> add all the new points -> create new SparseCompressedRowMatrixStorage from Coordinate format.

public static Matrix<double> BuildSymmetricMatrix(Dictionary<string, List<KeyValuePair<string, int>>> input, List<string> order, Dictionary<string, int> orderDict, Matrix<double> oldMatrix)
{
	var matrixSize = order.Count;
	var oldMatrixSize = oldMatrix.RowCount;

	//create matrix of new size

	if (oldMatrix.Storage is SparseCompressedRowMatrixStorage<double> sparse)
	{
		var columns = new List<int>(sparse.ValueCount);
		var rows = new List<int>(sparse.ValueCount);
		var values = new List<double>(sparse.ValueCount);

		// Efficiently populate lists

		foreach (var (row, col, value) in sparse.EnumerateNonZeroIndexed())
		{
			columns.Add(col);
			rows.Add(row);
			values.Add(value);
		}
                oldMatrix = null;
                sparse = null;
                GC.Collect();
                GC.WaitForPendingFinalizers();  //force clean to release the oldMatrix
		for (int i = oldMatrixSize; i < matrixSize; i++)
		{
			var item = order[i];
			foreach (var keyValue in input[item])
			{
				if (orderDict.TryGetValue(keyValue.Key, out int j))
				{
					//row
					rows.Add(i);
					columns.Add(j);
					values.Add(keyValue.Value);
					//collumn
					rows.Add(j);
					columns.Add(i);
					values.Add(keyValue.Value);
				}
			}
		}
		return Matrix<double>.Build.Sparse(
		SparseCompressedRowMatrixStorage<double>.OfCoordinateFormat(order.Count, order.Count, values.Count, rows.ToArray(), columns.ToArray(), values.ToArray())
	);

	}
	else
	{
		Logger.Info($"Matrix is not sparse {sw.ElapsedMilliseconds}");
		throw new InvalidOperationException("Matrix should always be sparse");
	}

}

Using this approach I can currently expand 50k x 50k matrix by 1k in around 300ms. The problem I'm facing now, is due to all the walkarounds I'm basically 3x the memory usage, because I have oldMatrix, row/col/val[] and new Matrix. This doesn't impact the system too much at first, but when the matrix expands to 400k x 400k and the Data alone above - 4 GB of RAM by using this method I create a spike of about 12GB.

My question is - Is there any approach I could use to batch update/expand the SparseCompressedRowMatrixStorage using At() or any other function without forcing NormalizeOrdering(), NormalizeDuplicates() or any other unnecessary functions, until all the items are added to the storage without using my RAM heavy workaround?

[MissedSte4k]

Ok - took some more time and a lot of thinking, but I think I managed to solve my problem by basically recreating a something close to an expanded OfCompressedSparseColumnFormat() method.

/// <summary>
/// Create new expanded storage
/// </summary>
/// <param name="existingMatrix">The matrix you want to be expanded</param>
/// <param name="newRowCount">Total new row count</param>
/// <param name="newColumnCount">Total new collumn count</param>
/// <param name="additionalValueCount">The amount of new values added</param>
/// <param name="newRowIndices">indices for new rows that should be added</param>
/// <param name="newColumnIndices">indices for new columns that should be added</param>
/// <param name="newValues">new values that should be added</param>
/// <returns></returns>
public static SparseCompressedRowMatrixStorage<double> ExpandStorage(
SparseCompressedRowMatrixStorage<double> existingMatrix,
int newRowCount,
int newColumnCount,
int additionalValueCount,
int[] newRowIndices,
int[] newColumnIndices,
double[] newValues)
{
	// Create new RowPointers, Values, and ColumnIndices arrays
	int[] newRowPointers = new int[newRowCount + 1];
	double[] newValuesArray = new double[existingMatrix.ValueCount + additionalValueCount];
	int[] newColumnIndicesArray = new int[existingMatrix.ValueCount + additionalValueCount];

	// Copy existing RowPointers, Values, and ColumnIndices
	Array.Copy(existingMatrix.RowPointers, newRowPointers, existingMatrix.RowCount);
	Array.Copy(existingMatrix.Values, newValuesArray, existingMatrix.ValueCount);
	Array.Copy(existingMatrix.ColumnIndices, newColumnIndicesArray, existingMatrix.ValueCount);

	//remake pointers to not be cumulative
	for (int i = 0; i < existingMatrix.RowCount; i++)
	{
		newRowPointers[i] = existingMatrix.RowPointers[i + 1] - existingMatrix.RowPointers[i];
	}

	// update count for all pointers
	for (int i = 0; i < additionalValueCount; i++)
	{
		newRowPointers[newRowIndices[i]]++;
	}

	// make pointers cumulative again
	int num = 0;
	for (int j = 0; j <= newRowCount; j++)
	{
		int num2 = newRowPointers[j];
		newRowPointers[j] = num;
		num += num2;
	}

	// based on previous pointers copy old values to new places
	for (int i = existingMatrix.RowCount - 1; i >= 0; i--) // Start from the end
	{
		int oldStart = existingMatrix.RowPointers[i]; // the position of old point
		int oldCount = existingMatrix.RowPointers[i + 1] - existingMatrix.RowPointers[i]; // count of old

		if (oldStart != newRowPointers[i]) //if positions are not the same - move values
		{
			Array.Copy(newValuesArray, oldStart, newValuesArray, newRowPointers[i], oldCount);
			Array.Copy(newColumnIndicesArray, oldStart, newColumnIndicesArray, newRowPointers[i], oldCount);
		}
	}

	//make temp rowPointers to track new positioning
	int[] tempRowPointers = new int[newRowCount + 1];
	Array.Copy(newRowPointers, tempRowPointers, newRowPointers.Length);

	// add new columns and values into the matrix
	for (int k = additionalValueCount - 1; k >= 0; k--)
	{
		int rowIndex = newRowIndices[k];
		int insertIndex = --tempRowPointers[rowIndex + 1];

		// Insert new value and column index
		newValuesArray[insertIndex] = newValues[k];
		newColumnIndicesArray[insertIndex] = newColumnIndices[k];
	}

	SparseCompressedRowMatrixStorage<double> updatedMatrix = SparseCompressedRowMatrixStorage<double>.OfCompressedSparseRowFormat(
		newRowCount,
		newColumnCount,
		newValuesArray.Length,
		newRowPointers,
		newColumnIndicesArray,
		newValuesArray
	);

	return updatedMatrix;
}

Would love for someone to look at it and possibly add to the project