Algorithm to minimize the space complexity of a sparse matrix?

Question

When storing and manipulating sparse matrices on a computer (zeros and ones), it is beneficial and often necessary to use specialized algorithms and data structures that take advantage of the sparse structure of the matrix. Operations using standard matrix structures and algorithms are slow and consume large amounts of memory when applied to large sparse matrices. Sparse data is by nature easily compressed, and this compression almost always results in significantly less memory usage.

You are given a two dimensional matrix where the number of rows are known in advance (You can select any number between 30-256). The number of columns is very, very big. You can think of 10⁶ columns. Each column has exactly 1 value of one.

Write an algorithm that minimizes the space complexity of this matrix. You can show how your algorithm works and even write a program.

Answer 1

Step one: define miximize

Answer 2

Hint (as this is for homework): each column contains exactly one field with '1', so it should be sufficient to store, for each column, the row for which this is the case. Now think about a good way of storing this information, taking into account that the number of rows is <= 256.

Answer 3

Sparse Matrices are stored in 2 different ways in CS. Adjacent Matrices or Adjacent Lists: I think you're wanting to use Matrices, so we have several options: CSR's, Jagged Diagonals, CSC's etc etc: Recommend wikipedia them to learn the algorithms. Its essentially breaking down a Matrix into 3 different 1-d arrays.

Answer 4

Hi, I wrote a simple algorithm that minimize the space required to represent Sparse Matrix, I think you may find it useful :) .

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace sparse_matrix
{
    class Program
    {
        static void Main(string[] args)
        {
            /*
             * In this algorithm I store all the Sparse Matrix into single diminsion matrix of type byte, each row
             * in this matrix has a number that represent the position of the "1" in the original Sparse matrix.
             * By this way, I save a lot of space... and store the same matrix with the minimum space(I could reach)
             * Since I treat the digits as bits, and stored them into the byte, since the biggest number I will reach
             * will not exceed 255 bit.
             * I read about the byte data type from here:(http://msdn.microsoft.com/en-us/library/5bdb6693.aspx)
             * In this program, I run it on a (3 * 3) matrix, however it can work the same for (255 * 10^6)
             */
            int matrixRows = 3;
            int matrixColumns = 3;
            int[,] matrix;
            matrix = new int[matrixRows, matrixColumns];
            matrix[0, 0] = 0;
            matrix[1, 0] = 0;
            matrix[2, 0] = 1;
            matrix[0, 1] = 1;
            matrix[1, 1] = 0;
            matrix[2, 1] = 0;
            matrix[0, 2] = 0;
            matrix[1, 2] = 1;
            matrix[2, 2] = 0;

            byte []x = new byte [matrixColumns];
            Console.WriteLine("The Original Sparse Matrix:\n");

            for (int i = 0; i != matrixColumns; i++)
            {
                for (int j = 0; j != matrixRows; j++)
                {
                    if (matrix[j, i] == 1)
                    {                        
                        x[i] = (byte)j;
                    }
                    Console.Write(matrix[i, j] + " ");
                }
                Console.WriteLine();
                Console.WriteLine();
            }
            Console.WriteLine();
            Console.WriteLine();
            Console.WriteLine("The new representation for the Sparse matrix:\n");
            for (int k = 0; k != matrixColumns; k++)
            {
                Console.WriteLine(x[k] + "\n");
            }
        }
    }
}

I will be happy to receive any feedback from you.

Answer 5

i need a two dimensional matrix where the number of rows are known in advance (You can select any number between 30-256). The number of columns is very, very big. You can think of 106 columns. Each column has exactly 1 value of one.

Answer 6

You are working with a heavily constrained problem, far more so than "general" sparse matrices you see appearing in (for example) finite element code. In particular, you can take advantage of these items that most of the time people can't:

1. The number of rows is constant and you get to pick it.
2. The number appearing in any cell of the matrix is either 1 or 0.
3. Each column contains 1 and only 1 non-zero value.

Let me pause here to say this matrix appears in close to this form in one very common case: a permutation matrix, but in those cases it's always a square matrix (same number of rows as columns).

Here's a very basic compression scheme that's easy to implement, and easy to write down the exact number of bytes required to store a matrix of size Nx*M* (N rows, M columns). Let N=256, which means we can represent a row as a number from 0-255, which is exactly an unsigned 8-bit number. Store the matrix as a 1x*M* array of unsigned 8-bit (1 byte) integers, where the value at index i is the row number containing the value 1 in column i. There's no reason to store the value itself (since it's always 1), and there's no need to store the column number explicitly because we represent it as the array index.

Suppose a "dense" NxM matrix stores 4-byte integers. Such a matrix would require N*M*4 bytes of memory. With the compression I described, it would only take M bytes of memory, which as described is 1/1024 of the original memory!

Answer 7

not to means your answer