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.

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.

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.

Previous: Two Dimensional Arrays

Next: Iterative Sorting