Project Suggestions for CS/MA 615

  1. Rewrite the code for parabolic PDEs to use multigrid to solve the elliptic problems and generally clean up the code. This is one-person project.
  2. Solve an image segmentation problem. Use 1 and 2 to compute solutions to "Threshold dynamics for the piecewise constant Mumford-Shah functional", by Selim Esedoglu and Yen-Hsi Richard Tsai, J. Comput. Phys. 211 (2006), pp. 367--384. This is a two-person project.
  3. Apply domain decomposition techniques. Block the matrix operator so that each triangle in the coarse triangulation leads to its own local operator. The object of this project is speed, not functionality---you should be able to cut the solution time by at least 1/3, and perhaps parallelize it. It's a one- or two-person project, depending on how much you want to achieve.
  4. Add a reaction term to the parabolic code. There is code in mmoc.scm to solve a convection-diffusion equation using the "modified method of characteristics" of Douglas and Russell; if you're interested in this kind of stuff you can add a reaction term (modelling chemistry, say) to this code. (Note added in later: the code in mmoc.scm doesn't work, fixing it is a project.)
  5. Write time-stepping code for second-order hyperbolic problems. This is a one-person project.
  6. Exploit symmetry in matrix representations. The Sparse-matrix and Sparse-matrix-operator classes exploit the sparsesness of a matrix A, but not its symmetry. Define two new classes Symmetric-parse-matrix and Symmetric-sparse-matrix-operator that exploit the symmetry of A by calculating and storing and using only the lower-triangular elements. See how much faster you can make the code.
  7. Write code to solve the "obstacle problem". Use the Douglas-Rachford iteration method as described in the paper Splitting algorithms for the sum of two nonlinear operators by P. L. Lions and B. Mercier, SIAM J. Numerical Analysis, (16) 1979, pages 964-979. A one-person project. (There used to be code for the obstacle problem in the system, but it was nonsense and I removed it.)
  8. Finite difference schemes. This is a multi-step project. It would need to be coordinated among several people. Among the subprojects:
    1. Find a way to describe the domains you want to handle; probably just rectangles or unions of rectangles. Discretize these domains; refine the discretizations.
    2. Calculate the finite difference spaces; build the matrix multiplication operator based on the coefficients.
    3. Build injection and projection operators for multigrid applied to the finite difference problems.
  9. Write code to solve the linear, time-dependent Schrödinger equation. This is a one-person project. This problem is solved several orders of magnitude faster using multigrid rather than conjugate gradient to solve the elliptic problems that arise in Crank-Nicolson time stepping, so you'll need to use multigrid for this project.
  10. Parallelize the code. This isn't as hard as it sounds. Dan O'Malley has written a bit of wrapper code to use MPI with Gambit, and one can block the matrix multiplications so that computations on all coarse triangles are done in parallel. A two-person project.