% Options for packages loaded elsewhere
\PassOptionsToPackage{unicode}{hyperref}
\PassOptionsToPackage{hyphens}{url}
%
\documentclass[
]{article}
\usepackage{amsmath,amssymb}
\usepackage{iftex}
\ifPDFTeX
  \usepackage[T1]{fontenc}
  \usepackage[utf8]{inputenc}
  \usepackage{textcomp} % provide euro and other symbols
\else % if luatex or xetex
  \usepackage{unicode-math} % this also loads fontspec
  \defaultfontfeatures{Scale=MatchLowercase}
  \defaultfontfeatures[\rmfamily]{Ligatures=TeX,Scale=1}
\fi
\usepackage{lmodern}
\ifPDFTeX\else
  % xetex/luatex font selection
\fi
% Use upquote if available, for straight quotes in verbatim environments
\IfFileExists{upquote.sty}{\usepackage{upquote}}{}
\IfFileExists{microtype.sty}{% use microtype if available
  \usepackage[]{microtype}
  \UseMicrotypeSet[protrusion]{basicmath} % disable protrusion for tt fonts
}{}
\makeatletter
\@ifundefined{KOMAClassName}{% if non-KOMA class
  \IfFileExists{parskip.sty}{%
    \usepackage{parskip}
  }{% else
    \setlength{\parindent}{0pt}
    \setlength{\parskip}{6pt plus 2pt minus 1pt}}
}{% if KOMA class
  \KOMAoptions{parskip=half}}
\makeatother
\usepackage{xcolor}
\usepackage{color}
\usepackage{fancyvrb}
\newcommand{\VerbBar}{|}
\newcommand{\VERB}{\Verb[commandchars=\\\{\}]}
\DefineVerbatimEnvironment{Highlighting}{Verbatim}{commandchars=\\\{\}}
% Add ',fontsize=\small' for more characters per line
\newenvironment{Shaded}{}{}
\newcommand{\AlertTok}[1]{\textcolor[rgb]{1.00,0.00,0.00}{\textbf{#1}}}
\newcommand{\AnnotationTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textbf{\textit{#1}}}}
\newcommand{\AttributeTok}[1]{\textcolor[rgb]{0.49,0.56,0.16}{#1}}
\newcommand{\BaseNTok}[1]{\textcolor[rgb]{0.25,0.63,0.44}{#1}}
\newcommand{\BuiltInTok}[1]{\textcolor[rgb]{0.00,0.50,0.00}{#1}}
\newcommand{\CharTok}[1]{\textcolor[rgb]{0.25,0.44,0.63}{#1}}
\newcommand{\CommentTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textit{#1}}}
\newcommand{\CommentVarTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textbf{\textit{#1}}}}
\newcommand{\ConstantTok}[1]{\textcolor[rgb]{0.53,0.00,0.00}{#1}}
\newcommand{\ControlFlowTok}[1]{\textcolor[rgb]{0.00,0.44,0.13}{\textbf{#1}}}
\newcommand{\DataTypeTok}[1]{\textcolor[rgb]{0.56,0.13,0.00}{#1}}
\newcommand{\DecValTok}[1]{\textcolor[rgb]{0.25,0.63,0.44}{#1}}
\newcommand{\DocumentationTok}[1]{\textcolor[rgb]{0.73,0.13,0.13}{\textit{#1}}}
\newcommand{\ErrorTok}[1]{\textcolor[rgb]{1.00,0.00,0.00}{\textbf{#1}}}
\newcommand{\ExtensionTok}[1]{#1}
\newcommand{\FloatTok}[1]{\textcolor[rgb]{0.25,0.63,0.44}{#1}}
\newcommand{\FunctionTok}[1]{\textcolor[rgb]{0.02,0.16,0.49}{#1}}
\newcommand{\ImportTok}[1]{\textcolor[rgb]{0.00,0.50,0.00}{\textbf{#1}}}
\newcommand{\InformationTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textbf{\textit{#1}}}}
\newcommand{\KeywordTok}[1]{\textcolor[rgb]{0.00,0.44,0.13}{\textbf{#1}}}
\newcommand{\NormalTok}[1]{#1}
\newcommand{\OperatorTok}[1]{\textcolor[rgb]{0.40,0.40,0.40}{#1}}
\newcommand{\OtherTok}[1]{\textcolor[rgb]{0.00,0.44,0.13}{#1}}
\newcommand{\PreprocessorTok}[1]{\textcolor[rgb]{0.74,0.48,0.00}{#1}}
\newcommand{\RegionMarkerTok}[1]{#1}
\newcommand{\SpecialCharTok}[1]{\textcolor[rgb]{0.25,0.44,0.63}{#1}}
\newcommand{\SpecialStringTok}[1]{\textcolor[rgb]{0.73,0.40,0.53}{#1}}
\newcommand{\StringTok}[1]{\textcolor[rgb]{0.25,0.44,0.63}{#1}}
\newcommand{\VariableTok}[1]{\textcolor[rgb]{0.10,0.09,0.49}{#1}}
\newcommand{\VerbatimStringTok}[1]{\textcolor[rgb]{0.25,0.44,0.63}{#1}}
\newcommand{\WarningTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textbf{\textit{#1}}}}
\usepackage{longtable,booktabs,array}
\usepackage{calc} % for calculating minipage widths
% Correct order of tables after \paragraph or \subparagraph
\usepackage{etoolbox}
\makeatletter
\patchcmd\longtable{\par}{\if@noskipsec\mbox{}\fi\par}{}{}
\makeatother
% Allow footnotes in longtable head/foot
\IfFileExists{footnotehyper.sty}{\usepackage{footnotehyper}}{\usepackage{footnote}}
\makesavenoteenv{longtable}
\setlength{\emergencystretch}{3em} % prevent overfull lines
\providecommand{\tightlist}{%
  \setlength{\itemsep}{0pt}\setlength{\parskip}{0pt}}
\setcounter{secnumdepth}{-\maxdimen} % remove section numbering
\ifLuaTeX
  \usepackage{selnolig}  % disable illegal ligatures
\fi
\IfFileExists{bookmark.sty}{\usepackage{bookmark}}{\usepackage{hyperref}}
\IfFileExists{xurl.sty}{\usepackage{xurl}}{} % add URL line breaks if available
\urlstyle{same}
\hypersetup{
  pdftitle={asg1},
  hidelinks,
  pdfcreator={LaTeX via pandoc}}

\title{DM587\\Obligatory Assignment: VecMat}
\author{}


\begin{document}
\maketitle

%\hypertarget{assignment-1-vector-and-matrix}{%
%\subsubsection{Vectors and Matrices}\label{assignment-1-vector-and-matrix}}

\textbf{Submission Deadline: Friday, September 27 2024, at noon}

In this assignment you are asked to implement your own Vector and Matrix
types in Python and to compare them with Numpy array type
implementations.

In your git repository you will find a new directory \texttt{asg-vecmat}
with the following specifications files that you will need to edit:
\texttt{vec.py} and \texttt{mat.py}. In addition, you will find the file
\texttt{banchmark.py} that will use your implementations to carry out
the comparison with NumPy implementations. The files
\texttt{vec-sparse.py} and \texttt{mat-sparse.py} are for an optional
part of the assignment.

Your job is to implement the appropriate methods for the classes
\texttt{Vec} and \texttt{Mat} such that the functions in the doctest
examples and those in \texttt{benchmark.py}, that use the operators with
objects from the \texttt{Vec} and \texttt{Mat} classes, work correctly.
To facilitate your task the procedures that you have to finish
implementing have been moved out of the class where they are called.
Hence you should make no changes to the class definition. Your code for
a procedure can include calls to other procedures that you have
implemented.

The table below resumes the functions that are used for the different
operators:

\begin{longtable}[]{@{}lcr@{}}
\toprule\noalign{}
operation & syntax & function \\
\midrule\noalign{}
\endhead
\bottomrule\noalign{}
\endlastfoot
vector addition & u+v & \texttt{\_\_add\_\_} \\
vector negation & -v & \texttt{\_\_neg\_\_} \\
vector subtraction & u-v & \\
scalar-vector multiplication & alpha*v & \texttt{\_\_rmult\_\_} \\
division of a vector by a scalar & v/alpha & \texttt{\_\_truediv\_\_} \\
dot-product & u*v & \texttt{\_\_mult\_\_} \\
getting value of an entry & v{[}d{]} & \texttt{\_\_getitem\_\_} \\
setting value of an entry & v{[}d{]} = . & \texttt{\_\_setitem\_\_} \\
testing vector equality & u == v & \texttt{\_\_eq\_\_} \\
pretty-printing a vector & print(v) & \texttt{\_\_str\_\_} \\
copying a vector & v.copy() & \texttt{copy} \\
\end{longtable}

You can test if your modules pass all their \texttt{doctests} from a
console, by typing

\begin{Shaded}
\begin{Highlighting}[]
\ExtensionTok{python3} \AttributeTok{{-}m}\NormalTok{ doctest vec.py}
\end{Highlighting}
\end{Shaded}

or

\begin{Shaded}
\begin{Highlighting}[]
\ExtensionTok{python3}\NormalTok{ vec.py}
\end{Highlighting}
\end{Shaded}

To benchmark your implementations against those from Numpy you can call:

\begin{Shaded}
\begin{Highlighting}[]
\ExtensionTok{python3}\NormalTok{ benchmark.py}
\end{Highlighting}
\end{Shaded}

You can vary the size of the matrices to observe the growing rate of
computation time but you should otherwise not edit file
\texttt{benchmark.py}.

Your code will be tested and graded on a different test set than the one
in the docstring of the files provided.

\emph{Assertions}: For most of the procedures to be written, the first
statement after the docstring is an assertion. Executing an assertion
verifies that the condition is true, and raises an error if not. The
assertions are there to detect errors in the use of the procedures. Take
a look at the assertions to make sure you understand them. You can take
them out, but you do so at your own risk. If you complie your script
with the flag \texttt{-O} assertion statements are ignored.

\hypertarget{sparse-vectors-and-matrices-optional}{%
\paragraph{Sparse Vectors and Matrices
(Optional)}\label{sparse-vectors-and-matrices-optional}}

This part is associated with the files \texttt{vec\_sparse.py} and
\texttt{mat\_sparse.py}.

A vector (matrix) most of whose values are zeros is called \emph{sparse
vector (matrix)}.

\emph{Sparse representation}: To represent sparse vectors and matrices
in Euclidean spaces, it might be useful to regard them as functions from
a domain \(D\) to a co-domain \(\mathbb{R}\). For example the vector \$
{[}3.14159, 2.718281828, -1.0, 2.0{]} \$ can be represented as the
function:

\[
\begin{array}{lcl}
0 &\mapsto & 3.14159\\
1 &\mapsto & 2.718281828\\
2 &\mapsto & -1.0\\
3 &\mapsto & 2.0
\end{array}
\]

For a matrix the domain \(D\) is made by the product of a domain \(R\)
for the rows and a domain \(C\) for the columns. For example, the
identity matrix of size \(3\times 3\) can be seen as the function that
maps the pairs \((r,c)\in R\times C\) where \(R=C=\\{1,2,3\\}\).

\[
\begin{array}{lcl}
(0,0) &\mapsto & 1\\
(1,1) &\mapsto & 1\\
(2,2) &\mapsto & 1
\end{array}
\]

All other elements of the domain \(R\times C\) are mapped to zero and do
not need to be explicitly stated.

Functions like these can be represented in Python by dictionaries, where
the keys are elements from the set \(D\) or tuples from the set
\(R\times C\) and values are the corresponding values from
\(\mathbb{R}\).

Sparse vectors and matrices are implemented in Python in the module
\texttt{scipy}, which contains the numerical code for operations on
arrays (see
\href{https://www.scipy.org/scipylib/faq.html\#what-is-the-difference-between-numpy-and-scipy}{difference
between numpy and scipy}. Here you find a
\href{https://imada.sdu.dk/u/marco/DM559/Resources/Ipython/Sparse.html}{short
introduction to sparse matrices in \texttt{scipy}}.

Your task is to implement in \texttt{vec\_sparse.py} and
\texttt{mat\_sparse.py} methods that can cope with sparse
representations, For example, \texttt{getitem(v,\ k)} should return a
value from the vector function \texttt{v.f} for every domain element
\texttt{k} even if \texttt{k} is not a key of \texttt{v.f}.

However, your methods do not need to make any effort to retain sparsity
when adding two vectors. That is, for two instances \texttt{u} and
\texttt{v} of \texttt{Vec}, it is okay if every element of \texttt{u.D}
is represented explicitly in the dictionary of the instance
\texttt{u+v}. Several other procedures need to be written with the
sparsity convention in mind. For example, two vectors can be equal even
if their \texttt{.f} fields are not equal: one vector's \texttt{.f}
field can contain a key-value pair in which the value is zero, and the
other vector's \texttt{.f} field can omit this particular key. For this
reason, the \texttt{equal(u,\ v)} procedure needs to be written with
care.

\end{document}