- A 2-D array is a list of a finite number m×n of homogenous data elements.
- The elements of the array are referred by two index sets consisting of m and n consecutive integer numbers.
- The elements of the array are stored in consecutive memory location.
- 2-D arrays are called matrices in mathematics and tables in business applications
Representing 2D array in memory
- The elements are stored column by column i. e. m elements of first column and stored in first m locations, elements of the second column are stored in next m locations and so on.
- The elements are sorted row by row for n elements.
For 2-D array a of size m×n , using the base address of a[i][j] element by:
In column major order
loc(a[i][j]) =base(a) +w(m*j+i)
In row major order
loc (a[i][j])=base(a) +w(n*i+j)
where, w=width i. e. number of bytes taken by each element
m=total number of rows
n=total number of columns
Note:The product A×B of two matrices A and B is defined only when the number of columns in A equals to the number of rows in B.
- A square matrix has the same number of rows and columns.
- Some special form of square matrix are:
- Diagonal matrix
- Tridiagonal matrix
- Lower triangular matrix
- Upper triangular matrix
- A matrix B is diagonal iff B(i,j) =0 for i≠j
- The diagonal matrix can be stored as 1-D array to reduce memory space.
- A matrix B is trdiagonal iff B(i,j) =0 for |i-j|>1
- In a n×n tridiagonal matrix B, the non-zero elements lie on one of the three diagonals.
- Main diagonal , for which i=j.It has n elements.
- Diagonal below main diagonal, for which i=j+1.It has n-1 elements.
- Diagonal above main diagonal, for which i=j-1.It has n-1 elements.
- It has 3n-2 non-zero elements.
- The elements of tridiagonal matrix can be mapped up by following ways
- Row wise
- Column wise
- Diagonal wise beginning with the lowest.
Lower triangular matrix
- A matrix B is lower triangular iff B(i,j) =0 for i<j
Upper triangular matrix
- A matrix B is upper triangular iff B(i,j) =0 for i>j
- Total number of non-zero elements in triangular matrix is n(n+1) /2
- A m×n matrix A is said to be sparse if many of its elements are zero.
- Matrix that is not sparse is known as dense matrix.
- It is not possible to define an exact boundary between dense and sparse matrices.
- The diagonal and tridiagonal matrices fit into the category of sparse matrices.
Array representation of sparse matrices
- In array representation, an array of triplets of type
- is used to store non-zero elements, where first field of the triplet is used to record row position, second to record column position and third one to record non-zero element of the sparse matrix.
- In addition, we need to record the size of the matrix(i.e. number of rows and columns) and non-zero elements. For this purpose, the first element of array triplet is used, where first field stores number of rows, second field stores number of non-zero elements . The remanining elements of the array store non-zero elements of the sparse matrix on row major order.
- A linear array can be called 1-D array, since each element in the array is referred by a single subscript.
- A 2-D ‘m×n’ array is a collection of m. n data elements such that each element is specified called subscriptsA[i],[j]
- A 3-D array ‘m×n×s’ . Then it contains m. n. elements.
- For example, Suppose B is a three dimensional 2×4×3 array, then B contains 2.4.3=24 elements.