DM561 - Linear Algebra with Applications

Assignment 1: Vector and Matrix

Submission Deadline: Friday, November 23 2018, 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 the following spec files that you will need to edit vec.py and mat.py. In addition, you will find the file banchmark.py that will use your implementations to carry out the comparison with NumPy.

The files vec-sparse.py and mat-sparse.py are for an optional part of the assignment. For implementing the methods in these files you will get help by the instructors in Computer Lab class of week 47.

Your job is to implement the appropriate methods for the classes Vec and Mat such that the functions in the doctest examples and those in benchmark.py that use the operators with objects from those 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.

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

operation syntax function
vector addition u+v __add__
vector negation -v __neg__
vector subtraction u-v  
scalar-vector multiplication alpha*v __rmult__
division of a vector by a scalar v/alpha __truediv__
dot-product u*v __mult__
getting value of an entry v[d] __getitem__
setting value of an entry v[d] = . __setitem__
testing vector equality u == v __eq__
pretty-printing a vector print(v) __str__
copying a vector v.copy() copy

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

python3 -m doctest vec.py

or

python3 vec.py

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

python3 benchmark.py

You can play around with the size of the matrices to observe the growing rate of computation time but you should otherwise not edit this file. This file will be updated when we deal with the sparse matrix part.

Your code will be graded on another set of tests that will be unveiled during grading.

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.

Sparse Vectors and Matrices (Optional)

This part will be discussed in class in one of the Computer Lab. It is associated with the files vec_sparse.py and mat_sparse.py.

A vector (matrix) most of whose values are zeros is called a sparse vector (matrix).

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{B}$. For example the vector $ [3.14159, 2.718281828, −1.0, 2.0] $ can be represented as the function:

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\}$.

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 scipy, which contains the numerical code for operations on arrays. Here you find a short introduction to sparse matrices in scipy.

Your procedures should be able to cope with sparse representation, For example, getitem(v, k) should return a value for every domain element even if k is not a key of v.f.

However, your procedures need not make any effort to retain sparsity when adding two vectors. That is, for two instances u and v of Vec, it is okay if every element of u.D is represented explicitly in the dictionary of the instance 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 .f fields are not equal: one vector’s .f field can contain a key-value pair in which the value is zero, and the other vector’s .f field can omit this particular key. For this reason, the equal(u, v) procedure needs to be written with care.