MACM 316- D100 COMPUTING ASSIGNMENT 2

• Please follow the Guidelines for Computing Assignments found on Canvas (under FAQ).

• Submit a one-page report via Crowdmark, grading scheme is also found on the FAQ.

GE Timing Test

From the lecture on operation counts, the flop counts involved in the GE solution for an N × N linear

system, A~x = ~b, are

• O(n

3

), if A is dense and we use GE; and

• O(n

2

), if A is upper triangular and only back substitution is needed.

In this assignment, you will measure the actual computing performance of Matlab on a particular computer, and compare and contrast the data with the theoretical flop counts. We will also be discovering that

Matlab’s ’backslash’ algorithm is more sophisticated than the textbook GE, and offers built-in efficiencies

for special matrix classes.

Before you begin, note that your performance measurements will depend on the computing platform

used. Be sure to gather all the data on the same machine! Include in your report relevant identifying

information, including computer model and year, processor and clockspeed, operating system, and Matlab

version (type version at the Matlab prompt). Furthermore, it is advantageous that you stop all other

activities on your computer while testing.

To begin, start by following the link in the Canvas assignment to the math-apps demo. Run this demo

once, and check that the ouput gives estimated solve times for 3 types of matricies (see below). Then,

copy the entire code (including portions outside the edit window), and paste it into your

own Matlab script. You will build upon this code to complete the assignment. Once you have

succesfully run the demo and extracted the code, you do not need to submit anything else to the mathapps online portal for this assignment.

This script that you have just run and copied performs the set-up for three N × N linear solve tests with

matrices [M] having certain patterns of zero entries

• [Md], a dense matrix with random entries using randn (no zeros);

• [Mt], an upper triangular matrix extracted from [Md] (using triu);

• [Mp], a randomly row-permuted form of [Mt].

The test uses righthand side vectors ~b that give solutions ~x that are vectors of all 1’s.

Matlab has a handy set of tools, called tic and toc, that can be used to time portions of your script. Calling

tic in Matlab will start a timer, and toc will output the current time elapsed. Wrapping a portion of your

script between tic and toc will allow you to time how long, in seconds, that section of code took to run.

However, Matlab documentation does NOT recommend to use tic and toc for processes that take less than

0.1 seconds to run, as the accuracy for short times is unreliable. Since Matlab can solve even large matrix

problems incredibly quickly, this presents a problem.

The way that the demo works around this is that it repeats each matrix solve Nex number of times, and

it records the total time for all the solves. This total time can be designed to be well in excess of the 0.1

second minimum, despite the fact that the average time per solve may be much less.

For this computing assignment, incorporate the following into your experiment and report:

DJM 1

MACM 316- D100 COMPUTING ASSIGNMENT 2

• Modify the script to collect average solve times over a range of matrix sizes Nex, for all three of the

above described matrix classes. However, we expect that solve times for a smaller matrix should be

faster, therefore a larger Nex is needed to get the measured time above tic and toc’s range of accuracy.

Likewise, different types of matrices may require more or less Nex than others. The takeaway: using

the same Nex for all sizes and types of matrix is poor experimental design.

• The theory for GE operation counts suggests that for large N, a power-law relationship between the

flop count and matrix size. This suggests that a log plot of solve times versus matrix size should

be considered. On such a log-log plot, the power for the relationship can be obtained — see the plot

example that accompanies this assignment (power law plot.m).

• Discuss the comparison of these results, to each other, as well as to the theoretical flop counts. What

might this reveal for what happens with backslash in Matlab? Particularly, what might one make

of the observations for the permuted upper-triangular case, [Mp]? When adressing this point, it may

help to recall the flowchart shown in lecture, detailing Matlab’s ’backslash’ implementation.

• Having benchmarked the timing against some known results, now do additional testing on two other

matrices

• [M3], a tri-diagonal matrix extracted from [Md] (using diag); and

• [M3s], a sparse-version of [M3] (using sparse).

The code to build these matricies has already been included in the demo script, and simply needs to

be uncommented.

DJM 2