04 December, 2013

Three ways to generate a checkerboard matrix

Sometimes it is challenging and broadens the mind to find different solutions for a given task. In this post three methods for generating a checkerboard matrix is discussed.

A checkerboard matrix looks like this:

   0   1   0   1   0
   1   0   1   0   1
   0   1   0   1   0
   1   0   1   0   1
   0   1   0   1   0

We will write a function for this task having the following skeleton:

% generate an n-by-n checkerboard matrix
function C = checkerboard(n)
  % create the output matrix
  C = zeros(n);
end

The shortest, uncommon solution using a special matrix

An uncommon and tricky solution is based on the inverse of Hilbert matrix, which can be calculated by using invhilb MATLAB function. The mathematical background is not interesting for now but its pattern:

>> H = invhilb(4)
H =
     16   -120    240   -140
   -120   1200  -2700   1680
    240  -2700   6480  -4200
   -140   1680  -4200   2800

The sign of the values have the same checkerboard pattern we need: this is true for all matrices of any size generated by this function. By using a simple comparison to zero, we can get the desired result, as the following code example shows:

function C = checkerboard_1(n)
  C = invhilb(n) < 0;
end

The output of this function is:

>> C = checkerboard_1(4)
C =
   0   1   0   1
   1   0   1   0
   0   1   0   1
   1   0   1   0

Although this function is a simple one-liner having minimal complexity, it is not efficient for generating large checkerboard matrices: the runtime for a 1000-by-1000 matrix is about 295.67 milliseconds.

A solution using linear indexing

If you are not familiar with linear indices, please read this tutorial on MATLAB matrix indexing.

To understand the idea behind this approach, please have a look at the following matrix containing the linear indices of its elements. Even linear indices are marked by bold:

   1    6   11   16   21
   2    7   12   17   22
   3    8   13   18   23
   4    9   14   19   24
   5   10   15   20   25

The idea is the following: choose every second element to get the desired pattern. This is definitely a good way to go, but have a look at the following matrix:

   1    5    9   13
   2    6   10   14
   3    7   11   15
   4    8   12   16

This method fails when a matrix has even number of rows. The solution is simple: insert a row before setting every second element to get a matrix having odd number of rows and remove it in the last step.

The source code of this approach is the following:

function C = checkerboard_2(n)
  % case of even rows
  if mod(n, 2) == 0
    C = zeros(n + 1, n);    % create a matrix having a plus row
    C(2 : 2 : end) = 1;     % select every second element
    C(end, :) = [];         % remove the last row from the matrix
  else
    C = zeros(n, n);        % create the matrix
    C(2 : 2 : end) = 1;     % select every second element
  end
end

This solution is longer in code but has better performance: generating an 1000-by-1000 matrix takes 9.82 milliseconds, which is about 30 times faster than the first one.

A solution using the xor operator

First have a look at the following figure showing the positions of zero values, the rows and the columns:

   1  2  3  4  5
1  +     +     +
2     +     +
3  +     +     + 
4     +     +
5  +     +     +

Those elements are zero, where the row and the column indices are both even or both odd. Since this depends only on the parity, modify the figure containing the indices modulo two:

   1  0  1  0  1
1  +     +     +
0     +     +
1  +     +     + 
0     +     +
1  +     +     +

The desired result can be achieved by using the exclusive or (xor) operator, which is described by the following formula:

$$ xor(A, B) = A \oplus B = \begin{cases} 0: & A = B \\ 1: & A \ne B \\ \end{cases} $$

The algorithm is the following: generate the parity map which equals to the indices modulo two, then expand it and use the xor operator. See the following detailed example for a checkerboard matrix of size four:

n = 4;                  % the size of the matrix
i = 1 : n               % the index list
p = mod(i, 2)           % calculate parity

r = repmat(p,  [n 1])   % expand the parities to rows
c = repmat(p', [1 n])   % expand the parities to columns

M = xor(r, c)           % apply the xor operator

The output of the code example is:

i =
   1   2   3   4

p =
   1   0   1   0

r =
   1   0   1   0
   1   0   1   0
   1   0   1   0
   1   0   1   0

c =
   1   1   1   1
   0   0   0   0
   1   1   1   1
   0   0   0   0

M =
   0   1   0   1
   1   0   1   0
   0   1   0   1
   1   0   1   0

MATLAB bsxfun function is a perfect choice to do the needed steps. An important property of this function is the following:

Whenever a dimension of A or B is singleton (equal to one), bsxfun virtually replicates the array along that dimension to match the other array.

The dimensions are automatically extended to match each other, so we have only to generate the parity map and pass it both in row and column format. The third parameter of the function identifies the operator being applied on the inputs, in our case, this is the xor operator.

The final source code for this approach is:

function C = checkerboard_3(n)
  % generate the parity map
  p = mod(1 : n, 2);
  % pass the xor operator, a column and a row vector
  % containing the parity data
  C = bsxfun(@xor, p', p); 
end

This code requires only 2.17 milliseconds to generate an 1000-by-1000 checkerboard matrix. This is 4.5 times faster than the second approach using linear indexing and is 140 times faster, than the first method based on the inverse of Hilbert matrix.

         

New comment

comments powered by Disqus