In this project, you will write two classes representing matrices of the form:

⎡  %%        %%          0       0       0 ⎤

 = % %(%)             ) and  = ⎢    &(&)              '(')        ⎥ ⎣ 0       0       0      ('        (( ⎦

 is a dense   ×  matrix which, in general, has no special structure and no zero entries.  is a tri-diagonal matrix, where all entries are zero apart from along the diagonal and upper and lower diagonals. Note that although  is only a 5 × 5 matrix, your classes should represent a general   ×  tri-diagonal matrix. Also, the tri-diagonal matrices you need to represent will always be square.

In a similar fashion to Fraction, you will then write functions to perform various matrix operations:

1.  addition and subtraction;

2.  scalar and matrix-matrix multiplication;

3.  calculating the determinant of the matrix.

Clearly calculating the determinant is the trickiest task here. Probably you will already have seen expansion by minors as a possible method. Whilst this is an excellent method for calculating determinants by hand, you should not use it for this task. The reason is that calculating the determinant of a  ×  matrix requires (!) operations, since for each  ×  matrix, we must calculate the values of the   −  1 sub-determinants. This is extremely slow.

A much better method is called LU decomposition. In this, we write a matrix  as product of two matrices  and  which are lower- and upper- triangular respectively. For example, for a 4×4 matrix, we would find matrices so that

BAAAAAAC = B $$'$        'AAAAA BAAAAAAC

)                                                                      *                                                               +

Such a factorisation is not guaranteed to exist (and indeed is not unique), but typically it does. In this project, you  don’t  really  need to  worry  about this – your  code  will  be tested  with  matrices for  which the  LU decomposition  exists.  It  is  up  to  you  to  figure  out  how  to  calculate  the  determinant  from  the  LU decomposition!

Throughout the formulation, matrices will be represented by indices running between 1  ≤   ,   ≤  ,  . However,  in  your  code,  you  should  stay  consistent  with  Java  notation  and  indices  should  start  at  0 (i.e. 0  ≤   ,   ≤    −  1,   −  1).

2          Programming Instructions

On the course web page for the project, you will find files for the following classes. As with the previous projects, the files have some predefined methods that are either complete or come with predefined names and  parameters. You  must  keep  all  names,  parameter types  and  return types  of public objects  and methods as they are in the templates. Other methods must be filled in and it is up to you to design them properly.

There are five classes in this project:

•  Matrix: a general class defining the basic properties and operations on matrices.

•  MatrixException: a subclass of the RuntimeException class which you should use to throw matrix-related exceptions. This class is complete – you do not need to alter it.

•  GeneralMatrix: a subclass of Matrix which describes a general   ×  real matrix.

•  TriMatrix: another subclass of Matrix which describes a   ×  real tri-diagonal matrix.

•  Project3: a separate class which will use Matrix and its subclasses to collect some basic statistics involving random matrices.

•  Please note that unlike other projects, you may not assume that the data you receive will be valid. Therefore, you will need to check, amongst other things, that matrix multiplications are done using matrices of valid sizes, the user is not trying to access matrix elements which are out of bounds, etc. If

something goes wrong, you are expected to throw a MatrixException.

The classes you need to work on are briefly described below.

2.1       The Matrix class

This is the base class from which you will build your specialised subclasses. Matrix is abstract – as described in the lectures, this means that some of the methods are not defined, and they need to be implemented in the subclasses. The general idea is that each subclass of Matrix can implement its own storage schemes, whilst still maintaining various common methods inherent in all matrices.

In particular, the following functions are not abstract, and need to be filled in inside Matrix:

•  the protected constructor function;

•  toString, which should return a String representation of the matrix.

Additionally, the following abstract methods will be implemented by the subclasses of Matrix:

•  getIJ and setIJ: accessor and mutator methods to get/set the th entry of the matrix.

•  add: returns a new Matrix containing the sum of the current matrix with another.

•  multiply(double scaler): multiply the matrix by a constant  ∈ ℝ .

•  multiply(Matrix B): multiply the matrix by another matrix. Note that this is intended to be a left multiplication; i.e. A.multiply(B) corresponds to the multiplication  .

•  random(): fills current the matrix with random numbers, uniformly distributed between 0 and

1. For a tri-diagonal matrix, this should fill the three diagonals with random numbers.

In subclasses, you should  pay attention to what type of  matrix  needs to  be  returned from each of the functions.   For   example,   when   adding   two   GeneralMatrix objects   the   result   should   be   a GeneralMatrix (which is then typecast to a Matrix).

2.2     The GeneralMatrix class

GeneralMatrix represents a full   × n matrix and extends Matrix.

1.  The matrix will be stored in a private two-dimensional array.

2.  You should implement all the functions mentioned above using the standard formulae from linear algebra to do so, as well as the usual constructors, accessor and mutator methods.

3.  You may choose whatever method you want to calculate the determinant of the matrix. However, it is strongly   recommended   you   use   the   provided   LUdecomp function,   which   will   perform   LU decomposition for you since the algorithm is quite tricky for   ×  matrices.

To  call  LUdecomp, you  should  pass  it  a  double array  sign of  length  1.  It  will  return  a  new GeneralMatrix storing  both   =  (,- ) and   =  ( ,- ) .  For instance, when   =  5, the  matrix returned is

⎡⎢⎤⎥

⎢  $%          $&        $$        $'        $( ⎥

⎢  '%          '&          '$       ''       '( ⎥

⎣  (%          (&          ($          ('        (( ⎦

The reason we can store it in this compact form is that the algorithm insists that  ,,  = 1 for every  , and so this information can be omitted from the array.

On exit, the double inside the array you passed in will have a value of 1 or − 1. You should multiply the calculated determinant by this value so that it has the correct sign. This constant arises because the decomposition algorithm will flip rows in the matrix to aid with singular matrices, thus changing the sign of the determinant.

As a result, if you explicitly perform the multiplication LU, you probably won’t get the original matrix back again, but rather a permutation of it. For example, consider a matrix J which is a slightly altered identity matrix.

2.3       The TriMatrix class

TriMatrix represents a tri-diagonal matrix of size  ×  and extends Matrix. The constructor therefore only accepts a single parameter, dimension.

1.  Tri-diagonal matrices are never stored in full two-dimensional arrays because they are sparse – that is, most of the entries are zero. Instead, we use three arrays of double: diagonal, upperDiagonal and  lowerDiagonal.  These  store  the  diagonal,  upper-diagonal  and  lower-diagonal  elements respectively. In this form, the matrix looks like

⎡  %        %

⎢  &           &

⎢          $

# . % ⎥

 #   ⎦

diagonal should therefore  be  of  length  , whereas  upperDiagonal and  lowerDiagonal should be of length   −  1.

2.  For this class, you will need to implement your own LUdecomp method to perform LU decomposition, which should not be copied from GeneralMatrix, since the algorithm for a tri-diagonal matrix is very simple to derive. First, we assume that the diagonal elements of the lower-diagonal matrix

 are 1. Then, you should show that the matrix product

⎡ 1                                   ⎤⎡                                           ⎤

⎢                 ⋱         ⎥ ⎢                   %        . % ⎥

AAAAAABAAAAAAAAB

*                                                                     +

is tri-diagonal. Finally, set the product equal to the matrix  above, and equate co-efficients to find a difference relation for each of the  ,   and   . Just like the LUdecomp method above, you can store the matrix in a compact form inside a TriMatrix.

2.4      The Project3 class

The final part of this project is to generate some simple statistics on random matrices. Here, the definition of random  is that  each  co-efficient  of the  matrix   will  have ,-    ∼  (0,1) (i.e.,  a  uniformly  distributed random number between 0 and 1).   =  () is a random variable: the question is, how is  distributed? You will estimate the variance  &  =  () by generating several random matrices of various sizes, and then calculate the determinant of each of the samples.

Project3 contains two functions to aid you in this endeavour. It is not meant to be challenging – indeed, it is probably the easiest part of the assignment!

•  matVariance(): This function will be passed a Matrix object and an integer 01!2 . It should generate  random  matrices ,  for 1  ≤    ≤  01!2  by  calling the  random function  on the  passed matrix. The variance is estimated by

 &  = (& ) − [()]&  =  3!"#\,4%$  det(, )&  −  ` 3!"#\,4%$  det(, )a&

You should not store each of the random samples, as this will consume a huge amount of memory for large values of 01!2 .

•  main: Your main function should not be a tester in this class. Instead, for 2  ≤    ≤  50, it should create  a   ×  GeneralMatrix and  a  TriMatrix,  and  pass these to matVariance() to calculate the variance of the distribution for this value of  . For each  , you should generate 20,000 general matrix samples and 200,000 tri-diagonal samples.

Ensure that you test matVariance()intensively before running with large numbers of samples. Start with a small number of samples at first to ensure you are not encountering infinite loops, etc. My solution code completes this in just over a minute (on bell), so this should be your aim. You should print this information out to the terminal. On each line, print out

n varGen varTri

where n is the integer value of  , varGen is the variance found for the GeneralMatrix and varTri is the variance  found  for the  TriMatrix, both  formatted to  computerized  scientific notation with 15 digits after the decimal point.

https://docs.oracle.com/javase/8/docs/api/java/util/Formatter.html#syntax

Finally, you should plot two graphs with the data you find: one for the general matrix and one for the tri- diagonal. Along the  -axis plot the matrix size, and along the  -axis, the logarithm of the variance.

To save your output to a file, on bell you can run the command

java Project3 > variance.data

and then transfer this file to your computer – for more information, see the week 12 and 15 lab notes, where you did something similar. Once you have this on your computer, you can then issue the following commands in Matlab to produce the plots:

load 'variance.data'

subplot(211)

semilogy(variance(:,1), variance(:,2), 'r')

subplot(212)

semilogy(variance(:,1), variance(:,3), 'b')

orient landscape

saveas(figure(1), 'VarGraph.pdf')

This will create two subplots; the top one containing the general matrix variance, the bottom the tri-diagonal matrix. Finally, it saves the plots as a PDF file, which can be opened in Adobe Reader or similar viewers. You should add labels to the plot.

3        A note on efficiency

Your code will not, generally, be tested for efficiency, and will not be tested for very large matrices; at most, you will be given a 100×100 matrix. However, it perfectly possible to calculate the determinant of such a matrix in much less than a second using the methods outlined here. Bear in mind that you will need a certain amount of efficiency in your code to complete the Project3 class.

Whilst it is certainly possible to write all this code on bell, I heartily encourage you to do your initial testing on your laptop or desktop machine. Not only do they provide a more friendly development environment, but if you inadvertently run code with an infinite loop, it will not have an impact on other users.

Finally, the Project3 class can be quite time-consuming, but shouldn’t take more than a couple of minutes to run. You should test this on your own machine if possible; if not, then reduce the number of samples generated at first to get an initial indication of the time it will take to run. Remember that if your code is taking minutes to calculate determinants of small matrices, something is very wrong!