exercise6.tex

\documentclass[11pt]{article}

\include{packages}


\begin{document}

% ========== Edit your name here
%\author{Your Name}
\title{\coursename~Quiz 6: Due by \DueDate{\coursedate}{44}}
\date{}
\maketitle

\medskip

% ========== Begin answering questions here

\section*{Exercises}

\begin{enumerate}
\item Programming on paper (2 credits): \\
Write a program that squares all elements $(a_i \cdot a_i)$ in a \lstinline|std::vector<double> a| and compute the sum of all elements using \lstinline|std::for_each| and \lstinline|std::execution::par|.


\item Understanding code (2 credits): \\
What does this program do?
\begin{lstlisting}
#include <iostream>
#include <vector>
#include <numeric>
#include <future>

using namespace std;

int func1(vector<int> values){
    
    
    return accumulate(values.begin(),values.end(),0);
    
    
}

int main()
{
    std::vector<int> values = {1,2,3,4,5,6,7,8,9,10};
    
    auto f1 = std::async(func1,values);
    
    auto f2 = std::async([](const vector<int> values )
          {return std::inner_product(values.begin(), values.end(), values.begin(), 0);}
          ,values);
    
    
    cout << f1.get() + f2.get() << std::endl;

    return 0;
}
\end{lstlisting}


\end{enumerate}

\section*{Programming exercise}

\begin{enumerate}

\item Communication matrix: (2 credits)\\
Use the following matrix as the network of people
\begin{center}
$
\mathbf{M} = \left[\begin{matrix}
1 & 1 & 1 & 1 & 1 \\
1 & 0 & 0 & 1 & 0 \\
0 & 1 & 1 & 0 & 0 \\
1 & 1 & 1 & 1 & 1 \\
0 & 0 & 1 & 1 & 0
\end{matrix}\right]
$
\end{center}
and compute $\mathbf{M}^4$, where $\mathbf{M}^4= \mathbf{M}*\mathbf{M}*\mathbf{M}*\mathbf{M}$ and print the resulting matrix to the terminal or in the Jyputer notebook. 

\item Conjugate gradient method (4 credits)\\
To solve a equation system $\mathbf{A}\mathbf{x}=\mathbf{b}$, we can use the conjugate gradient methods (CG) by using following algorithm
\begin{enumerate}
\item $\mathbf{r_0} = \mathbf{b} - \mathbf{A} \mathbf{x}_0$
\item If $\vert \mathbf{r}_0 \vert< \epsilon$ return  $\mathbf{x}_0$
\item $\mathbf{p}_0=\mathbf{r}_0$
\item $k=0$
\item $\alpha_k = \frac{\mathbf{r}_k^T\mathbf{r}_k}{\mathbf{p}_k^T\mathbf{A}\mathbf{p}_k}$
\item $ \mathbf{x}_{k+1} = \mathbf{x}_k + \alpha_k \mathbf{p}_k$
\item $ \mathbf{r}_{k+1} = \mathbf{r}_k - \alpha_k \mathbf{A} \mathbf{p}_k$
\item If $\vert \mathbf{r}_{k+1} \vert < \epsilon$ exit loop
\item $\beta_k = \frac{\mathbf{r}_{k+1}^T\mathbf{r}_{k+1}}{\mathbf{r}_k^T\mathbf{r}_k}$
\item $\mathbf{p}_{k+1}=\mathbf{r}_{k+1} + \beta_k \mathbf{p}_k$
\item $k=k+1$
\item go to (e)
return $\mathbf{x}_{k+1}$
\end{enumerate}
Implement the conjugate gradient algorithm using the Blaze library\footnote{\url{https://bitbucket.org/blaze-lib/blaze/wiki/Home}}. Note that the Blaze library is installed on the course's server \lstinline|#include <blaze/Math.h>| and I recommend to use the server or Jupyter notebooks for this exercise.

\textbf{Hints:}
\begin{itemize}
\item Note that $\mathbf{x}_0$ can be chosen, if we know some assumption of the solution or set to zero.
\item The symbol $\mathbf{v}^T$ denotes the transpose\footnote{\url{https://bitbucket.org/blaze-lib/blaze/wiki/Vector\%20Operations\#!trans}} of the vector $\mathbf{v}$.
\item  The symbol $\vert \mathbf{v} \vert$ denotes the norm\footnote{\url{https://bitbucket.org/blaze-lib/blaze/wiki/Vector\%20Operations\#!norms}} of a vector $\mathbf{v}$.
\item Before you start coding, please read Blaze's documentation\footnote{\url{https://bitbucket.org/blaze-lib/blaze/wiki/Home}} first. You will find plenty of functions there, \emph{e.g.}\ printing a matrix to the terminal, and will have less work to implement.
\end{itemize}

\textbf{Validation}
This code produces a matrix $\mathbf{A}$ and a vector $\mathbf{b}$, such that the vector $\mathbf{x}$ is the solution for  $\mathbf{A} \mathbf{x} = \mathbf{b}$
\begin{lstlisting}
 for(int i=0; i<N; ++i) {
        A(i,i) = 2.0;
        b[i] = 1.0*(1+i);
        x[i] = 0.5*(i+1);
 }
\end{lstlisting}
You can use the matrix $\mathbf{A}$ and the vector $\mathbf{b}$ as the input of your CG implementation and compare your solution with the vector $\mathbf{x}$ to validate your code. You should not use this vector as the input of the CG algorithm, since your code might stop at step (2) already.


% ========== Continue adding items as needed

\end{enumerate}
\doclicenseThis 

\end{document}
\grid
\grid