Next: , Previous: , Up: Vectorization and Faster Code Execution   [Contents][Index]


19.2 Broadcasting

Broadcasting refers to how Octave binary operators and functions behave when their matrix or array operands or arguments differ in size. Since version 3.6.0, Octave now automatically broadcasts vectors, matrices, and arrays when using elementwise binary operators and functions. Broadly speaking, smaller arrays are “broadcast” across the larger one, until they have a compatible shape. The rule is that corresponding array dimensions must either

  1. be equal, or
  2. one of them must be 1.

In case all dimensions are equal, no broadcasting occurs and ordinary element-by-element arithmetic takes place. For arrays of higher dimensions, if the number of dimensions isn’t the same, then missing trailing dimensions are treated as 1. When one of the dimensions is 1, the array with that singleton dimension gets copied along that dimension until it matches the dimension of the other array. For example, consider

x = [1 2 3;
     4 5 6;
     7 8 9];

y = [10 20 30];

x + y

Without broadcasting, x + y would be an error because the dimensions do not agree. However, with broadcasting it is as if the following operation were performed:

x = [1 2 3
     4 5 6
     7 8 9];

y = [10 20 30
     10 20 30
     10 20 30];

x + y
⇒    11   22   33
      14   25   36
      17   28   39

That is, the smaller array of size [1 3] gets copied along the singleton dimension (the number of rows) until it is [3 3]. No actual copying takes place, however. The internal implementation reuses elements along the necessary dimension in order to achieve the desired effect without copying in memory.

Both arrays can be broadcast across each other, for example, all pairwise differences of the elements of a vector with itself:

y - y'
⇒    0   10   20
    -10    0   10
    -20  -10    0

Here the vectors of size [1 3] and [3 1] both get broadcast into matrices of size [3 3] before ordinary matrix subtraction takes place.

A special case of broadcasting that may be familiar is when all dimensions of the array being broadcast are 1, i.e., the array is a scalar. Thus for example, operations like x - 42 and max (x, 2) are basic examples of broadcasting.

For a higher-dimensional example, suppose img is an RGB image of size [m n 3] and we wish to multiply each color by a different scalar. The following code accomplishes this with broadcasting,

img .*= permute ([0.8, 0.9, 1.2], [1, 3, 2]);

Note the usage of permute to match the dimensions of the [0.8, 0.9, 1.2] vector with img.

For functions that are not written with broadcasting semantics, bsxfun can be useful for coercing them to broadcast.

: bsxfun (f, A, B)

Apply a binary function f element-by-element to two array arguments A and B, expanding singleton dimensions in either input argument as necessary.

f is a function handle, inline function, or string containing the name of the function to evaluate. The function f must be capable of accepting two column-vector arguments of equal length, or one column vector argument and a scalar.

The dimensions of A and B must be equal or singleton. The singleton dimensions of the arrays will be expanded to the same dimensionality as the other array.

See also: arrayfun, cellfun.

Broadcasting is only applied if either of the two broadcasting conditions hold. As usual, however, broadcasting does not apply when two dimensions differ and neither is 1:

x = [1 2 3
     4 5 6];
y = [10 20
     30 40];
x + y

This will produce an error about nonconformant arguments.

Besides common arithmetic operations, several functions of two arguments also broadcast. The full list of functions and operators that broadcast is

      plus      +
      minus     -
      times     .*
      rdivide   ./
      ldivide   .\
      power     .^
      lt        <
      le        <=
      eq        ==
      gt        >
      ge        >=
      ne        !=  ~=
      and       &
      or        |
      atan2
      hypot
      max
      min
      mod
      rem
      xor

      +=  -=  .*=  ./=  .\=  .^=  &=  |=

Here is a real example of the power of broadcasting. The Floyd-Warshall algorithm is used to calculate the shortest path lengths between every pair of vertices in a graph. A naive implementation for a graph adjacency matrix of order n might look like this:

for k = 1:n
  for i = 1:n
    for j = 1:n
      dist(i,j) = min (dist(i,j), dist(i,k) + dist(k,j));
    endfor
  endfor
endfor

Upon vectorizing the innermost loop, it might look like this:

for k = 1:n
  for i = 1:n
    dist(i,:) = min (dist(i,:), dist(i,k) + dist(k,:));
  endfor
endfor

Using broadcasting in both directions, it looks like this:

for k = 1:n
  dist = min (dist, dist(:,k) + dist(k,:));
endfor

The relative time performance of the three techniques for a given graph with 100 vertices is 7.3 seconds for the naive code, 87 milliseconds for the singly vectorized code, and 1.3 milliseconds for the fully broadcast code. For a graph with 1000 vertices, vectorization takes 11.7 seconds while broadcasting takes only 1.15 seconds. Therefore in general it is worth writing code with broadcasting semantics for performance.

However, beware of resorting to broadcasting if a simpler operation will suffice. For matrices a and b, consider the following:

c = sum (permute (a, [1, 3, 2]) .* permute (b, [3, 2, 1]), 3);

This operation broadcasts the two matrices with permuted dimensions across each other during elementwise multiplication in order to obtain a larger 3-D array, and this array is then summed along the third dimension. A moment of thought will prove that this operation is simply the much faster ordinary matrix multiplication, c = a*b;.

A note on terminology: “broadcasting” is the term popularized by the Numpy numerical environment in the Python programming language. In other programming languages and environments, broadcasting may also be known as binary singleton expansion (BSX, in MATLAB, and the origin of the name of the bsxfun function), recycling (R programming language), single-instruction multiple data (SIMD), or replication.

19.2.1 Broadcasting and Legacy Code

The new broadcasting semantics almost never affect code that worked in previous versions of Octave. Consequently, all code inherited from MATLAB that worked in previous versions of Octave should still work without change in Octave. The only exception is code such as

try
  c = a.*b;
catch
  c = a.*a;
end_try_catch

that may have relied on matrices of different size producing an error. Because such operation is now valid Octave syntax, this will no longer produce an error. Instead, the following code should be used:

if (isequal (size (a), size (b)))
  c = a .* b;
else
  c = a .* a;
endif

Next: Function Application, Previous: Basic Vectorization, Up: Vectorization and Faster Code Execution   [Contents][Index]