Skip to Main Content


Implementation and Experiments on SDD Solver Based on Spectral Sparsification

Implementation and Experiments on SDD Solver Based on Spectral Sparsification

-research by Dr. Li and students; begun Spring 2010, ongoing-



Solving SDD systems has always been an interesting topic in computational mathematics. When the matrix is sparse, one would expect the algorithm to run efficiently with respect to the amount of nonzero entries. Spielman and Teng developed an SDD solver (ST solver) that runs in nearly linear time. The idea of spectral sparsification and its use in matrix reduction was proposed in their work.

The ST solver solves the SDD system iteratively by the classic Preconditioned Conjugate Gradient method or the Preconditioned Chebyshev Method. The preconditioners are constructed using spectral sparsification in graph theory, which are reduced into smaller size systems by some direct method.

Researchers from CMU recently improved the ST solver by varying the process of sparsification and greatly enhanced the algorithm efficiency.

In our research, we implemented the algorithm by Mathematica and Matlab. Experiments on different types of SDD systems will be conducted to test the robustness and feasibility of the algorithm. The program will be applied to example heat dynamic differential equations. The numerical results will be compared with results obtained from other algorithms.

Computer Simulation of Compound Eyes

Computer Simulation of Compound Eyes

-research by Dr. Li and students; begun Summer 2012, ongoing-


The optics of compound eyes, which are very different from the camera eyes of vertebrates, has interested scientists for more than a century. Visual acuity in compound eyes is dependent on both facet number (larger numbers of facets = larger visual field and smaller interommatidial angles) and facet size (increased facet size = increased photon capture rates and decreased diffraction).

We are interested in setting up a quantitative mathematical model of an eye. This model would allow quantitative assessments of the specific compromises that insects make with respect to regional variation around their eyes. Furthermore, it would provide a model that could be used to evaluate how eyes would respond to different selection pressures.

Student Research Journals