I am an Assistant Professor in the Department of Mathematics at Emory University. My research interests include numerical linear algebra and high performance computing.
Office: Mathematics and Science Center, Room E428
Phone: 1-404-727-3638
Email: yxi26@emory.edu
Scientific computing and data analytics are nowadays the third and fourth pillars for scientific discovery. However, the ever-growing size of these problems makes many classical computational tools inefficient up to a certain scale. My research interests include the development of fast algorithms by studying the inherent mathematical structures of the underlying problem and the implementation of these algorithms into high performance computing mathematical software.
Fast structured dense solvers
Fully dense linear systems often appear in scientific computing and data analytics problems, e.g., numerical solutions of integral equations, kernel methods for nonparametric modeling and semi-supervised learning. The power of these methods is often limited to moderate sized problems due to quadratic cost in storage and cubic cost in solution. By exploiting the separability of the associated kernel functions, we have proposed several nearly linear complexity algebraic solvers for different scenarios. These fast solvers hierarchically partition the row and column indexes of the coefficient matrix and compress certain off-diagonal blocks into low-rank forms. We are now working on the extension of these methods for high-dimensional data analytics and vector valued kernels.
Indefinite sparse linear systems appear frequently in high frequency wave scattering simulation, interior eigenvalue computations and mixed finite element formulation of fluid and solid mechanics problems. Since the spectrum of the coefficient matrix lies on both sides of the y-axis in the complex plane, these problems are much harder to solve by iterative methods than definite linear systems. We have developed several robust preconditioning techniques to tackle these challenging problems. In particular, the proposed fast contour integral preconditioner (FCI) could achieve frequency-independent convergence for solving 3D Helmholtz equations discretized on regular grids. We are now working on the linear complexity algorithms for updating the FCI preconditioner when solving a sequence of Helmholtz equations discretized on the same FEM mesh but with different frequencies.
In quantum physics/chemistry, it often needs to compute thousands of eigenvalues and their associated eigenvectors of very large matrices. One example is solving the Kohn-Sham equation for determining the electronic structure of atoms and condensed matter systems in density functional theory：
Most existing eigensolvers scale cubically for this problem. We have developed a new breed of eigensolvers that exploit “spectrum slicing” principles. These eigenvectors could partition the desired parts of the spectrum into non-overlapping slices and compute the eigenvalues located inside each slice independently from one other. In collaboration with geophysicists from Rice University, we are now applying these eigensolvers to directly compute the earth’s normal modes (generalized eigenvalue problems with size upto one billion) for the first time in history. This research would be able to help understand the earth’s response to earthquakes and post-seismic imaging.
J. Shi, M. V. de Hoop, R. Li, Y. Xi, and Y. Saad, Fast eigensolver for computing earth’s normal modes, in Proceedings of the Project Review, Geo-Mathematical Imaging Group, vol. 2, 2017, pp. 317–345.
In mathematics, spectral graph theory studies the properties of a graph in relationship to the spectrum of the matrix associated with the graph. In particular, the distribution of the eigenvalues often reveals important features of the underlying problem, whether a Hamiltonian system in physics, or a social network in behavioral sciences. However, computing all the eigenvalues explicitly usually has cubic complexity and thus is prohibitively expensive for real-world applications. We exploit the concept of density of states to propose almost linear complexity algorithms to approximate the eigenvalue distribution accurately. We are now applying these methods to analyze the social networks.
S. Cauley, Y. Xi, B. Bilgic, J. Xia, E. Adalsteinsson, V. Balakrishnan, L. Wald, and K. Setsompop, Fast reconstruction for multi-channel compressed sensing using a hierarchically semiseparable solver, Magn. Reson. Med., 73 (2015), pp. 1034-1040. (Journal article link)
Math 517. Iterative Methods for Linear Systems (Spring 2019)
Math 515. Numerical Analysis I (Fall 2018)
Past courses taught at the University of Minnesota:
CSCI 8314 Sparse Matrix Computation (Spring 2017)
Past courses taught at Purdue:
MA 514 Numerical Analysis
MA154 Plane Analytic Geometry And Calculus I
MA161 Multivariate Calculus
MA261 Multivariate Calculus
Presentations
Invited Presentations
Multilevel low-rank correction preconditioning techniques, Copper Mountain, CO, USA, March 2018
Exploiting data-sparse structures in large-scale computations, Arlington, TX, USA, April 2017
Exploiting data-sparse structures in numerical linear algebra, IMA data science seminar, Minneapolis, MN, USA, April 2017
Polynomial and rational filtering for eigenvalue problems, SIAM CSE Conference, Atlanta, GA, USA, March 2017
Exploiting data-sparse structures in numerical linear algebra, Michigan State University, East Lansing, MI, USA, February 2017
Exploiting data-sparse structures in scientific computing, The Ohio State University, Columbus, OH, USA, November 2016
CCAM Lunch Seminar, Purdue University, West Lafayette, IN, USA, November 2016
Polynomial and rational filtering for eigenvalue problems, CCAM special lecture, Rice University, Houston, TX, USA, September 2016
A rational function preconditioner for highly indefinite sparse matrices, Geo-Mathematical Imaging Group Project Review and Advisory Board Meeting, Rice University, Houston, TX, USA, April 2016
An arbitrary inversion algorithm for general sparse matrices, SIAM Annual Meeting, San Diego, CA, USA, July 2013
Afast selected inversionfor general sparsematrices, Geo-Mathematical Imaging Group Project Review and Advisory Board Meeting, Chicago, IL, USA, April 2013
A fast eigensolver for discretized PDE from irregular mesh, Geo-Mathematical Imaging Group Project Review and Advisory Board Meeting, Purdue University, West Lafayette, IN, USA, April 2012
Contributed Talks
Ten reasons to love EVSL, FEAST group meeting, Minneapolis, MN, USA, July 2017
Fast contour-integral preconditioner, Workshop on Fast Direct Solvers, CCAM, Purdue University, West Lafayette, IN, USA, November 2016
A rational function preconditioner for indefinite sparse linear systems, SIAM Annual Meeting, Boston, MA, USA, July 2016
Spectrum slicing by polynomial and rational function filtering, SIAM Annual Meeting, Boston, MA, USA, July 2016
Spectrum slicing by polynomial and rational function filtering, Midwest Numerical Analysis Day, La Crosse, WI, USA, April 2016
An algebraic multilevel preconditioner with low-rank corrections for sparse symmetric matrices, SIAM conference on Applied Linear Algebra, Atlanta, GA, USA, October 2015
Superfast algorithms for Toeplitz matrices, New Frontiers in Numerical Analysis and Scientific Computing, Kent State University, Kent, OH, USA, April 2013
Superfast algorithms for Toeplitz problems, 4th SIAM Annual Computational Science and Engineering Student Conference (CSESC), Purdue University, West Lafayette, IN, USA, April 2012
A superfast and stable solver for Toeplitz linear systems via randomized sampling, Midwest Numerical Analysis Day, Purdue University, West Lafayette, IN, USA, May 2011
Software
Eigenvalues slicing library (EVSL)
EVSL is a C library for computing the eigenvalues of a symmetric matrix pencil that are located in a given interval. EVSL also provides tools for spectrum slicing, i.e., the technique of subdividing a given interval into p smaller subintervals and computing the eigenvalues in each subinterval independently, as well as Kernel Polynomial method (KPM) and Lanczos based density of states/spectral density estimators. EVSL implements a polynomial filtered Lanczos (thick restart, no restart) a rational filtered Lanczos (thick restart, no restart), and a polynomial filtered subspace iteration for solving standard eigenvalue problems A u = λ u and generalized eigenvalue problems A u = λ B u. The latest version can be downloaded here.
SMASH package (to be posted)
SMASH is a C++ library for efficiently performing structured dense matrix operations. The matrix A considered here is generated by a set of points {Xk} and a kernel function g such that Ai,j = g(Xi, Xj). In the current release, we only provide routines for performing matrix-vector multiplications for 2D/3D cases. SMASH can also be integrated into EVSL package (through the matrix-free interface) for computing the eigenvalues of these kernel matrices. We are now extending this package for vector valued kernels and high dimensional data analysis.
Superfast and stable Toeplitz direct solvers
This package is a Fortran library for solving Toeplitz linear systems. It uses randomization and hierarchically semiseparable (HSS) methods to reduce the computational complexity to be nearly linear and has provable numerical stability. The package can be downloaded here.
Fully dense linear systems often appear in scientific computing and data analytics problems, e.g., numerical solutions of integral equations, kernel methods for nonparametric modeling and semi-supervised learning. The power of these methods is often limited to moderate sized problems due to quadratic cost in storage and cubic cost in solution. By exploiting the separability of the associated kernel functions, we have proposed several nearly linear complexity algebraic solvers for different scenarios. These fast solvers hierarchically partition the row and column indexes of the coefficient matrix and compress certain off-diagonal blocks into low-rank forms. We are now working on the extension of these methods for high-dimensional data analytics and vector valued kernels.
Indefinite sparse linear systems appear frequently in high frequency wave scattering simulation, interior eigenvalue computations and mixed finite element formulation of fluid and solid mechanics problems. Since the spectrum of the coefficient matrix lies on both sides of the y-axis in the complex plane, these problems are much harder to solve by iterative methods than definite linear systems. We have developed several robust preconditioning techniques to tackle these challenging problems. In particular, the proposed fast contour integral preconditioner (FCI) could achieve frequency-independent convergence for solving 3D Helmholtz equations discretized on regular grids. We are now working on the linear complexity algorithms for updating the FCI preconditioner when solving a sequence of Helmholtz equations discretized on the same FEM mesh but with different frequencies.
In quantum physics/chemistry, it often needs to compute thousands of eigenvalues and their associated eigenvectors of very large matrices. One example is solving the Kohn-Sham equation for determining the electronic structure of atoms and condensed matter systems in density functional theory：
In mathematics, spectral graph theory studies the properties of a graph in relationship to the spectrum of the matrix associated with the graph. In particular, the distribution of the eigenvalues often reveals important features of the underlying problem, whether a Hamiltonian system in physics, or a social network in behavioral sciences. However, computing all the eigenvalues explicitly usually has cubic complexity and thus is prohibitively expensive for real-world applications. We exploit the concept of density of states to propose almost linear complexity algorithms to approximate the eigenvalue distribution accurately. We are now applying these methods to analyze the social networks.
EVSL is a C library for computing the eigenvalues of a symmetric matrix pencil that are located in a given interval. EVSL also provides tools for spectrum slicing, i.e., the technique of subdividing a given interval into p smaller subintervals and computing the eigenvalues in each subinterval independently, as well as Kernel Polynomial method (KPM) and Lanczos based density of states/spectral density estimators. EVSL implements a polynomial filtered Lanczos (thick restart, no restart) a rational filtered Lanczos (thick restart, no restart), and a polynomial filtered subspace iteration for solving standard eigenvalue problems A u = λ u and generalized eigenvalue problems A u = λ B u. The latest version can be downloaded here.