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