Programming project 7

Download the archive pp7.zip. It contains all the files for this project.

In numerical analysis, one often deals with large matrices that are very sparse: most entries are zero. For instance, you might have a matrix of size 10,000x10,000, but only 30,000 entries are non-zero.

If would be foolish to implement such a matrix using an array of 100,000,000 Doubles. In this task we implement a better data structure for doing this. The data structure consists of a singly-linked list for every row and for every column of the matrix, storing only the entries that are not zero. However, the same node object is used in both lists: For instance, the matrix

would be represented by the following data structure: The module matrix.py implements such a sparse matrix as the class Matrix. The constructor makes an all-zero matrix of the given dimensions. Note how it creates the lists prow and pcol: They will link to the first node in each row and column (but for the all-zero matrix there are no nodes).

There is a function identity(n) that creates an \(n \times n\) identity matrix.

The given implementation already has the code for string conversion, to retrieve the value of an entry (one can simply write M[i,j]), and to compare two matrices.

Your task is to finish the implementation of several additional methods, see below.

If you run the file matrix.py, it performs a few matrix operations that use all the methods of the Matrix class. For further testing, use the unit tests in test_matrix.py.

Setting matrix entries

Clients can set matrix entries by simply writing M[i,j] = value. This syntax calls the method M.__setitem__((i, j), value).

Note that setting an entry that already has a node in the data structure is already implemented, your task is to allow setting of new entries (this is done in the method _insertnode).

When an entry is set to zero, the node must be removed (this is done in the method _removenode).

Matrix arithmetic

We implement matrix addition, multiplication with a vector, and transposing matrices. All these operations do not modify the matrix: instead, they return a new matrix with the result.

We will be careful with the running times of our methods. All operations should run in time linear in the total number of entries of the matrices involved. (We assume that the number of entries is at least the number of rows and the number of columns.)

The operations are:

• M * v: Multiplying a matrix M with a vector v (a vector is simply a list of float objects). This is the __mul__ method.
• v * M: Multiplying a matrix M from the left with a vector v. This is the __rmul__ method. Note that the result of M * v and v * M is generally not the same, we have v * M == M.transposed() * v.
• M1 + M1: Adding two matrices M1 and M2. This is the method __add__.
• M.transposed() returns the transpose of the matrix.

Submission: Upload your file matrix.py to the submission server.