Please finish before the deadline.
MATH 456 Final Projects Due 04/23/2023 by 11:59pm (upload to Canvas) Final Project Description The final project will be a typed report which addresses one of the following (or proposed) projects. Each of the below projects deals with either Eigenvalues, Boundary Value Problems, Optimization, or the Fast Fourier Transform. More specifically, it looks at these topics in the context of an applied problem. Your report should address the questions listed under each project; however, in addition it should clearly explain the problem the project is dealing with and how it is related to the topics we covered in class. You may also explore or pose questions which you think are interesting as they are related to the project. The goal is to think about the problems. Any exposition around potential extensions or variations will be viewed favorably. Project Parameters 1. You may also choose your own project but it must be approved by me no later than 3/31. 2. You may work individually or in groups of up to three people. 3. Your submission should contain two total files. One pdf file containing all of your solutions (including the output of your code) and one file with your code. I should not need to run your code to view your solutions. Projects 1. Page Rank This project looks at an application of Power Iteration which is used to compute a quantity called page rank. Page rank is a measure which search engines such as Google.com use to determine the quality of their recommendations. The goal of this project will be to address the suggested activities 1-7 on page 578 of Timothy Sauer’s, Numerical Analysis. • Relevant References: Pages 575–578 of Timothy Sauer’s, Numerical Analysis. 2. Buckling of a Circular Ring A very common application of BVPs is modeling the properties of structural systems –e.g. how structures deform under stresses. This project uses Boundary Value Problems (BVPs) to model the buckling of a circular ring. The goal of this project will be to address the suggested activities 1-7 on page 376 of Timothy Sauer’s, Numerical Analysis. • Relevant References: Pages 374–375 of Timothy Sauer’s, Numerical Analysis. 3. Optimization in Deep Learning Deep learning has become a topic of significant interest in recent days. The goal of this project is to understand how our basic framework of pk = −B−1k ∇ϕ(xk) αk = linesearch() xk+1 = xk + αkpk fits into how Deep Neural Networks learn. The below paper considers a model problem of training a network to classify a set of points into two categories. This will be our model problem considered in the tasks below. 1 • Relevant References: C. Higham, D. Higham. Deep Learning: An Introduction for Applied Mathematicians, SIAM Review, 2019. (a) In your own words, describe the optimization problem being set up in Section 2. Recre- ate the results of Section 2 using MATLAB’s lsqnonlin (you may use the code provided by the paper). (b) Read Section 4 of the paper and describe Stochastic Gradient descent. How is it related to the traditional Gradient Descent? What are its benefits and drawbacks? In context of our basic framework for choosing our search direction pk, what are the update formulas for each method? (c) In the context of our basic framework what is the learning rate? Can we modify the learning rate during training? If so, provide one method we could use. (d) Read Section 5 of the paper. What is back propagation and how is it related to applying (stochastic) gradient descent? (e) Apply stochastic gradient descent and report your results (you may use the paper’s code). (f) Modify the paper’s code to experiment with solving the problem using traditional gradient descent method. Report your results. 4. Fast Fourier Transforms, Eigenvalues, and Solving Ax = b. This project will investigate matrices with circulant structure and their computational properties. Specifically, it will investigate two different types of circulant structure: (a) Standard Circulant Matrices. These are defined as matrices where each row is a circular shift of the row above it, e.g. C = c1 c2 c3 c4 c4 c1 c2 c3 c3 c4 c1 c2 c2 c3 c4 c1 . Assume C is a circulant matrix of size n and is constructed from its first row c = (c1, c2, . . . , cn) T . Circulant matrices are special in that their eigenvalue decomposition is given by C = 1 n F−1ΛF where F is the Fourier matrix and Λ is the diagonal matrix with diagonal entries ĉ = Fc. (In this case, F is the Fourier matrix without the normalization by √ n.) i. Find an algorithm that is O(n log n) for solve the linear system Cx = b for x. ii. Apply the algorithm for an increasing size of n and compare this with using Gaussian Elimination to solve the system Cx = b. Report the timing results. (b) Circulant Block Matrices These are block matrices where each individual block is circulant. For example, we could have and n× n matrix B = C11 C12 C13 C14 C21 C22 C23 C24 C31 C32 C33 C34 C41 C42 C43 C44 where each Cij is an m×m circulant matrix as defined above. i. Apply Jacobi iteration to solve Bx = b and determine the big-O complexity for com- puting a single iteration without taking into account any structure. ii. Use the circulant structure to speed up your Jacobi iteration. What is the big-O complexity? iii. Implement your solutions for increasing sizes of n and compare your results. 2