Vectorization #1: the difficulty of notation, part 1

In this series of posts, I will try looking at different aspects of vectorization. We will start today with a scalar/vector/matrix notations, and try explaining what are the benefits and complications related to using such notations. I won’t be talking much about the performance or programming in the strict sense, but I will rather try explaining what is the problem in finding a fair notation. The mathematics presented here are simplified so that non-mathematicians could also follow the thought process without (too) much effort. Although the knowledge about real vector/matrix algebra might be of some use.

Vectorizing scalar equations

The vector term originates from mathematics. Say you have a group of equations, like:

$a_1 = b_1 + c_1 \cdot d_1$
$a_2 = b_2 + c_2 \cdot d_2$
$...$
$a_N = b_N + c_N \cdot d_N$

All of the variables: $a_1, b_1, c_1, d_1, a_2, b_2, c_2, d_2 ..., a_N, b_N, c_N, d_N$ are used in the equation of the same exact form:

$\alpha = \beta + \gamma \cdot \delta$

In order to simplify the first notation, you can first group the variables at the same position in equations in a following way, forming vectors:

$\textbf{a} = (a_1, a_2, ..., a_N)$
$\textbf{b} = (b_1, b_2, ..., b_N)$
$\textbf{c} = (c_1, c_2, ..., c_N)$
$\textbf{d} = (d_1, d_2, ..., d_N)$

Now you can replace the original set of equations with a vector form (a cautious mathematician can now point that ‘ $\cdot$ ‘ is not a correct vector operation symbol here, and that we should use $\circ$ instead. This is a part of the thought experiment. Please bear with me in this insanity for a while.):

$\textbf{a} = \textbf{b} + \textbf{c} \cdot \textbf{d}$

An entity representing a singular value, such as $a_1$ is called a scalar. A list (or more precisely ‘an ordered-set’) of elements, such as $\textbf{a}$ is called a vector.

By vectorizing our equations, we replaced an unknown number of equations ( $N$ ) of known number of variables ( $a_1, b_1, c_1, d_1$ ), with a known number of equations (1), and unknown number of packed variables( $a_1, ..., a_N, ... , b_N, ..., c_N, ..., d_N$ ).

The obvious gain we will get from having vector notation is the simplification of mathematical proofs. Instead of repeating each time that a certain property applies to equations for $a_1, a_2, ..., a_N$ we can simply state that the property applies to all elements of $\textbf{a}$ . We still have more complicated definition of the types we manipulate, but we usually have to deal with that only in the beginning and possibly at the end of a proof.

Now imagine following set of equations:

$a_{11} = 3 \cdot b_{11} + 4 \cdot c_{11} + 5 \cdot d_{11}$
$a_{12} = 3 \cdot b_{12} + 4 \cdot c_{12} + 5 \cdot d_{12}$
$...$
$a_{1M} = 3 \cdot b_{1M} + 4 \cdot b_{1M} + 5 \cdot d_{1M}$
$a_{21} = 1 \cdot b_{21} + 5 \cdot c_{21} + 4 \cdot d_{21}$
$a_{22} = 1 \cdot b_{22} + 5 \cdot c_{22} + 4 \cdot d_{22}$
$...$
$a_{2M} = 1 \cdot b_{2M} + 5 \cdot c_{2M} + 4 \cdot d_{2M}$
$...$
$a_{N1} = 7 \cdot b_{N1} + 3 \cdot c_{N1} + 9 \cdot d_{N2}$
$a_{N2} = 7 \cdot b_{N2} + 3 \cdot c_{N2} + 9 \cdot d_{N2}$
$...$
$a_{NM} = 7 \cdot b_{NM} + 3 \cdot c_{NM} + 9 \cdot d_{NM}$

If we apply our vector notation then we have:

$\textbf{a}_1 = (a_{11}, a_{12}, ..., a_{1M})$
$\textbf{a}_2 = (a_{21}, a_{22}, ..., a_{2M})$
…
$\textbf{a}_N = (a_{N1}, a_{N2}, ..., a_{NM})$

$\textbf{b}_1 = (b_{11}, b_{12}, ..., b_{1M})$
$\textbf{b}_2 = (b_{21}, b_{22}, ..., b_{2M})$
…
$\textbf{b}_N = (b_{N1}, b_{N2}, ..., b_{NM})$

$\textbf{c}_1 = (c_{11}, c_{12}, ..., c_{1M})$
$\textbf{c}_2 = (c_{21}, c_{22}, ..., c_{2M})$
…
$\textbf{c}_N = (c_{N1}, c_{N2}, ..., c_{NM})$

$\textbf{d}_1 = (d_{11}, d_{12}, ..., d_{1M})$
$\textbf{d}_2 = (d_{21}, d_{22}, ..., d_{2M})$
…
$\textbf{d}_N = (d_{N1}, d_{N2}, ..., d_{NM})$

And the re-written equations:

$\textbf{a}_1 = 3 \cdot \textbf{b}_1 + 4 \cdot \textbf{c}_1 + 5 \cdot \textbf{d}_1$
$\textbf{a}_2 = 1 \cdot \textbf{b}_2 + 5 \cdot \textbf{c}_2 + 4 \cdot \textbf{d}_2$
…
$\textbf{a}_N = 7 \cdot \textbf{b}_N + 3 \cdot \textbf{c}_N + 9 \cdot \textbf{d}_N$

So we replaced a long set of equations, with a shorter set of equations. But again if we start performing proofs on such equations, we would end up repeating everything as in the first example.

We can also think about another way of representing the same set of equations. Instead of grouping all $a$ ‘s and all $b$ ‘s together, we could use following grouping:

$\textbf{p}_1 = (3, 4, 5)$
$\textbf{p}_2 = (1, 5, 4)$
$...$
$\textbf{p}_N = (7, 3, 9)$

$\textbf{q}_{11} = (b_{11}, c_{11}, d_{11})$
$\textbf{q}_{12} = (b_{12}, c_{12}, d_{12})$
$...$
$\textbf{q}_{NM} = (b_{NM}, c_{NM}, d_{NM})$

Our second vector form becomes then:

$a_{11} = \textbf{p}_1 \cdot \textbf{q}_{11}$
$a_{12} = \textbf{p}_1 \cdot \textbf{q}_{12}$
$...$
$a_{1M} = \textbf{p}_1 \cdot \textbf{q}_{1M}$
$a_{21} = \textbf{p}_2 \cdot \textbf{q}_{21}$
$a_{22} = \textbf{p}_2 \cdot \textbf{q}_{22}$
$...$
$a_{2M} = \textbf{p}_2 \cdot \textbf{q}_{2M}$
$...$
$a_{N1} = \textbf{p}_N \cdot \textbf{q}_{N1}$
$a_{N2} = \textbf{p}_N \cdot \textbf{q}_{N2}$
$...$
$a_{NM} = \textbf{p}_N \cdot \textbf{q}_{NM}$

While in this case we didn’t decrease the number of equations, we made each of them much simpler. As for the previous transformation, we could vectorize again and get yet simpler notation for the set of our equations. We will do that in a moment. But first we need to clarify something about ‘ $\cdot$ ‘ symbol we’ve been using carelessly so far.

The continuation in: Vectorization #1: the difficulty of notation, part 2

Gain Performance

Vectorization #1: the difficulty of notation, part 1

Vectorizing scalar equations

Leave a Reply Cancel reply

Tips and tutorials on code optimization for performance

Vectorizing scalar equations

Share this:

Like this:

Related

Leave a Reply Cancel reply

Tips and tutorials on code optimization for performance