Efficient method to store a Lower Triangular Matrix using Column-major mapping
Given a lower triangular matrix Mat[][], the task is to store the matrix using column-major mapping.
Lower Triangular Matrix: A Lower Triangular Matrix is a square matrix in which the lower triangular part of a matrix consists of non-zero elements and the upper triangular part consists of 0s. The Lower Triangular Matrix for a 2D matrix Mat[][] is mathematically defined as:
- If i < j, set Mat[i][j] = 0.
- If i >= j, set Mat[i][j] > 0.
Illustration:
Below is a 5×5 lower triangular matrix. In general, such matrices can be stored in a 2D array, but when it comes to matrices of large size, it is not a good choice because of its high memory consumption due to the storage of unwanted 0s.
Such a matrix can be implemented in an optimized manner.
The efficient way to store the lower triangular matrix of size N:
- Count of non-zero elements = 1 + 2 + 3 + … + N = N * (N + 1) /2.
- Count of 0s = N2 – (N * (N + 1) /2 = (N * (N – 1)/2.
Now let see how to represent lower triangular matrices in the program. Notice that storing 0s must be avoided to reduce memory consumption. As calculated, for storing non-zero elements, N*(N + 1)/2 space is needed. Taking the above example, N = 5. Array of size 5 * (5 + 1)/2 = 15 is required to store the non-zero elements.
Now, elements of the 2D matrix can be stored in a 1D array, column by column, as shown below:
Array to store Lower Triangular Elements
Apart from storing the elements in an array, a procedure for extracting the element corresponding to the row and column number is also required. Using Column-Major-Mapping for storing a lower triangular matrix, the element at index Mat[i][j] can be represented as:
Index of Mat[i][j] matrix in the array A[] = [n*(j-1)-(((j-2)*(j-1))/2)+ (i-j))]
Below is the implementation of the above article:
C++
// C++ program for the above approach #include <bits/stdc++.h>#include<stdio.h>using namespace std;// Dimensions of the matrix const int N = 5;// Structure of a memory // efficient matrixstruct Matrix { int* A; int size;};// Function to set the // values in the Matrix void Set(struct Matrix* m, int i, int j, int x){ if (i >= j) m->A[((m->size)*(j-1)-(((j-2) *(j-1))/2)+(i-j))] = x;}// Function to store the // values in the Matrix int Get(struct Matrix m, int i, int j){ if (i >= j) return m.A[((m.size)*(j-1)-(((j-2) *(j-1))/2)+(i-j))]; else return 0;}// Function to display the // elements of the matrix void Display(struct Matrix m){ // Traverse the matrix for (int i = 1; i <= m.size; i++) { for (int j = 1; j <= m.size; j++) { if (i >= j) cout<< m.A[((m.size)*(j-1)-(((j-2) *(j-1))/2)+(i-j))] <<" "; else cout<<"0 "; } cout<<endl; }}// Function to generate an efficient matrix struct Matrix createMat(int Mat[N][N]) { // Declare efficient Matrix struct Matrix mat; // Initialize the Matrix mat.size = N; mat.A = (int*)malloc( mat.size * (mat.size + 1) / 2 * sizeof(int)); // Set the values in matrix for (int i = 1; i <= mat.size; i++) { for (int j = 1; j <= mat.size; j++) { Set(&mat, i, j, Mat[i - 1][j - 1]); } } // Return the matrix return mat; } // Driver Codeint main(){ // Given Input int Mat[5][5] = { { 1, 0, 0, 0, 0 }, { 1, 2, 0, 0, 0 }, { 1, 2, 3, 0, 0 }, { 1, 2, 3, 4, 0 }, { 1, 2, 3, 4, 5 } }; // Function call to create a memory // efficient matrix struct Matrix mat = createMat(Mat); // Function call to // print the Matrix Display(mat); return 0;}// This code is contributed by rrrtnx. |
C
// C program for the above approach #include <stdio.h>#include <stdlib.h>// Dimensions of the matrix const int N = 5;// Structure of a memory // efficient matrixstruct Matrix { int* A; int size;};// Function to set the // values in the Matrix void Set(struct Matrix* m, int i, int j, int x){ if (i >= j) m->A[((m->size)*(j-1)-(((j-2) *(j-1))/2)+(i-j))] = x;}// Function to store the // values in the Matrix int Get(struct Matrix m, int i, int j){ if (i >= j) return m.A[((m.size)*(j-1)-(((j-2) *(j-1))/2)+(i-j))]; else return 0;}// Function to display the // elements of the matrix void Display(struct Matrix m){ // Traverse the matrix for (int i = 1; i <= m.size; i++) { for (int j = 1; j <= m.size; j++) { if (i >= j) printf("%d ", m.A[((m.size)*(j-1)-(((j-2) *(j-1))/2)+(i-j))]); else printf("0 "); } printf("\n"); }}// Function to generate an efficient matrix struct Matrix createMat(int Mat[N][N]) { // Declare efficient Matrix struct Matrix mat; // Initialize the Matrix mat.size = N; mat.A = (int*)malloc( mat.size * (mat.size + 1) / 2 * sizeof(int)); // Set the values in matrix for (int i = 1; i <= mat.size; i++) { for (int j = 1; j <= mat.size; j++) { Set(&mat, i, j, Mat[i - 1][j - 1]); } } // Return the matrix return mat; } // Driver Codeint main(){ // Given Input int Mat[5][5] = { { 1, 0, 0, 0, 0 }, { 1, 2, 0, 0, 0 }, { 1, 2, 3, 0, 0 }, { 1, 2, 3, 4, 0 }, { 1, 2, 3, 4, 5 } }; // Function call to create a memory // efficient matrix struct Matrix mat = createMat(Mat); // Function call to // print the Matrix Display(mat); return 0;} |
Java
import java.util.Arrays;class Matrix { // Structure of a memory // efficient matrix int size; int[][] matrix; public Matrix(int size) { this.size = size; this.matrix = new int[size][size]; } // Function to set the // values in the Matrix public void set(int i, int j, int x) { if (i >= j) { matrix[i][j] = x; } } // Function to store the // values in the Matrix public int get(int i, int j) { if (i >= j) { return matrix[i][j]; } else { return 0; } } // Function to display the // elements of the matrix public void display() { // Traverse the matrix for (int[] row : matrix) { System.out.println(Arrays.toString(row)); } }}public class Main { // Function to generate an efficient matrix public static Matrix createMat(int[][] mat) { int n = mat.length; Matrix matrix = new Matrix(n); // Set the values in matrix for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { matrix.set(i, j, mat[i][j]); } } // Return the matrix return matrix; } public static void main(String[] args) { // Driver Code int[][] mat = { {1, 0, 0, 0, 0}, {1, 2, 0, 0, 0}, {1, 2, 3, 0, 0}, {1, 2, 3, 4, 0}, {1, 2, 3, 4, 5} }; // Function call to create a memory // efficient matrix Matrix m = createMat(mat); // Function call to // print the Matrix m.display(); }} |
Python3
class Matrix: def __init__(self, size): self.size = size self.matrix = [[0 for _ in range(size)] for __ in range(size)] def set(self, i, j, x): if i >= j: self.matrix[i][j] = x def get(self, i, j): if i >= j: return self.matrix[i][j] else: return 0 def display(self): for row in self.matrix: print(row)def create_mat(mat): n = len(mat) matrix = Matrix(n) for i in range(n): for j in range(n): matrix.set(i, j, mat[i][j]) return matrixif __name__ == '__main__': mat = [[1, 0, 0, 0, 0], [1, 2, 0, 0, 0], [1, 2, 3, 0, 0], [1, 2, 3, 4, 0], [1, 2, 3, 4, 5]] m = create_mat(mat) m.display() |
C#
using System;class Matrix{ // Structure of a memory // efficient matrix private int size; private int[,] matrix; public Matrix(int size) { this.size = size; this.matrix = new int[size, size]; } // Function to set the // values in the Matrix public void Set(int i, int j, int x) { if (i >= j) { matrix[i, j] = x; } } // Function to store the // values in the Matrix public int Get(int i, int j) { if (i >= j) { return matrix[i, j]; } else { return 0; } } // Function to display the // elements of the matrix public void Display() { // Traverse the matrix for (int i = 0; i < size; i++) { for (int j = 0; j < size; j++) { if (i >= j) { Console.Write(matrix[i, j] + " "); } else { Console.Write("0 "); } } Console.WriteLine(); } }}class Program{ // Function to generate an efficient matrix public static Matrix CreateMat(int[,] mat) { int n = mat.GetLength(0); Matrix matrix = new Matrix(n); // Set the values in matrix for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { matrix.Set(i, j, mat[i, j]); } } // Return the matrix return matrix; } static void Main(string[] args) { // Driver Code int[,] mat = { {1, 0, 0, 0, 0}, {1, 2, 0, 0, 0}, {1, 2, 3, 0, 0}, {1, 2, 3, 4, 0}, {1, 2, 3, 4, 5} }; // Function call to create a memory // efficient matrix Matrix m = CreateMat(mat); // Function call to // print the Matrix m.Display(); }} |
Javascript
// Dimensions of the matrixconst N = 5;// Structure of a memory// efficient matrixclass Matrix { constructor() { this.A = new Array(); this.size = 0; }}// Function to set the// values in the Matrixfunction Set(m, i, j, x) { if (i >= j) { m.A[m.size * (j - 1) - ((j - 2) * (j - 1)) / 2 + (i - j)] = x; }}// Function to store the// values in the Matrixfunction Get(m, i, j) { if (i >= j) { return m.A[m.size * (j - 1) - ((j - 2) * (j - 1)) / 2 + (i - j)]; } else { return 0; }}// Function to display the// elements of the matrixfunction Display(m) { // Traverse the matrix for (let i = 1; i <= m.size; i++) { let row = ""; for (let j = 1; j <= m.size; j++) { if (i >= j) { row += m.A[m.size * (j - 1) - ((j - 2) * (j - 1)) / 2 + (i - j)] + " "; } else { row += "0 "; } } console.log(row); }}// Function to generate an efficient matrixfunction createMat(Mat) { // Declare efficient Matrix let mat = new Matrix(); // Initialize the Matrix mat.size = N; mat.A = new Array(mat.size * (mat.size + 1) / 2).fill(0); // Set the values in matrix for (let i = 1; i <= mat.size; i++) { for (let j = 1; j <= mat.size; j++) { Set(mat, i, j, Mat[i - 1][j - 1]); } } // Return the matrix return mat;}// Driver Codelet Mat = [ [1, 0, 0, 0, 0], [1, 2, 0, 0, 0], [1, 2, 3, 0, 0], [1, 2, 3, 4, 0], [1, 2, 3, 4, 5],];// Function call to create a memory// efficient matrixlet mat = createMat(Mat);// Function call to// print the MatrixDisplay(mat); |
Output
1 0 0 0 0 1 2 0 0 0 1 2 3 0 0 1 2 3 4 0 1 2 3 4 5
Time Complexity: O(N2)
Auxiliary Space: O(N2)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
