Math 56 projects. Project 1-page descriptions with a couple of references due Fri May 9 Presentations Tues May 27 in class, and Wed May 28 usual X-hr slot. Write-ups due Friday 30th May at noon. ---- Alex Barnett 5/6/14 List of ideas (you may create your own, but they must have some overlap with class content): Take any topic from class and investigate further, with a computational component. (See references on the Schedule page). How does FFT work for N prime? How is FFT actually coded and why is this faster than our recursive algorithm from class? How does the in-place bit-reversal FFT work? Write the fastest FFT you can in C, comparing a couple of versions. Non-uniform FFT, using Gaussian convolution as in Greengard-Lee. Use for spectral or autocorrelation analysis of spike data eg distribution of prime numbers. Study other matrix norms and singular value decomposition (SVD) including implementing applications to data analysis. (Trefethen-Bau book) Go more in depth into image deconvolution algorithms that handle noisy images, Tikhonov regularization. Study and implement methods for dense matrix eigenvalues (Trefethen-Bau). Implement BBP algorithm for arbitrarily high hexadecimal digits of pi. Discuss the PSLQ algorithm used to find the BBP formula. Implement the search for asymptotics of the number of unique entries in the n*n multiplication table, using random factored integers and Monte-Carlo, as in Brent-Pomerance 2012. See: http://maths-people.anu.edu.au/~brent/pd/multiplication.pdf Riemann zeta function: how is it computed, and how can its Fourier transform tell you about prime numbers? Plot fractals from Indria's pearls book; teach us some about the group theory underlying them. Ulam spiral - how dense are the "arms"? What number theory conjectures underlie them, and what is known? Explore and solve for coeffs of high-order finite-difference stencils, following LeVeque book. Do the same in 2D. Use to solve ODEs on regular grids, understand how to do boundary conditions in 1D and maybe 2D. Dig into Dan Bernstein's algorithms for batch GCD to crack RSA keys from bad random prime generators. Write your own code, test, and explain the algorithms. See http://facthacks.cr.yp.to/ Study conjectures on pattern-avoiding permutations. Study of 3n+1 conjecture (eg number of iterations, largest n). Do large-scale computations, statistics of distributions (eg Benford's Law), analyse the graph following the iteration backwards. See Lagarias reviews, and Miller-Takloo-Bighash book. Dig into attempts to prove in literature. Study FFT for other audio applications, effects, signal processing. Install Chebfun, teach us about what it does, and write a new demo, upload to the chebfun demos site. Read on how non-power-of-two FFTs work. How does it work for N a prime? Also discuss bit-reversal for in-place FFT. Code and test some of the algorithms. Or maybe focus on history of Gauss and the FFT (Heideman et al article). Study and implement/compare algorithms for large-integer multiplication in Ch. 9 of Crandall-Pomerance. What does mpmath use? For what N is each algorithm best? History of computation of digits of pi. How does polygon method work? What is its complexity? How did people actually compute on pencil & paper? Compute highest digits of pi you can. Compare different methods, eg Brent-Salamin vs Ramanujan, other recent cubic etc methods. Statistics of digits of pi - uniform distribution, auto-correlation? Do some large-scale tests of whether they are an iid random string. Quadrature for integrals of functions with singularities at ends (implement sinh-tanh quadrature and compare to Adcock-Richardson 2014). Evaluate integrals to 1e4 digits. Compare various quadrature schemes. Look for relations via PSLQ. Eigenvalue spacing distributions of random matrices, or for singular values. Extremal distributions and Tracy-Widom. Benford's Law (not so exciting) Spectral methods in 1D, then 2D, or time-stepping of 1D problems (Trefethen book on this). Project ideas on links in http://experimentalmath.info Parallelize codes via openMP or MPI. Build a sage module. Upload a working documented utility to matlabcentral. Make adaptive BVP spectral-element solver, or ODE spectral solver via time grid. (?) Explore pyOpenCL, go through tutorials, then code something useful on a GPU. See: http://andreask.cs.illinois.edu/Teaching/HPCFall2012 Discuss large computing architectures. Review some advanced techniques & history. (although don't just paraphrase Bailey, Gourdon, etc).