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 9-9:50am      DMS106

            CS 466/666 Numerical Methods I     M   2:30-3:45pm   DMS106
                                                W  2:30-3: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, Pretice-Hall Software Series, 1984.

Student Learning Outcomes

Upon completion of this course
  1. Students will be able to implement a numerical method to solve a nonlinear equation using the bisection method and Newton's method.
  2. Students will be able to solve linear systems using direct and iterative methods.
  3. Students will be able to construct interpolating functions.

Announcements

[24-Dec-2017] Solutions to Final Part 2

Here are my solutions to part 2 of the Final Exam.

[18-Dec-2017 or 20-Dec-2017] Final Exam

Please study the following theory in preparation for the final exam: Please study the following programming problems:

[18-Dec-2017 or 20-Dec-2017] 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.

[11-Dec-2017] Quiz 2

Quiz 2 concerning Newton's method will be given in class Monday, December 11. Please prepare answers to the following questions:

[06-Dec-2017] Newton's Method Lecture

The lecture notes on Newton's method are now available online.

[05-Dec-2017] Solutions to Programming Project 2

Solutions to Programming Project 2 are available online.

[30-Nov-2017] Homework Solutions

I have posted my solutions for the homework problems in chapter 3 from the textbook.

[27-Nov-2017] In-class 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.

[29-Nov-2017] Video Homework 7 Due

Please watch the video
Cheapest Super Computer in the World and answer the following questions. You may also consult these other resources for more information.

[23-Nov-2017] Solutions to the Midterm

Here are my solutions to part 1 and my solutions to part 2. Have a happy Thanksgiving!

[22-Nov-2017] 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 There will also be an extra-credit problem not on the above list for the second part.

[21-Nov-2017] 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.62161-13.8851*x-4.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.

[20-Nov-2017] 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

[15-Nov-2017] 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.

[13-Nov-2017] Data Files for Linear Regressions

There are two data files for linear regressions available.

[08-Nov-2017] Video Homework 6 Due

Please watch the video Can We Make Quantum Technology Work? and answer the following questions.

[23-Oct-2017] Video Homework 5 Due

Please watch the video Sunway TaihuLight's Strengths and Weaknesses Highlighted by Jack Dongarra and answer the following questions. See Sunway Taihulight Named World's Fastest Supercomputer for more information.

[18-Oct-2017] Written Homework Due

Please turn in exercises 3.1, 3.6, 3.9, 3.11 and 3.15 in class.

[11-Oct-2017] Video Homework 4 Due

Please watch the video Faster than Fast Fourier Transform and answer the following questions.

[09-Oct-2017] Quiz 1

Quiz 1 concerning the fast Fourier transform will be given in class Monday, October 9.

[04-Oct-2017] Programming Project 1 Due

Programming project 1 is due in class on Wednesday.

[02-Oct-2017] Video Homework 3 Due

Please watch the video The Citadel Campus and answer the following questions. Additional information may be found at the Switch website.

[26-Sep-2017] 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 hands-on discussion.

[25-Sep-2017] 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\<your-net-id> in domain unr.

[18-Sep-2017] Finding Elapsed Time

Source code for the tictoc timing routines is available. Files from the math section are here.

[18-Sep-2017] Video Homework 2 Due

Written answers to Video Homework 2 are due Monday, September 18.

[08-Sep-2017] Video Homework 2

Please watch the video Beating Floats at Their Own Game and answer the following questions. You may wish to consult this preprint which further describes posits.

[06-Sep-2017] Machine Epsilon

A source code template and related files for the machine epsilon program is available.

[06-Sep-2017] Video Homework 1 Due

Written answers to Video Homework 1 are due Wednesday, September 6.

[29-Aug-2017] Video Homework 1

Please watch the video Grace Hopper on Letterman and answer the following questions:

[12-Aug-2017] 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

[10-Jul-2017] 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 Euler-Mascheroni constant in the hands-on discussion.

[25-Jun-2017] 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

  1. Write a program to compute the Euler-Mascheroni constant which runs on your cell phone. Report the program, the speed of the program in flops and the type of cell phone used.

  2. Consider the programming languages Julia, Maple, Matlab, Kotlin and Go. Determine which languages store matrices in row-major format and which use column-major format.

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

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

  5. Work problem 3.13abc from the textbook.

  6. Define ||x||p = ( |x1|p + |x2|p + . . . + |xn|p )1/p and ||x|| = max( |x1|, |x2|, . . . , |xn| ). Prove or disprove the claim that limp→∞ ||x||p = ||x||.

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

  8. For n = 10, 20, 40, 80, . . . , 1280 let Kn be the average condition number with respect to the 2-norm of 100 random n × n matrices with entries uniformly distributed between −1 and 1. Plot Kn versus n and try to deduce a relationship between the size of the random matrices and the average condition number.

  9. [Midterm Part 2] Let ARn×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.

  10. [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.

  11. [Final Exam] Let A and B be matrices such that ATA=BBT. Suppose B is invertible and define Q=A(BT)−1. Prove or disprove the claim that the columns of Q are orthonormal.

Sample Code

Programming Assignments

Homework Assignments

  1. Video Homeworks 1, 2, 3, 4, 5, 6, 7 due as indicated above.
  2. 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 In-class 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

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