Numerical Analysis 1

2025-02-12 Admin 写评论


Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due


Numerical Analysis 1

Mini-project 1 information
Presentations are on Tues, Feb 25th and Thurs Feb 27th, 2025

Presentation information

Your mini-project should solve a problem more difficult than a typical homework problem, but less difficult than a thesis topic. You will write a program to solve the problem, and then give a presentation before the class describing your solution. The presentation should last no longer than 15 minutes. This means you should present around 6 or 7 slides. A good presentation might look like this:
• 2 or 3 slides introducing your general topic area, and talking about the specific problem you want to solve.
• 2 or 3 slides reviewing your computation and algorithm
• 1 or 2 slide presenting your results.

Process for selecting a mini-project

Come up with your own topic to investigate, or choose one of the selections below. One you choose your subject, please discuss it with Professor Brorson (e-mail your ideas to him). It is likely he will approve your topic if it is relevant to the class, and at the right level of difficulty. He will also make sure everybody has a different topic. After you receive approval, fill out a project proposal form and send it to Prof. Brorson. The form is designed to help you think through all the details necessary to make a successful project presentation. After you send your proposal form to Prof. Brorson may offer some guidance about your project, or just simply give you the green light to go ahead. Then it’s up to you to work on your project independently – read some relevant papers, write your code, and create your presentation.

Mini-project suggestions

You are encouraged to come up with your own topic for the first mini-project . If you can't think of something to do, here are some ideas. Please use them for inspiration.

1. Where's Waldo? In this project, write a program which solves the child's game “Where's Waldo?” using convolution. Use Waldo's image as the kernel, then find the location in the larger image where the correlation between the kernel and the image is high. Due to the duality between convolution in the image domain and multiplication in the Fourier domain, you can also use an FFT to find Waldo. Please implement both methods and show why the FFT version is preferable to the convolution algorithm.

2. Write a program to implement computer graphics transformations using “homogeneous coordinates”. Your test program should try manipulating a wide variety of 3D objects read from VRML files, and then plot the result in 3D. Manipulations include rotations, translations, etc. A good score depends upon making a clear presentation of the mathematics of homogeneous coordinates.3. Latent semantic indexing (LSI) – We looked at an example of using LSI in Class 4 using a very small corpus of documents which I created for the demo. For this mini-project, find a realworld corpus of documents, and perform LSI on it. Be ready to discuss the number of factors (dimensions) to keep in order to get good matches from your search. A good survey article about LSI is available here: http://lsa.colorado.edu/papers/dp1.LSAintro.pdf.

4. Write a program which computes and plots the pseudospectrum of an arbitrary input matrix. In your presentation please show the pseudospectra of some common, important matrices. A description of what matrix pseudospectra are can be found at this website: http://www.cs.ox.ac.uk/projects/pseudospectra/. A good grade on this project depends upon providing a clear explanation of what matrix pseudospectra are and why they are interesting.

5. Write a program to implement a Gabor transform (short time Fourier transform) and make time frequency plots (spectrograms) of a simple tune. A good score depends upon making a clear presentation of the Gabor transform itself.

6. Implement QR decomposition using Householder reflections. This involves implementing your own function to perform Householder reflections. A good grade depends upon making a clear

presentation of what Householder reflections are, and how they work.

7. Write a program (or two programs) which compute the Bessel functions J n (x) and Yn (x) for moderate values of n and all real values of x. You will need to use different algorithms depending upon if x is very small, mid-side, or very large. Then check your implementation using some identities found on the DLMF, https://dlmf.nist.gov/10.

8. Read the paper “Ten Problems in Experimental Mathematics”, available here: http://crd legacy.lbl.gov/~dhbailey/dhbpapers/tenproblems.pdf. Each of the problems listed in the paper discusses an interesting computation. For this mini-project, choose one of the problems and implement a program which computes at least part of the problem. Note that many of the problems listed are difficult, and involve using a bignum library. Please have a discussion with Prof Brorson prior to starting any particular project – he will make suggestions about what is feasible (and not feasible) for you to do. The ideas in this paper should serve as an inspiration for a project, not as a prescription about what to do.

9. For several years the company Netflix ran a competition called “the Netfix Prize”. The competition was open to any entrant, and was for the best recommender system which could be used to predict and individual's ratings of new movies based on that person's previous recommendations. Several new algorithms came out of the Netflix Prize competition, including the “Funk SVD”, invented by Simon Funk. This is a matrix factorization similar to the traditional SVD we discussed in class. For this mini-project, write an implementation of the Funk SVD. A good grade involves making a clear presentation of the Funk SVD algorithm. A useful paper which discusses the algorithm and the Netflix Prize is https://datajobs.com/data-science-repo/Recommender-Systems-[Netflix].pdf .

10. Another algorithm used in the Netflix Prize competition was the so-called SVD++ algorithm. SVD++ builds on traditional SVD, but performs better as a recommnder. Implement this algorithm and describe how it works.

11. Analyze a social network. Choose an interesting dataset from the Stanford collection of network datasets, https://snap.stanford.edu/data/. Then create an implementation of Google's page rank algorithm to identify the most important people in that network.

12. Read about Singular Spectral Analysis (SSA), which is a way to decompose a time series into three pieces: 1. A slowly growing or decaying part, 2. an oscillatory part, and 3. noise. The decomposition is performed using the SVD. Then find an interesting dataset with some periodicity and analyze it using SSA. A good introduction to SSA is under https://ssa.cf.ac.uk/ssa2010/a_brief_introduction_to_ssa.pdf A good grade on this project depends upon providing a clear explanation of the steps required to perform SSA.

发表评论

电子邮件地址不会被公开。 必填项已用*标注