Course projects

CS289 Final Project, Fall 2018:

Combination of Particle Swarm Optimization with Stigmergy and Evolution

I have been fascinated by social insects for quite some time. In CS289, we learned a lot about how to design algorithms so that multi-agent systems can produce predictable (most of the time) and useful collective behavior, be it finding the shortest path between points, transporting an object, building structures, forming static or dynamic patterns, etc.

For the final project, I reflect on the very first concept we learned in class, i.e. stigmergy, which beautifully demonstrated in an experiment of ants finding the shorter path to a food source. There are two bridges connected to it, both with identical branching angle from the centerline, but one is longer than the other. The idea of stigmergy functions similarly in numerical methods, and have been used to approximately solve the traveling salesman problem, find optimal routes within a network, etc. The examples we saw in class were mostly combinatorial problems, which made me wonder if multi-agent approach and the idea of stigmergy can be used for continuous global optimization problems as well.

And of course it can be and it has been. Our group decided to look into a simple, effective, and flexible method called the Particle Swarm Optimization. We are currently working on extending it with additions of Ant Colony Optimization; thinking about some new ideas of incorporating stigmergy; and eventually we want to subject the whole shebang to artificial evolution. A brief intro to our project can be found here, more to follow.

I implemented the basic PSO and applied it to the Goldstein-Price function (in 2D). In about 160  iterations, PSO is able to get to the global minimum within machine precision.

AM225 Final Project, Spring 2018:

Multigrid-Precondition Conjugate Gradient

Since I was dong two solo final projects, one for CS205 and another for this course, working on the same piece of software (the Multigrid solver developed in the Rycroft group), from different aspects, makes a lot of practical sense. AM225 is the second semester continuation of AM205, and focuses on numerical methods for PDEs as well as parallel computing. Therefore, the project was designed to have both theoretical and applied components.

When using multigrid to solve elliptic PDEs that have discontinuous coefficients, it is known that, to ensure the convergence properties of multigrid, the interpolation and restriction operations need to be modify to avoid applying these operators across the discontinuity. Another way to use multigrid would be to use it as a preconditioner to other iterative methods, such as conjugate gradient.

If a matrix is symmetric positive definite (SPD), it can be used as a preconditioner for conjugate gradient (CG). In the multigrid solver, we use both Jacobi and Gauss-Seidel (GS) iterative methods. Since Gauss-Seidel has better convergence properties, we prefer to use GS most of the time. I set out to show that performing natural order GS in a forward sweep, followed by a backward sweep, in fact results in a SPD matrix. Then, I implemented, tested, and compared the convergence multigrid preconditioned conjugate gradient (MGPCG) to multigrid on some discontinuous problems. A written report can be found here.

CS205 Final Project, Spring 2018:

Hybrid Parallelization of Custom Multigrid Linear Solver, via MPI, OpenMP, and GPU acceleration

multigrid_schematicFor the final project of CS205: Computing Foundations for Computational Science, I work on adding hybrid parallelism to the multigrid solver developed by the Rycroft group.

Multigrid is an iterative algorithm for solving a linear matrix equation, \mathbf A \mathbf x = \mathbf b. If the matrix is very large, direct methods, such as LU decomposition,  having \mathcal{O}(n^3) complexity, could be infeasible. Direct methods  can also turn a sparse matrix into a dense due to fill-ins, hence inefficient in memory usage.

By using multigrid method, we can reduce time complexity to \mathcal{O}(n), as well as preserve and exploit the sparsity in the problem. In this post, I give a detailed report on this project, covering what multigrid is in a nutshell, the research problem that it can be applied to, and the effects of adding OpenMP and GPU accelerations on the existing MPI implementation.

AM205 Final Project, Fall 2016 :

Modeling Patterns on Shells of Mollusks with Reaction-Diffusion Equations

I was reading a book I borrowed from a friend, called The Self-made Tapestry: Pattern Formation in Nature, written by Phillip Ball, when it was time to form a final project group and brainstorm for ideas. I had just learned about reaction-diffusion equations and the patterns that they can produce in the book, and thought it will be cool to simulate these equations, and learn something about solving nonlinear PDEs and about some basic pattern formations. My project teammates, Lindsey Brown and Siheng Chen, and I decided to (1) model seashell patterns using the Meinhardt formulation; (2) develop techniques to automatically detect and classify patterns; (3) explore and analyze the parameter space that give rise to detectable patterns. A written report can be found here.