Java代写|MA117 Project 3: Determinants of Matrices


1 Formulation of the Problem

Matrices are one of the most important mathematical concepts to be modelled by computer, being used in many problems from solving simple linear systems to modelling complex partial differential equations.

Whilst a matrix (in our formulation) is simply an element of the vector space ℝ!×#, it usually possesses some structure which we can exploit to gain computational speed. For example, a matrix-matrix multiplication generally requires of the order of ?$ floating-point operations. If the matrix has some special structure which we can exploit using a clever method, then we might be able to reduce this to ? operations. For large values of ?, this significantly improves the performance of our code.

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

? 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

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 aleft 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).