Skip to content

To-do 25

What should you prepare before the session?

Practice your skills by reviewing the previous sessions

Topic 2 (Go language) and Topic 3 (PyTorch and neural networks).

Practice solving problems using Go

Parallel matrix-vector multiplication

Matrix-vector multiplication \(y = Ax\), where \(A\) is an \(n \times n\) matrix and \(x\) is a vector of length \(n\), is the fundamental kernel of virtually every iterative solver in scientific computing. Each output element is:

\[ y_i = \sum_{j=0}^{nāˆ’1} A_{i,j} x_j \quad\text{for } i = 0, 1, \ldots, nāˆ’1 \]

Implement

func ParallelMatVec(A [][]float64, x []float64, k int) []float64

partitioning rows evenly across k goroutines. Each worker writes its block of output indices into a pre-allocated result slice.

Parallel matrix-matrix multiplication

Multiply two \(n \times n\) matrices \(A\) and \(B\). Partition the output rows across goroutines ā€” each goroutine computes a contiguous block of rows of the result matrix \(C\). Workers write to non-overlapping regions of a pre-allocated result slice.

Implement

func ParallelMatMul(A, B [][]float64, k int) [][]float64

partitioning rows evenly across k goroutines. Each worker writes its block of output indices into a pre-allocated result slice.

Discuss: What happens when k > runtime.NumCPU()? What is the Amdahl's law prediction for this problem?

Automatic differentiation: Trigonometric and polynomial

Consider the scalar function

\[ f(x_1,x_2)=\sin(x_1x_2)+x_1^2. \]

Let the input nodes be \(v_1=x_1\) and \(v_2=x_2\). All other nodes should be defined as intermediate quantities in a computational graph.

a. Draw a computational graph for \(f\). Label each node \(v_i\), state its value in terms of earlier nodes, and identify the elementary operation that produces it.

b. Perform forward-mode automatic differentiation at

\[ (x_1,x_2)=(1,\pi) \]

using the input tangent seed

\[ (\dot v_1,\dot v_2)=(1,0). \]

Tabulate, for every node \(v_i\), both the primal value \(v_i\) and the tangent value \(\dot v_i\). State which partial derivative this computes.

c. Perform reverse-mode automatic differentiation at the same point using the output adjoint seed

\[ \bar f = 1. \]

Tabulate the primal values from the forward sweep and the adjoints \(\bar v_i\) from the reverse sweep. State the resulting gradient \(\nabla f(1,\pi)\).

Example solution: Trigonometric and polynomial

Part a. Computational graph. We introduce the following nodes:

\[ \begin{aligned} v_1 &= x_1 \\ v_2 &= x_2 \\ v_3 &= v_1 v_2 \\ v_4 &= \sin(v_3) \\ v_5 &= v_1^2 \\ f = v_6 &= v_4 + v_5 \end{aligned} \]

Part b. Forward-mode AD. \((x_1, x_2) = (1, \pi)\), seed \((\dot v_1, \dot v_2) = (1, 0)\). The forward sweep propagates primals and tangents simultaneously. The tangent rule for each node follows from the chain rule applied to that elementary operation.

Propagating primal values \(v_i\):

\[ \begin{aligned} v_1 &= x_1 = 1 \\ v_2 &= x_2 = \pi \\ v_3 &= \pi \\ v_4 &= \sin(\pi) = 0 \\ v_5 &= 1 \\ f = v_6 &= 1 \end{aligned} \]

Forward-propagating tanget values \(\dot v_i\):

\[ \begin{aligned} \dot v_1 &= 1 \\ \dot v_2 &= 0 \\ \dot v_3 &= \frac{\partial v_3}{\partial v_1} \dot v_1 + \frac{\partial v_3}{\partial v_2} \dot v_2 = v_2 \dot v_1 + v_1 \dot v_2 = \pi \cdot 1 + 1 \cdot 0 = \pi \\ \dot v_4 &= \frac{\partial v_4}{\partial v_3} \dot v_3 = \cos(v_3) \dot v_3 = \cos(\pi)\cdot\pi = -\pi \\ \dot v_5 &= \frac{\partial v_5}{\partial v_1} \dot v_1 = 2 v_1 \dot v_1 = 2\cdot 1\cdot 1 = 2 \\ \dot v_6 &= \frac{\partial v_6}{\partial v_4} \dot v_4 + \frac{\partial v_6}{\partial v_5} \dot v_5 = \dot v_4 + \dot v_5 = -\pi + 2 = 2-\pi \end{aligned} \]

One forward pass with this seed computes

\[ \Rightarrow \dot v_6 = \nabla f(1,\pi) \cdot (1,0)^\top = \frac{\partial f}{\partial x_1} = 2-\pi. \]

Part c. Reverse-mode AD. \((x_1, x_2) = (1, \pi)\), seed \(\bar f = 1\). The adjoint \(\bar v_i = \frac{\partial f}{\partial v_i}\) is accumulated by traversing the graph backwards, distributing the adjoint through each local partial derivative.

Propagating primal values \(v_i\) is the same as in part (b).

Reverse-propagating adjoint values \(\bar v_i\):

\[ \begin{aligned} \bar v_6 &= \bar f = 1 \\ \bar v_5 &= \bar v_6 \frac{\partial v_6}{\partial v_5} = \bar v_6 \cdot 1 = 1 \cdot 1 = 1 \\ \bar v_4 &= \bar v_6 \frac{\partial v_6}{\partial v_4} = \bar v_6 \cdot 1 = 1 \cdot 1 = 1 \\ \bar v_3 &= \bar v_4 \frac{\partial v_4}{\partial v_3} = \bar v_4 \cos(v_3) = 1 \cdot \cos(\pi) = -1 \\ \bar v_2 &= \bar v_3 \frac{\partial v_3}{\partial v_2} = \bar v_3 v_1 = (-1) \cdot 1 = -1 \\ \bar v_1 &= \bar v_3 \frac{\partial v_3}{\partial v_1} + \bar v_5 \frac{\partial v_5}{\partial v_1} = \bar v_3 v_2 + \bar v_5 2v_1 = (-1) \cdot \pi + 1 \cdot 2 \cdot 1 = -\pi + 2 = 2 - \pi \end{aligned} \]

Reverse pass yields the full gradient simultaneously for the scalar-valued function

\[ \Rightarrow \nabla f(1,\pi) = \left(\frac{\partial f}{\partial x_1},\, \frac{\partial f}{\partial x_2}\right) = (2-\pi,\;-1). \]

Note that \(\bar v_1 = 2-\pi\) agrees with the forward-mode result in part (b) because the forward-mode seed was \(\dot v_1 = 1, \dot v_2 = 0\).

Automatic differentiation: Polynomial and exponential

Consider the scalar function

\[ f(x_1,x_2)=e^{x_1x_2}+x_2^3. \]

Let the input nodes be \(v_1=x_1\) and \(v_2=x_2\).

a. Draw a computational graph for \(f\). Label each node \(v_i\), state its value in terms of earlier nodes, and identify the elementary operation that produces it.

b. Perform forward-mode automatic differentiation at

\[ (x_1,x_2)=(0,2) \]

using the input tangent seed

\[ (\dot v_1,\dot v_2)=(1,0). \]

Tabulate the primal value \(v_i\) and tangent value \(\dot v_i\) at every node. State the resulting partial derivative.

c. Perform reverse-mode automatic differentiation at the same point using the output adjoint seed

\[ \bar f=1. \]

Tabulate the primal values and adjoints \(\bar v_i\). State \(\nabla f(0,2)\).

Automatic differentiation: Logarithm and product

Consider the scalar function

\[ f(x_1,x_2)=\log(x_1+x_2^2)+x_1x_2. \]

Let the input nodes be \(v_1=x_1\) and \(v_2=x_2\).

a. Draw a computational graph for \(f\). Label each node \(v_i\), state its value in terms of earlier nodes, and identify the elementary operation that produces it.

b. Perform forward-mode automatic differentiation at

\[ (x_1,x_2)=(1,2) \]

using the input tangent seed

\[ (\dot v_1,\dot v_2)=(0,1). \]

Tabulate the primal value \(v_i\) and tangent value \(\dot v_i\) at every node. State the resulting partial derivative.

c. Perform reverse-mode automatic differentiation at the same point using the output adjoint seed

\[ \bar f=1. \]

Tabulate the primal values and adjoints \(\bar v_i\). State \(\nabla f(1,2)\).

Automatic differentiation: Trigonometric composition

Consider the scalar function

\[ f(x_1,x_2)=\cos(x_1+x_2)+x_1x_2^2. \]

Let the input nodes be \(v_1=x_1\) and \(v_2=x_2\).

a. Draw a computational graph for \(f\). Label each node \(v_i\), state its value in terms of earlier nodes, and identify the elementary operation that produces it.

b. Perform forward-mode automatic differentiation at

\[ (x_1,x_2)=(0,\pi) \]

using the input tangent seed

\[ (\dot v_1,\dot v_2)=(1,0). \]

Tabulate the primal value \(v_i\) and tangent value \(\dot v_i\) at every node. State the resulting partial derivative.

c. Perform reverse-mode automatic differentiation at the same point using the output adjoint seed

\[ \bar f=1. \]

Tabulate the primal values and adjoints \(\bar v_i\). State \(\nabla f(0,\pi)\).