Assignments

The following problems are the assigment for the completion of the course (work in progess). The student must choose one, and produce a C/C++ code with a small report which describe the problem and the implementation. In alternative to the report DOXYGEN documentation is allowed.

Problem 1

Given two rectangular matrix \(\mathbf{A}\in\mathbb{R}^{n\times p}\) and \(\mathbf{B}\in\mathbb{R}^{p\times m}\) write a C or C++ code which compute the matrix \(\mathbf{C}=\mathbf{A}\mathbf{B}\in\mathbb{R}^{n\times m}\) using recursive splitting in such a way the splitted block fit in the computer cache.

Problem 2

Solve the problem 1 using thread to parallelize recursion.

Problem 3

Given a matrix \(\mathbf{A}\in\{0,1,\ldots,255\}^{n\times p}\) of values in 0..255 store the matrix in a packed way in a matrix of integer. Using this packed representation write a C or C++ code which perform the following operation

\[\begin{split}A_{i,j} \leftarrow A_{i,j} + \sum_{k=-1,0,1}\sum_{k=-1,0,1}A_{i+k,j+l} M_{k,l}, \quad \begin{cases} i=1,2,\ldots,n-2 \\ j=1,2,\ldots,p-2 \end{cases}\end{split}\]

where

\[\begin{split}\mathbf{M} = \begin{pmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \\ \end{pmatrix}\end{split}\]

Operation of sum and multiplication are performed modulo 256 i.e 13*34 = 186 and 255+1 = 0.

Problem 4

Write a class Poly which implement algebra of polinomial with values in \(\mathbb{R}\), in particular sum, multiplication and division with remainder must be in the class. Use the class to write a program which compute the the great common divisor of two polinomial, i.e. given \(p(x)\) and \(q(x)\) find \(m(x)\) such that \(m(x) \| p(x)\) and \(m(x) \| q(x)\) and if \(s(x)\) divide \(p(x)\) and \(q(x)\) then \(s(x)|m(x)\).

Problem 5

Solve the problem 4 with Galois field \(F_2=\mathbb{Z}/2\mathbb{Z}\)

Problem 6

Develop two class Vec2 and Mat2 which implement algebra of real vector and real square matrix of dimension 2. The operations for the vector class are element by element addition subtraction multiplication and division.

container:: paragraph

The operations for the matrix class are element by element addition subtraction and matrix-matrix multiplication.

container:: paragraph

Division is equivalent to left multiplication by inverse.

container:: paragraph

Write external operation which implement mixed operation of Matrix-Vector multiplication and vector-Matrix division which is the linear system solution, i.e. \(\mathbf{v}/\mathbf{A} \equiv \mathbf{A}^{-1} \mathbf{v}\).

Use this classes to solve some geometric problem in \(\mathbb{R}^2\), like

• Find the tangent points between a circle and lines passing from a fixed points

• Given two line in parametric form find the intersection point

Problem 7

Consider a lower triangular matrix \(\mathbf{L}\) an the partition

\[\begin{split}\mathbf{L} = \begin{pmatrix} \mathbf{L}_{1,1} & \mathbf{0} \\ \mathbf{L}_{2,1} & \mathbf{L}_{2,2} \end{pmatrix}\end{split}\]

The linear system \(\mathbf{L}\mathbf{x}=\mathbf{b}\) can be solved as follows

\[\begin{split}\begin{pmatrix} \mathbf{L}_{1,1} & \mathbf{0} \\ \mathbf{L}_{2,1} & \mathbf{L}_{2,2} \end{pmatrix} \begin{pmatrix} \mathbf{x}_{1} \\ \mathbf{x}_{2} \end{pmatrix} = \begin{pmatrix} \mathbf{b}_{1} \\ \mathbf{b}_{2} \end{pmatrix}, \qquad \begin{cases} \mathbf{x}_{1} = \mathbf{L}_{1,1}^{-1} \mathbf{b}_{1} \\ \mathbf{x}_{2} = \mathbf{L}_{2,2}^{-1} (\mathbf{b}_{2}-\mathbf{x}_{1}) \\ \end{cases}\end{split}\]

Use recursively this pattern to write a C or C++ routine which solve a lower triangular linear system.

Problem 8

Write a class GF3 which implement algebra of the Galois field \(F_3=\mathbb{Z}/3\mathbb{Z}\)

---