Free Java Tutorials >> Table of contents >> Advanced Array Algorithms

2. Matrix Multiplication

Matrix Multiplication

In matrix (linear) algebra, one common thing to do is to multiply two matrices together. For example, if we have two matrices, A and B, as follows:

int[][] A = {{1, 3, 6},
             {2, 5, 4}};
int[][] B = {{0, 7},
             {-1, -2},
             {-3, -4}};
then the matrix multiplication of A and B is {{1 * 0 + 3 * -1 + 6 * -3, 1 * 7 + 3 * -2 + 6 * -4},{2 * 0 + 5 * -1 + 4 * -3, 2 * 7 + 5 * -2 + 4 * -4}} = {{-21, -23},{-17, -12}}. To implement the algorithm for matrix multiplication, we actually need 3 nested loops: 2 loops for each row/columns of the resultant matrix, and one loop for calculating the value at each cell of the resultant matrix.


			
Run

3. Matrix Rotation

Matrix Rotation

Another thing we can do with a matrix is to rotate it. For example with a matrix A: {{1, 3, 6},{2, 5, 4}}, we can rotate it clockwise so that it becomes {{2, 1},{5, 3},{4, 6}}. To achieve that, we need to create a new matrix to store the resultant rotated matrix (note that its dimensions will be flipped with respect to A), and use 2 nest loops to loop through elements in matrix A to populate the resultant matrix.



			
Run

4. Convolution

Convolution

Convolution is an important operation in image processing. It is an operation that takes as inputs: a matrix representing the bitmap of an image, and 3x3 kernel matrix, and a particular point in the image (row and column indices x and y). The operation slices out a 3x3 sub-matrix from the image matrix centered on position (x, y), performs a product on each number in the sub-matrix with the numbers at the corresponding positions in the kernel matrix, and then sums up all the product. For example, if the sub-matrix is : {{a, b, c},{d, e, f},{g, h, i}} and the kernel matrix is {{j, k, l},{m, n, o}, {p, q, r}}, then the convolution would be a * j + b * k + c * l + d * m + e * n + f * o + g * p + h * q + i * r. (If the position (x, y) is on the edge of the image matrix, we treat out-of-bounds positions in the sub-matrix as 0). When calculating convolution, we need to be careful about checking for potentially out-of-bound indices.



			
Run

Previous: Two Dimensional Arrays

Next: Iterative Sorting