Blog

Sparse Matrix in Java

A sparse matrix is a matrix in which most of the elements are zero. This type of matrix is significant in various computational applications due to its efficiency in storage and performance. In this blog, we will explore what a sparse matrix is, its role in data structures, provide an example, and discuss different approaches to implementing a sparse matrix in Java.

What is a Sparse Matrix?

A sparse matrix is a matrix where the number of zero elements is significantly greater than the number of non-zero elements. These matrices are common in various scientific and engineering applications, such as in solving systems of linear equations, computer graphics, and network analysis. The primary advantage of using sparse matrices is the reduction in memory usage and computational complexity.

What is a Sparse Matrix in Data Structure?

In data structures, a sparse matrix is typically represented in a way that only the non-zero elements are stored, thus saving memory space. The sparse matrix can be represented using:

  1. Coordinate List (COO): A simple list of tuples containing row index, column index, and value.
  2. Compressed Sparse Row (CSR): Uses three arrays to store the non-zero values, the extents of the rows, and the column indices.
  3. Compressed Sparse Column (CSC): Similar to CSR, but compresses column indices instead of row indices.

Sparse Matrix Example

Consider the following 4×4 matrix:

0  0  0  5
0  8  0  0
0  0  3  0
9  0  0  0

This matrix can be efficiently represented using a list of non-zero elements:

[(0, 3, 5), (1, 1, 8), (2, 2, 3), (3, 0, 9)]

Different Approaches to Sparse Matrix Program in Java

below we’ll discuss different approaches to implementing a sparse matrix in Java:

1. Using a List of Tuples (COO Format)

Code to find Sparse Matrix in Java by using a list of tuples 

import java.util.ArrayList;
import java.util.List;

public class SparseMatrix {
    private List<int[]> elements;
    private int rows;
    private int cols;

    public SparseMatrix(int rows, int cols) {
        this.rows = rows;
        this.cols = cols;
        this.elements = new ArrayList<>();
    }

    public void addElement(int row, int col, int value) {
        if (value != 0) {
            elements.add(new int[]{row, col, value});
        }
    }

    public void printMatrix() {
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                int value = 0;
                for (int[] element : elements) {
                    if (element[0] == i && element[1] == j) {
                        value = element[2];
                        break;
                    }
                }
                System.out.print(value + " ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        SparseMatrix matrix = new SparseMatrix(4, 4);
        matrix.addElement(0, 3, 5);
        matrix.addElement(1, 1, 8);
        matrix.addElement(2, 2, 3);
        matrix.addElement(3, 0, 9);
        matrix.printMatrix();
    }
}

Explanation of the Code

  • The code defines a `SparseMatrix` class to efficiently handle and print a sparse matrix, where most elements are zero. 
  • The class has a constructor to initialize the matrix with a specified number of rows and columns and an `elements` list to store non-zero elements as `{row, col, value}` arrays.
  • The `addElement` method adds non-zero elements to the matrix. 
  • The `printMatrix` method prints the entire matrix by iterating through all possible positions and checking if each position matches any element in the `elements` list, printing the corresponding value or zero if no match is found.
  • In the `main` method, a `SparseMatrix` object is created and populated with non-zero elements, then the matrix is printed to the console.

Output:

0 0 0 5 
0 8 0 0 
0 0 3 0 
9 0 0 0

2. Using Compressed Sparse Row (CSR) Format

import java.util.ArrayList;
import java.util.List;

public class CSRMatrix {
    private List<Integer> values;
    private List<Integer> columnIndices;
    private List<Integer> rowPointers;
    private int rows;
    private int cols;

    public CSRMatrix(int rows, int cols) {
        this.rows = rows;
        this.cols = cols;
        this.values = new ArrayList<>();
        this.columnIndices = new ArrayList<>();
        this.rowPointers = new ArrayList<>();
        this.rowPointers.add(0);
    }

    public void addElement(int row, int col, int value) {
        if (value != 0) {
            values.add(value);
            columnIndices.add(col);
            if (rowPointers.size() <= row) {
                rowPointers.add(values.size() - 1);
            }
        }
    }

    public void finalizeMatrix() {
        rowPointers.add(values.size());
    }

    public void printMatrix() {
        for (int i = 0; i < rows; i++) {
            int rowStart = rowPointers.get(i);
            int rowEnd = rowPointers.get(i + 1);
            for (int j = 0; j < cols; j++) {
                int value = 0;
                for (int k = rowStart; k < rowEnd; k++) {
                    if (columnIndices.get(k) == j) {
                        value = values.get(k);
                        break;
                    }
                }
                System.out.print(value + " ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        CSRMatrix matrix = new CSRMatrix(4, 4);
        matrix.addElement(0, 3, 5);
        matrix.addElement(1, 1, 8);
        matrix.addElement(2, 2, 3);
        matrix.addElement(3, 0, 9);
        matrix.finalizeMatrix();
        matrix.printMatrix();
    }
}

Explanation of the Code:

  • The code defines a `CSRMatrix` class to represent a sparse matrix using the Compressed Sparse Row (CSR) format. The class has lists for storing non-zero values, their column indices, and pointers indicating the start of each row. 
  • The constructor initializes these lists and the matrix dimensions. The `addElement` method adds non-zero values to the matrix, storing them in the `values` list and their column positions in the `columnIndices` list, updating `rowPointers` as needed. 
  • The `finalizeMatrix` method marks the end of the last row. The `printMatrix` method iterates through the matrix, using the `rowPointers` to locate non-zero values, and prints the matrix, inserting zeros where necessary.
  • In the `main` method, a `CSRMatrix` object is created, populated with non-zero elements, finalized, and printed.

Output:

0 0 0 5 
0 8 0 0 
0 0 3 0 
9 0 0 0

Conclusion

Sparse matrices are crucial for optimizing storage and computational efficiency in various applications. By representing only the non-zero elements, we can significantly reduce the memory footprint and improve performance. In this blog, we discussed what a sparse matrix is, its significance in data structures, and provided examples of different approaches to implementing sparse matrix programs in Java. Whether you use the COO or CSR format, understanding sparse matrices can greatly enhance your programming and data management skills. For more blogs and coding resources, visit Newtum. Happy coding!

About The Author

Sagar Salunkhe

See author's posts

Leave a Reply