Math/CS 466/666
466/666 NUMERICAL METHODS I (3+0) 3 credits
Instructor Course Section Time Room

Eric Olson Math 466/666 Numerical Methods I MWF 99:50am DMS106
CS 466/666 Numerical Methods I M 2:303:45pm DMS106
W 2:303:45pm SEM340
Course Information
 Instructor:
 Eric Olson
 email:
 ejolson at unr dot edu
 Office:
 Monday, Wednesday and Friday 10am DMS 238 and by appointment.
 Homepage:
 http://fractal.math.unr.edu/~ejolson/466/
 Assistant:
 Jordan Blocher
 Jordan's email:
 jordanblocher at gmail dot com
 Required Texts:
 Justin Solomon, Numerical Algorithms: Methods for Computer
Vision, Machine Learning and Graphics, CRC Press, 2015.
 Supplemental Texts on Numerical Methods:
 David Kincaid and Ward Cheney,
Numerical Analysis: Mathematics of Scientific Computing,
3rd Revised Edition,
Pure and Applied Undergraduate Texts,
American Mathematical Society, 2002.
 Richard Burden, Douglas Faires and Annette Burden,
Numerical Analysis, 10th Edition, Brooks Cole, 2015.
 Joe Hoffman and Steven Frankel, Numerical Methods for
Engineers and Scientists, Second Edition, CRC Press, 2001.
 Classic Texts on Numerical Methods:
 Kendall Atkinson, An Introduction to Numerical Analysis,
Second Edition, Wiley, 1989.
 Richard Hamming, Numerical Methods for Scientists and Engineers,
Second Edition, Dover, 1986.
 Eugene Isaacson, Analysis of Numerical Methods, Revised Edition,
Dover Books on Mathematics, 1993.
 Supplemental Texts on Computer Programming:

JTC1/SC22/WG14,
C99
Programming Standard, ISO/IEC, 2007.
 Simon Long, Learn
to Code with C, MagPi, 2017.
 Richard Smedley,
Conquer the Command Line, MagPi, 2016.
 Classic Texts on Computer Programming:
 Brian Kernighan, Dennis Ritchie,
C Programming Language, 2nd Edition,
Prentice Hall, 1988.
 Brian Kernighan, Rob Pike,
Unix Programming Environment,
PreticeHall Software Series, 1984.
Student Learning Outcomes
Upon completion of this course
 Students will be able to implement a numerical method to solve a
nonlinear equation using the bisection method and Newton's method.
 Students will be able to solve linear systems using direct and
iterative methods.
 Students will be able to construct interpolating functions.
Announcements
[24Dec2017] Solutions to Final Part 2
Here are my solutions to
part 2 of the Final Exam.
[18Dec2017 or 20Dec2017] Final Exam
Please study the following theory in preparation for
the final exam:
Please study the following programming problems:
 Refer to Section 4.1.4 see also Exercise 4.4 from the text.
Given points x_{i} and y_{i} in
R^{2}, write a subroutine to find the matrix
A∈R^{2×2} and
the vector b∈R^{2} which minimizes
the sum
∑_{i}  Ax_{i}+b−y_{i} ^{2}.
A subroutine to perform this minimization might appear as
void findAb(int n,double x[n][2],double y[n][2],
double A[2][2],double b[2]){
// Fill in code here to solve for A and b.
}
 Refer to Exercise 4.7 from the text.
Consider the underdetermined system Ax=b where
A∈R^{m×n} with
m<n. Solve the optimization problem
minimize x such that Ax=b.
by taking x=A^{T}(AA^{T})^{−1}b.
A subroutine to solve for x might appear as
void undsolve(int m,int n,double A[m][n],double x[n],double b[m]){
// Fill in code here to solve for x when m<n.
}
 Refer to Exercise 4.8 from the text and also the
Wikipedia
entry on the Thomas Algorithm. Suppose
A∈R^{n×n} is tridiagonal
with the vector v along the diagonal, w on the
upper diagonal and u on the lower diagonal. Thus,
Assume
u_{i}+w_{i}<v_{i}
for every i so that Gaussian elimination can be performed
without any pivoting to solve Ax=b in order O(n) time.
A subroutine to solve for x might appear as
void tdthomas(int n,double u[n],double v[n],double w[n1],
double x[n],double b[n]){
// Fill in code here to solve for x.
// Note that the first element of the vector u is not
// used for this computation.
}
[18Dec2017 or 20Dec2017] Programming Project/Homework 3
The combined Programming Project/Homework 3 is
due on the day of the the final exam. That would be December 18 for
the Math 466 section and December 20 for CS 466 section. Please let
me know if you are in the mathematics section and wish to turn your
programming project on the later date.
[11Dec2017] Quiz 2
Quiz 2 concerning Newton's method
will be given in class Monday, December 11. Please prepare answers
to the following questions:
 State Newton's method for solving f(x)=0.
 Let f be a twice continuously differentiable function
and a be a point such that f(a)=0 and f'(a)≠0.
Prove that Newton's method is quadratically convergent
provided x_{0} is close enough to a.
 Explain why it is sometimes said that Newton's method doubles
the number of significant digits at each iteration.
[06Dec2017] Newton's Method Lecture
The lecture notes on Newton's method
are now available online.
[05Dec2017] Solutions to Programming Project 2
Solutions to Programming Project 2 are
available online.
[30Nov2017] Homework Solutions
I have posted my solutions for the homework
problems in chapter 3 from the textbook.
[27Nov2017] Inclass Computer Lab
This week you will be working independently on a
computer lab
project to implement and test the inverse shifted power method.
Please come every day and make sure to electronically submit each
step in the assignment. The test matrix
is available in electronic format.
[29Nov2017] Video Homework 7 Due
Please watch the video
Cheapest Super Computer in the World and answer the following questions.
 The video discusses the construction of the DEGIMA
supercomputer at Nagasaki University.
How much did this supercomputer cost?
 What is a GPU and how many GPUs were used in the construction
of the DEGIMA supercomputer?
 The Gordon Bell Prize is an award for outstanding achievments
in highperformance computing.
The team that assembled the DEGIMA supercomputer won this prize
in what year and what category?
 If you had a national grant to make an individualized supercomputer
for your own needs, what specialized field or problem would you focus on?
You may also consult these
other
resources
for more information.
[23Nov2017] Solutions to the Midterm
Here are my solutions to part 1
and my solutions to part 2.
Have a happy Thanksgiving!
[22Nov2017] Midterm Part 2
The midterm exam will consist of two parts each 45 minutes long
over two days.
The second part will be on Wednesday and involve performing
a calculation based on code you have already written in class
or for the programming projects. Possible computations include
 Given some data and a linear model perform a linear regression
to fit the parameters in the model using a least squares fit.
 Given an invertible matrix find A_{2},
A^{−1}_{2} and cond_{2}(A).
There will also be an extracredit problem not on the above list
for the second part.
[21Nov2017] Gnuplot
I'm posting a few notes on how we used gnuplot to check the
least squares fit last week. Recall that the coefficients for the
cubic polynomial fit of the data in file05a.dat were given
as c = (7.62161, 13.8851, 4.80863, 1.93201). To visually
compare this
polynomial with the data we used the following commands
$ gnuplot
gnuplot> f(x)=7.6216113.8851*x4.80863*x*x+1.93201*x*x*x
gnuplot> plot "file05a.dat" every ::1 ps 2 pt 5,f(x)
Note that the option every ::1 instructs gnuplot not to plot
the first line of the file.
We omitted this option in class, but the graph looks better
with it included.
This is because the first line of the file wasn't
data but instead indicated the number of data points in the file.
[20Nov2017] Midterm Part 1
The midterm exam will consist of two parts each 45 minutes long
over two days.
The first part will be on Monday and involve writing a missing
subroutine or subroutines to complete a given program.
Possible topics for the subroutine include
 Find the inverse discrete Fourier transform of a vector
with length equal to a power of two using a
fast conqueranddivide algorithm.
 Use the PLU factorization to find the inverse matrix.
 Write four subroutines to find the products AB, A^{T}B,
AB^{T} and A^{T}B^{T} of matrices with
compatible dimensions.
[15Nov2017] Programming Project 2 Due
Programming project 2 is due in
class on Wednesday. The special matrix associated with your
netid needed for completing this assignment will soon be available.
[13Nov2017] Data Files for Linear Regressions
There are two data files for linear regressions available.
[08Nov2017] Video Homework 6 Due
Please watch the video
Can
We Make Quantum Technology Work? and answer the following questions.
 When Leo Kouwenhoven went to university, what subject was his
first choice of study?
 List some possible applications for quantum computing.
 What is a qubit? In theory how much faster is a 32qubit quantum computer
compared to a 16qubit quantum computer?
 Predict when, if ever, a quantum computer will be available
for student use at UNR. Explain your reasoning.
[23Oct2017] Video Homework 5 Due
Please watch the video
Sunway
TaihuLight's Strengths and Weaknesses Highlighted by
Jack Dongarra and answer the following questions.
 Who is Jack Dongarra?
 The processors used in the TaihuLight were developed and
manufactured in China.
How many cores does each processor contain?
What is the clock speed of each core?
 How many GFLOPS per watt does TaihuLight achieve?
 Estimate how many GFLOPS per watt are produced by the computers in DMS106.
Explain your answer and any assumptions you made.
See Sunway
Taihulight Named World's Fastest Supercomputer for more
information.
[18Oct2017] Written Homework Due
Please turn in exercises 3.1, 3.6, 3.9, 3.11 and 3.15 in class.
[11Oct2017] Video Homework 4 Due
Please watch the video
Faster
than Fast Fourier Transform and answer the following questions.
 What is a sublinear algorithm?
 What is the difference between sample complexity
and runtime complexity?
 According to Michael Kapralov, what properties would the ideal
Fourier transform algorithm have?
 Do you think such an algorithm exists
and will it ever be discovered?
[09Oct2017] Quiz 1
Quiz 1 concerning the fast Fourier transform will be given
in class Monday, October 9.
[04Oct2017] Programming Project 1 Due
Programming project 1 is due in
class on Wednesday.
[02Oct2017] Video Homework 3 Due
Please watch the video
The Citadel Campus and
answer the following questions.
 Where is the Citadel Campus located?
 What three energy sources are used to generate the
electricity used at the Citadel Campus?
 A Tier 4 datacenter guarantees 99.995% availability.
How many minutes could a datacenter be unavailable
per year and still meet these requirements?
 What is the advertised network latency from Reno to Las Vegas?
How does this compare to the theoretical limits based on
the speed of light found in Video Homework 1?
Additional information may be found at the
Switch website.
[26Sep2017] Fourier Transform Lecture
The lecture notes on the fast Fourier transform
are now available online as well as all the source
code examples used in the handson discussion.
[25Sep2017] Access Files from Windows
You may find it convenient to access your files from home using putty
to log into nxlogin.engr.unr.edu
using your netid.
Alternatively, you can download the
Math 466/666 Linux Image and
use slogin from within Virtual Box to access your files.
If you are logged into Windows on campus, you may access
your files by mounting the share
\\snappy.cse.unr.edu\<yournetid> in
domain unr.
[18Sep2017] Finding Elapsed Time
Source code for the tictoc timing
routines is available. Files from the math section
are here.
[18Sep2017] Video Homework 2 Due
Written answers to Video Homework 2 are due
Monday, September 18.
[08Sep2017] Video Homework 2
Please watch the video
Beating Floats
at Their Own Game
and answer the following questions.
 In what country does John Gustafson currently live?
 Show that the dot product of (3.2e8,1,1,8.0e7) with
(4.0e7,1,1,1.6e8) is exactly 2.
 What are the advantages of posits compared to floating point numbers?
 Predict when, if ever, hardware that implements posit arithemtic
will be available for student use in the UNR computing labs.
Explain your reasoning.
You may wish to consult this preprint
which further describes posits.
[06Sep2017] Machine Epsilon
A source code template and related
files for the machine epsilon program is available.
[06Sep2017] Video Homework 1 Due
Written answers to Video Homework 1 are due
Wednesday, September 6.
[29Aug2017] Video Homework 1
Please watch the video
Grace
Hopper on Letterman and answer the following questions:
 Who is Grace Hopper?
 How many nanoseconds does it take to travel at the speed
of light from Reno to Las Vegas?
 How many picoseconds does each clock cycle of a
CPU runing at 2.8 Ghz take?
[12Aug2017] Textbook Announced
The primary textbook we will be using for the course
is Numerical Algorithms: Methods for Computer Vision, Machine Learning
and Graphics by Justin Solomon.
This is a standard numerical methods text covering the standard
topics that includes a few remarks about computer vision and machine learning.
Hardbound versions cost about $85 and will be available in the
ASUN bookstore. You may also check
Amazon and other online booksellers
[10Jul2017] Introductory Lecture
The lecture notes for the introductory lecture
are now available online as well as
all the source code examples
used for computing the EulerMascheroni constant
in the handson discussion.
[25Jun2017] Math/CS 466/666 Linux Image
A preliminary version of the Math/CS 466/666 Linux image is available
for download along with
detailed instructions how to install
and run it on your home computer or laptop using
VirtualBox.
Extra Credit
 Write a program to compute the EulerMascheroni constant
which runs on your cell phone.
Report the program, the speed of the program in flops and
the type of cell phone used.
 Consider the programming languages Julia, Maple, Matlab,
Kotlin and Go. Determine which languages store matrices in
rowmajor format and which use columnmajor format.
 When the real number 0.0 is written to memory using
the double precision floating point format, it is stored
in 8 bytes as 64 bits all zero.
Suppose 0.0 is written to memory using the posit format
discussed in Video Lecture 2.
Is it true that all the bits in the bytes used to store
the number are zero? Explain.
 Submit a choice of values for a,
b and c in Programming Project 1 that is
different than the values submitted by any
other student.
 Work problem 3.13abc from the textbook.
 Define x_{p} = (
x_{1}^{p} +
x_{2}^{p} + . . . +
x_{n}^{p}
)^{1/p}
and x_{∞} = max(
x_{1},
x_{2}, . . . ,
x_{n} ).
Prove or disprove the claim that
lim_{p→∞} x_{p} = x_{∞}.

The matnorm1 routine written in class
computes A_{1} by reading
the matrix A from memory one column at a time.
Write a routine which computes the same norm while
reading the matrix row at a time. Compare the speed
of your routine with the routine written in class.
 For n = 10, 20, 40, 80, . . . , 1280
let K_{n} be the average condition number with
respect to the 2norm of
100 random n × n matrices with entries
uniformly distributed between −1 and 1.
Plot K_{n} versus n and try to deduce a relationship
between the size of the random matrices and the average condition number.
 [Midterm Part 2] Let A∈R^{n×n}
be a square invertible matrix.
Consider the algorithm
Repeatedly factorize A=QR and replace A with RQ
described on page 122 of Numerical Algorithms by Justin Solomon.
Write a program that implements this algorithm using one
of QR factorization routines written in class.
Note that sinze A is square, then R and Q
are also square.
Under certain conditions the diagonal elements of
R will converge to the eigenvalues of A up to a
possible sign difference as the program runs.
Starting with the matrix contained in
the file extra.c print the diagonal elements of R
at each iteration to show whether and how they converge.
 [Computer Lab] Modify your program to find an eigenvector
corresponding to the eigenvalue in the top left corner of the
eigenvalue plot for the matrix contained in the
the matrixA.c file.
 [Final Exam] Let A and B be matrices such
that A^{T}A=BB^{T}.
Suppose B is invertible and define
Q=A(B^{T})^{−1}.
Prove or disprove the claim that the columns of Q
are orthonormal.
Sample Code
Programming Assignments
Homework Assignments
 Video Homeworks 1, 2, 3, 4, 5, 6, 7 due as indicated above.
 Exercises 3.1, 3.6, 3.9, 3.11, 3.15 due October 18
(solutions).
Grading
2 Quizzes 20 points each
1 Exam 60 points
1 Final Exam 100 points
3 Homework Assignments 20 points each
3 Programming Projects 20 points each
1 Inclass Lab Work 20 points

340 points total
Exams and quizzes will be interpreted according to the following
grading scale:
Grade Minimum Percentage
A 90 %
B 80 %
C 70 %
D 60 %
The instructor reserves the right to give plus or minus grades and
higher grades
than shown on the scale if he believes they are warranted.
Final Exam
The final exams are presently scheduled for

Math Section: Monday, December 18 from 7:309:30am in DMS106.

CS Section: Wednesday, December 20 from 12:102:10pm in DMS106.
The above times are now finalized. The Math 466 and CS 466 sections
will have their respective final exams at different times on
different days.
Equal Opportunity Statement
The Mathematics Department is committed to equal opportunity in
education for all students, including those with documented physical
disabilities or documented learning disabilities. University policy
states that it is the responsibility of students with documented
disabilities to contact instructors during the first week of each
semester to discuss appropriate accommodations to ensure equity in
grading, classroom experiences and outside assignments.
Academic Conduct
Bring your student identification to all exams. Work independently on
all exams and quizzes. Behaviors inappropriate to test taking may
disturb other students and will be considered cheating. Don't talk or
pass notes with other students during an exam. Don't read notes or books
while taking exams given in the classroom. You may work on the
programming assignments in groups of two if desired. Homework may be
discussed freely. If you are unclear as to what constitutes cheating,
please consult with me.
Last Updated:
Sun Jun 25 14:11:37 PDT 2017