Date:1/21/02 PROJECTS for MATH 4660 and CSC 4666: Numerical Analysis II
Spring Semester 2002
ASSIGNED COMPUTER PROJECT: Projects are done in teams. A team consists of several persons that I will assign. Each team must complete one project from the list of projects given below. Each team must test the projects that they did not develop and write up a formal report on the results. The criteria and suggested content for each report will be depend on the project.
Each student will have an account on linus (one of the math department's networked computers) since it has MATLAB, a software package that you may use but are not required to use. MATLAB is an interpretive software package that may facilitate the completion of your projects and testing. Regardless of whether you use C, C++ or MATLAB, the projects that are developed must run on linus and it is from linus that all testing will take place. That is, you are free to develop the software required by each project in any language and on any computer you wish as long as its execution works on linus. My suggestion is to use MATLAB, since it can link C++ (or other executable files), it has graphics already built in and it is an interpretive language originally developed to handle mathematical problems.
Instructions
for Projects
There
are three major components to a project: software development, testing and
analysis.
Software Development (150 points): Project development
consists of four parts: code, execution, output and use.
1.
Code - the
actual computer implementation of the project.
Since this is not a coding class, I will not, in general, give points
for average cleverness in implementation or penalize for mildly inefficient
performance. When the coding is clearly
superior or clearly inferior, then points will be involved. Note: The development team is
responsible for having all test problems coded up for the testing/analysis
teams. Thus, the code that is developed
must have been run on all the test problems given (see below for the specifications). Robustness (see below) means that the
development team allows for the input of other problems (beyond the test
problems). These other problems need
not be coded up but are the responsibility of the testing/analysis teams.
2.
Execution
(65/150 points) - the algorithm as run must correctly perform what it was
designed to do.
3.
Output
(25/150 points) - relevant, clear display of solution (tables and graphs; that
is visuals) and information associated with the solution (errors, iteration
count, flops, accuracy, time/efficiency measures). If there are graphs or tables as output, how clear do the
graphics/tables display the information required?
4.
Use (60/150
points) - the software is to be used by the class and by me. Use consists of five parts: user support, ease
(user-friendliness), robustness, documentation and a project report.
a.
User
support (20/60) – Responsiveness to correcting incorrect code or confusing
output that users find.
b.
Ease
(20/60) - How easy is it to use your software?
How easy is it for the user to give the software input and to obtain
output?
c.
Robustness
(10/60) - A software system is more robust if it solves a wider range of
problems than another system designed to solve the same types of problems. For example, does the software package, as
it's designed, solve just the test problems or is it general enough to solve
any problem of which the test problems are simply an instance? If the software can solve a class of
problems rather than just the specific test problems, then the software package
in this latter case is more robust than one that just solves the test problems.
d.
Documentation
(10/60) - For each project, an oral presentation with handouts on how to use
the software must be given. In
addition, a read-me file is to be made and accessible for users in the testing
the software.
e.
Project
report - A project report consists of the project proposal, the source code, a
description of the software features and a comparison of the software system
results and that from MATLAB. The
specifics are given below.
Testing and Analysis: There are 75 points for each of the three
projects tested/analyzed. Thus you have
25 extra points and only a maximum of 200 points count toward your grade.
Testing consists of executing the given program and there are no points
associated with the execution; that is, testing simply consists of running the
software developed on the test problems given.
Results from the test problems are to be kept in a file and with a hard
copy of the output handed in (as an appendix).
In general, the teams that develop the software are to output results in
tables and graphs in such a way that the results are displayed so that it
facilitates the understanding of associated solution to the class of problems
that the software was designed to solve.
Thus, in the analysis of the performance associated with the test
problems, direct reference to tables and graphs generated by the software will
be made. In the process of testing the
software, email the team's user-support person about any problems or
fantastically clever/useful features that you have found with an electronic
copy to me.
The
software development team must at least supply the user with error (absolute
and relative error) associated with the test problems when relevant. Moreover, such factors as iteration counts,
flops, and/or execution times, when these are relevant, must be supplied to the
user by the development teams. These
factors are used directly in the analysis.
Therefore, it is to be expected that in the testing, these factors are
part of the output.
The
purpose of an analysis is to get you to critically
evaluate the results obtained from the software as it was run on the test
problems. An analysis requires you to
carefully look at the results. What is
the error? What explains the error -
the test problem itself, the precision used, the step-size used, the numerical
method, or the implementation (the way the code was written)? Is it some of the above reasons or all of
them? If you ask the computer to solve
a (real) problem it is because you don't know the solution. If you knew the solution, you would not have
a problem. So how do you know that the
solution to your problem is the solution that the computer software has
obtained?
An
analysis consists of three parts: summary tables and/or graphs associated with
the output (visuals), a textual part, and appendices.
1.
Summary
Tables and/or Graphs
(25/75) maximum 3 pages - Usually the software development team will
supply tables and graphs. If this is
not the case, a way to summarize the information must be found. The form for the summary is usually in the
form of a table and/or graph. A summary
is a condensation of a lot of information, the software’s output. Your summary table will refer to the
appendix. The appendix contains the
(raw) software output. Your team must decide how best to summarize and graph
the information associated with the raw output.
2.
Text (50/75) maximum 4 pages -
The textual part must address the questions listed above. Note:
A description of the output is not an analysis. There are at least three parts to an analysis into which the 50
points are broken down. In particular
you must address the following.
a.
Compare and
contrast (15/50 points) - In most (all) cases there will be several algorithms
that solve the same class of problems. You must discuss the
similarities/differences among the algorithms or approaches, results, test
problem types. Explain why these
occurred.
b.
Error
(15/50 points) - By the very nature of numerical methods there are associated
errors. What are the sources of the
errors? What explains the errors?
c.
Efficiency
(10/50) - Discuss the efficiency of each algorithm/method. Make sure you define and justify the
efficiency criterion that is being used
by your team (as given by the development team). What is the time efficiency?
What is the storage efficiency?
d.
Critique
(10/50 points) - Evaluate the software that you tested. What is good/bad about the software? What were the salient/useful/compelling
features? What were the flaws in and
difficulties with the software?
3.
Appendix – the raw output from the software. This will usually be a readable computer
file to whose directory you list. You
can attach a hardcopy of it to the report.
Be careful when using words like
"faster," "more efficient," "it is clear,"
"accurate." Be specific. What are meant by these words? Don't assume that this term is clear. Your team must clarify terms such as
these. Back up your words with
acceptable mathematical evidence.
Moreover, directly relate words to the results (output). For example, if you say that Newton's method
is "faster" than the bisection method, this is not specific nor is it
very meaningful. On the other hand
suppose you wrote, "For test problem 1, 2, 3 and 5, Newton's method, on
average, took 0.05 units of efficiency while bisection method took 2.5 units of
efficiency (where you have defined and justified “efficiency”) and on test
problem 4, both methods failed.
Therefore, Newton's method is faster than bisection method." These sentences convey clear, meaningful
and precise information. Here,
"fast" means “units of efficiency.”
If you use "fast" to describe a mathematical algorithm, you
must define "fast." That is,
you must specify how you are measuring the efficiency of the algorithm being
used. If one specifies seven digits of
accuracy for all solution of test problems, then one might use execution time
as a way to measure efficiency. However,
if for one test problem, the accuracy is 4 digits and on another the accuracy
is12 digits, then execution time does not measure how fast the algorithm
obtains a solution. What is a
solution? How many digits of your
solution are accurate? How would you
know if you were not given the solution?
Is there a pattern in the error?
If there is, why does this pattern occur? What is causing the error (input data, truncation error,
algorithmic implementation, a blunder)?
Procedures for Turning in Projects and
Testing/Analysis
1. Each project requires a formal project proposal that, at least, contains the following items:
a. Title of the project
b. Scope of the project - what the project will cover and its component parts
c. Component parts of the project - milestones and division of labor
d. Output
2. One hard-copy report per team with the results is to be submitted.
3. The team whose project is being tested must have software documentation that explains how to run the software. The team that creates the software does not have to submit a testing/analysis report. However, each software development team must submit documentation and a short report the contents of which are listed below.
Note: The following are suggestions for the testing and analysis report.
1. There is one analysis for the whole project. A project may consist of several software components and numerical methods. There is a single analysis for the all components. The analysis is the first part of the report.
2. The textual part of a report should not be more than 3 pages long.
3. Summarize and synthesize all the information. Use summary tables, graphs, and charts. These are “visuals.” Visuals are means by which information about the results are synthesized in a readily apprehended way.
4. Compare
a. Across methods
b. Across test problems
c. Across initial conditions
d. Across step-sizes
5. If the method(s) fail on particular problems, explain why.
6. Display and report all digits of precision that the computer gives you. Of course you must include in your report how many digits are accurate of the ones that are displayed. This is usually reported in the associated absolute and relative errors.
There will be four projects that will need to be completed by the
class in teams. Each team is
responsible for developing the software for one project and testing/analyzing
three projects developed by other teams.
All four project must be done so the teams will need to choose and
negotiate in such a way to insure that at least one team covers each of the
four project.
Note: Software, requisite user’s instructions
and project report are due at the beginning of class on the Thursday listed
below. Testing/analysis reports are due
by 11:59:59PM on the Fridays listed.
Topic Date
Due
Project 1: Software Chap
7,Iterative Matrix Techniques Thursday
2/14
Testing/Analysis Friday 2/22
Project 2: Software Chap
9,Eigenvalues, Eigenvectors Thursday
2/28
Testing/Analysis Friday 3/8
Project 3: Software Chap
10, Nonlinear Equations Thursday
3/21
Testing/Analysis Friday 4/5
Project 4: Software Chap
5, Differential Equations Thursday
4/25
Testing/Analysis Friday 5/3
1.
A designated person
(with the email address) who will handle software support.
Project
1: Algorithm 7.1 –
page 446, 7.2 – page 449, 7.3 – page 457, and 7.4 – page 466.
Test
7.1-7.3 on 5/458 with w = 0.00, 0.25, …,2.00
Test 7.4
on examples 3, 4 on pages 464, 467.
Project 2: Algorithm 9.1 – page 551, 9.2 – page 553, 9.3 – page 557, 9.4 – page 561, 9.5 – page 569 and 9.6 – page 579.
Test 9.1-9.4 on 1-9,15/562,563
Test 9.5 on 2/573
Test 9.6 on 2/583
Project 3: Algorithm 10.1 – page 601, 10.2 – page 610, and 10.3 – page 617.
Test on 1, 3/621, 622
Project 4: Algorithm 5.1 – page 261, 5.2 – page 271, 5.3 – page 281, 5.4 – page 302, 5.5 – page 308, 5.7 – page 320.
Test 5.1-5.5 on 1, 2, 3/317
Test 5.7 on 1, 2/328
Algorithm - Equation (5.17) page 271 and automatic generation of Taylor coefficients that will be developed from in-class notes.
Test on 1, 2, 3/317
Project Report: A report will have a maximum of two pages (10 point font or larger) and will be due on the testing/analysis due date. The contents are the following.