MAT00027I代写、Java程序语言调试、Mathematical Skills代做、Java代写

日期：2020-01-16 10:20

Mathematical Skills II (MAT00027I) 2019/20

Project 2 – Sparse matrices

Background

Matrices with large dimensions can be difficult to handle on computers: For an n×n matrix, the

memory needed to store them grows like n2, while the time needed for operations on matrices(like addition, multiplication, or inversion) can grow like n3.

Fortunately, in several relevant applications, one meets so-called sparse matrices, that is,

matrices where a large number of entries are known to be 0. Working with these can be more

memory- and time-efficient. A simple example are diagonal matrices A, where only the elements

on the diagonal, Aii (0 ≤ i < n) are nonzero, and all other entries vanish. For these, only the

n entries on the diagonal need to be stored (not all n

2

entries). Sums, products, and inverses

of diagonal matrices are again diagonal, following the formulas

(A + B)ii = Aii + Bii, (A · B)ii = AiiBii, (A?1)ii = (Aii)?1

for 0 ≤ i < n. (1)

For performing these computations, only O(n) operations are needed, which is much faster than

in the general case.

A slightly more general example are tridiagonal matrices, where only the entries on the

diagonal (Aii, 0 ≤ i < n), those directly above the diagonal (Ai,i+1, 0 ≤ i < n ? 1) and those

directly below the diagonal (Ai+1,i, 0 ≤ i < n ? 1) are nonzero, and all others vanish. Also for

these, matrix operations can be done much faster than in the general case.

The purpose of this project is to develop a set of functions that compute basic operations

(such as sum, product and inverse) on diagonal and tridiagonal matrices, along with some

applications.

Tasks

Throughout this project, all floating point numbers are of double type and all integers of int

type. All matrix entries are floating point numbers.

1) Diagonal matrices

We can store an n × n diagonal matrix using a one-dimensional array of type double[] with

length n; the array elements a[0], . . . , a[n-1] hold the matrix entries A0,0, . . . , An?1,n?1. Using

this convention, implement the following within the class Diagonals.

(a) Implement a function exampleMatrix, with no parameters, that returns a representation

of the diagonal matrix.

(b) Implement a function sum that computes the sum of two diagonal matrices.

(c) Implement a function product that computes the product of two diagonal matrices.

(d) Implement a function inverse that computes the inverse of a diagonal matrix. (You can

assume that the matrix is invertible.)

1

Mathematical Skills II (MAT00027I) 2019/20

For all three functions, see Eq. (1). If any of the array parameters of the functions is null,

the return value should be null. If the matrix sizes in sum or product are incompatible – e.g.,

when trying to add a 2-entry diagonal matrix to a 4-entry diagonal matrix –, the return value

should be null. If the input parameters are arrays of length 0, the return value should be of

length 0 as well. In all functions, make sure that your code does not alter the values of the

array parameters.

The following table summarizes the functions to be implemented in the class Diagonals,

together with their parameter types and return types.

Name Parameter types Return type

exampleMatrix double[]

sum double[], double[] double[]

product double[], double[] double[]

inverse double[] double[]

2) Tridiagonal matrices

An n × n tridiagonal matrix can be stored as follows in a two-dimensional array of size 3 × n:

? a[0] stores the matrix entries above the diagonal.

a[0][0], . . . a[0][n-2] correspond to A0,1, . . . , An?2,n?1.

? a[1] stores the matrix entries on the diagonal.

a[1][0], . . . a[1][n-1] correspond to A0,0, . . . , An?1,n?1.

? a[2] stores the matrix entries below the diagonal.

a[2][0], . . . a[2][n-2] correspond to A1,0, . . . , An?1,n?2.

? The array elements a[0][n-1] and a[2][n-1] are present but will be ignored in the

following.

Using this convention, implement the following within the class Tridiagonals.

(a) Implement a function exampleMatrix that, given n > 0, produces the n × n tridiagonal

matrix.

(b) Implement a function isValidTridiagonal that tests whether an array? of type double[][]

is a valid tridiagonal matrix in the sense above. It is valid if it is of length 3 at the first

level and of length n at the second level (for some n ≥ 1). If it violates these conditions, it

is invalid. null arrays (at any level) are invalid as well.

(c) Implement a function sum that computes the sum of two tridiagonal matrices.

(d) The product D · T of a diagonal matrix D with a tridiagonal matrix T is tridiagonal.

Implement a function productWithDiagonal that computes this product; the parameters

should be D and T in this order.

?Note that this might, in general, be a ragged array.

2

Mathematical Skills II (MAT00027I) 2019/20

(e) Implement a function linearSolve that computes a solution x ∈ Rn

to the linear equation

system T x = v, given a tridiagonal n × n matrix T and a vector v ∈ Rn. To that end,

use the algorithm that is described in the literature as “tridiagonal matrix algorithm”,

“Thomas algorithm” or “Crout factorization for tridiagonal systems”. You can assume

that T is invertible.

If in any of the functions sum, productWithDiagonal, or linearSolve, one of the parameter

values is invalid in the sense of (b) above, the return value should be null. If the

matrix/vector dimensions in the parameters are incompatible, the return value should be null.

In all functions, make sure that your code does not alter the values of the array parameters.

In summary, implement these functions in the class Tridiagonals:

Name Parameter types Return type

exampleMatrix int double[][]

isValidTridiagonal double[][] boolean

sum double[][], double[][] double[][]

productWithDiagonal double[], double[][] double[][]

linearSolve double[][], double[] double[]

3) A differential equation

As an application example, let us consider the following differential equation for a function f

with boundary conditions:(2)

Here a is a real constant.

A recipe for approximating the solution numerically goes as follows. Choose a positive

integer n (typically n is large, maybe around 1, 000–10, 000). Set h := 1

n+1 and let xi:= ih for1 ≤ i ≤ n. Consider the n × n matrix. (3)

Solve the linear equation system Mw = ?h2v for w ∈ Rn. Then w is an approximation for(f(x1), . . . , f(xn)).

Using your results from previous parts, write a function solve in the class ODE that takes a

(in floating point format) and n (an integer) as parameters, and returns a floating point approximation

for f(0.5). You may assume n > 0. If 0.5 is not among the xi, then the approximation

should be computed by averaging over the approximations at the nearest available xi.

4) Documentation

Within the source code, add Javadoc comments to every class and to every function. In

these, describe the purpose of the function or class, and document all parameters and return

values. Also, document the handling of exceptional input values, and any assumption about

the parameter ranges.

3

Mathematical Skills II (MAT00027I) 2019/20

How to prepare your submission

Start by downloading the template files from Moodle. The Java classes that you will work with

are already defined there.

Read the assignment sheet carefully. Be sure to implement all functions with exactly the

names, parameters and return types that are specified, and with parameters in the order as

given.

While preparing your code, please follow these style and formatting guidelines. (This forms

part of the assessment.)

? Place all code block delimiters – { and } – on separate lines.

? Within code blocks, indent the code by 4 spaces with respect to the surrounding code.

? Choose all names for variables, parameters, functions, and fields to start with a lowercase

character.

Make sure that your code compiles correctly. If the source code files that you submit do not

compile (for whatever reason), you will receive zero marks for the affected parts of the project.

The code template also includes a unit test. This test does not check the output of your

code – it only verifies whether you have declared your functions with the correct names and

with the correct parameter/return types. You are advised to use the unit test to check your

function declarations for any typos.

Test every piece of your code with meaningful test data (including any special or exceptional

values). Verify that the output of your functions is plausible.

Once you are satisfied with the code, create a JAR file in BlueJ as follows:

? Select “Project → Create Jar file” in the menu.

? Leave “Main class” set to “none”.

? Be sure to tick “Include source” and “Include BlueJ project files”.

? Click “Continue” and save the file in a convenient location.

This JAR file is the one that you need to submit.

Please do not mention your name or student number in the code or the documentation, as

your submission will be graded anonymously.

Hand-in, late submissions

Please submit your work by uploading it on Moodle before

Thursday, 16 January 2020 (week 2 Spring term), 2:00:00 pm.

Your submission should consist of the JAR file (containing the code and documentation) and

of nothing else.

Late submissions will incur a penalty according to the University’s standard rules: “Work

which is up to one hour late will have five percent of marks deducted. After one hour, ten

percent of the available marks will be deducted for each day (or part of day) that the work is

late, up to a total of five days, including weekends and bank holidays, e.g., if work is awarded a

mark of 30 out of 50, and the work is up to one day late, the final mark is 25. After five days,

the work is marked zero. Note, however, that the penalty cannot result in a mark less than

zero.”

4

Mathematical Skills II (MAT00027I) 2019/20

Please be sure to press the “Submit assignment” button once finished. You will receive an

e-mail notification from Moodle when your assignment is submitted; if you have not received

this, please assume that your submission is not yet complete.

If your submission is affected by Exceptional Circumstances (such as, being ill), you must

hand in an Exceptional Circumstances claim, accompanied by evidence. If you think this may

apply to you, please contact the Assessment Administrator at maths-exams@york.ac.uk as

soon as possible – and before the deadline if feasible.

Marking

Your submission will be marked as follows. Partial solutions are acceptable, and will be awarded

partial marks.

Code correctness (34 marks) Your code will be tested by an automated process (a collection

of unit tests) to check whether it works correctly for various values of the input parameters.

For each of these test cases that you pass, one mark will be awarded. Marks are awarded entirely

on the criterion whether the output values of your code match the conditions specified

on this assignment sheet.

Coding style (10 marks) Your source code will be read by the examiner. Marks will be

awarded to reflect whether your code is readable, is appropriately structured, and follows the

coding style conventions mentioned above. Marks may be subtracted for code that is functional

but is implemented in a non-transparent or overly complicated way.

Source code documentation (5 marks) These marks are awarded for appropriate Javadoc

comments in the code (see part 4).

In total, 49 marks are available. Your raw mark out of 49 will be moderated and scaled to

the University scale 0–100. This scaled mark will contribute 25% towards your final mark for

the module.

Academic integrity

To this project, the established Academic Integrity rules apply, as set out by the University.

In particular, you must not copy program code or the text of the documentation from fellow

students, or from other public or non-public sources. You must also not make your solution

available to fellow students before the deadline.

You are allowed to re-use example code from the lectures or practicals (though, where you

use it, you should include a comment to that effect in your source).

5