Sparse Matrix and its representations
A matrix is a two-dimensional data object made of m rows and n columns,
therefore having total m x n values. If most of the elements of the matrix
have 0 value, then it is called a sparse matrix.
Why to use Sparse Matrix instead of simple matrix ?
Storage: There are lesser non-zero elements than zeros and thus lesser
memory can be used to store only those elements.
Computing time: Computing time can be saved by logically designing a data
structure traversing only non-zero elements.
e.g
0 0 3 0 4
0 0 5 7 0
0 0 0 0 0
0 2 6 0 0
Representing a sparse matrix by a 2D array leads to wastage of lots of memory as
zeroes in the matrix are of no use in most of the cases. So, instead of storing
zeroes with non-zero elements, we only store non-zero elements. This means
storing non-zero elements with triples- (Row, Column, value).
Sparse Matrix Representations can be done in many ways following are two
common representations:
1. Array representation
2. Linked list representation
Method 1: Using Arrays:
2D array is used to represent a sparse matrix in which there are three
rows named as
Row: Index of row, where non-zero element is located
Column: Index of column, where non-zero element is located
Value: Value of the non zero element located at index - (row,column)
Time Complexity: O(NM), where N is the number of rows in the sparse matrix,
and M is the number of columns in the sparse matrix.
Auxiliary Space: O(NM), where N is the number of rows in the sparse matrix,
and M is the number of columns in the sparse matrix.
Method 2: Using Linked Lists
In linked list, each node has four fields. These four fields are defined as:
Row: Index of row, where non-zero element is located
Column: Index of column, where non-zero element is located
Value: Value of the non zero element located at index - (row,column)
Next node: Address of the next node
Time Complexity: O(N*M), where N is the number of rows in the sparse
matrix, and M is the number of columns in the sparse matrix.
Auxiliary Space: O(K), where K is the number of non-zero elements in the array.
Polynomial representations
Polynomials are mathematical expressions made up of variables (often
represented by letters like x, y, etc.), constants (like numbers), and exponents
(which are non-negative integers). These expressions are combined using
addition, subtraction, and multiplication operations.
A polynomial can have one or several terms. Each term is a product of a constant
and a variable raised to an exponent.
For Example:
• x 2,
• x2 + 2x,
• 5x + y,
• 3x3 + 5x2 - 4x,
• √2(x) + y, etc.
In the image added below, we have shown a polynomial, with variables,
constants, and a leading coefficient:
18*x0=18*1=1
8
1. Array Representation:
Concept:
This method utilizes an array where each index corresponds to an exponent, and the
value stored at that index represents the coefficient of that exponent. The array size is
determined by the highest degree (exponent) in the polynomial.
Example:
For the polynomial
𝑃(𝑥)=4𝑥3+6𝑥2+7𝑥+9 , an array P could be used as follows:
Code
9 7 6 4
P[0] = 9 (coefficient of x^0) 0 1 2 3
P[1] = 7 (coefficient of x^1)
P[2] = 6 (coefficient of x^2)
P[3] = 4 (coefficient of x^3)
Advantages: Simple to implement, direct access to coefficients by exponent.
Disadvantages: Inefficient for sparse polynomials (polynomials with many zero
coefficients), as memory is allocated for all exponents up to the highest degree, even
if their coefficients are zero.
2. Linked List Representation:
Concept:
A linked list is used, where each node in the list represents a non-zero term of the
polynomial. Each node typically contains two fields: one for the coefficient and one
for its corresponding exponent, along with a pointer to the next node.
Example:
Advantag
es:
Efficient for sparse polynomials as only non-zero terms are stored, dynamic memory
allocation allows for flexible size.
Disadvantages:
Requires more memory per term (due to pointers), access to a specific term requires
traversing the list.
The choice between array and linked list representation depends on the specific
characteristics of the polynomial (e.g., sparsity) and the operations to be performed.
