I am an Assistant Professor in the Department of Mathematics at Emory University. My research interests include numerical linear algebra and high performance computing. My current research is supported by NSF OAC 2003720.

Office: Mathematics and Science Center, Room E428

Phone: 1-404-727-3638

Email: yxi26@emory.edu

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.

Related References:

- Y. Xi and J. Xia, On the stability of some hierarchical rank structured matrix alogrithms, SIAM J. Matrix Anal. Appl., 37 (2016), pp. 1279-1303. (Journal article link)
- J. Xia, Y. Xi, S. Cauley, and V. Balakrishnan, Fast sparse selected inversion, SIAM J. Matrix Anal. Appl., 36 (2015), pp. 1283-1314. (Journal article link)
- 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)
- Y. Xi, J. Xia, and R. Chan, A fast randomized eigensolver with structured LDL factorization update, SIAM J. Matrix Anal. Appl., 35 (2014), pp. 974-996. (Journal article link)
- Y. Xi, J. Xia, S. Cauley, and V. Balakrishnan, Superfast and stable structured solvers for Toeplitz least squares via randomized sampling, SIAM J. Matrix Anal. Appl., 35 (2014), pp. 44-72. (Journal article link)
- J. Xia, Y. Xi, and M. Gu, A superfast structured solver for Toeplitz linear systems via randomized sampling, SIAM J. Matrix Anal. Appl., 33 (2012), pp. 837-858. (Journal article link)
- SMASH: Structured matrix approximation by separation and hierarchy, with D. Cai, E. Chow and Y. Saad, submitted to Numer. Linear Algebra Appl., 2017.
- Efficient solution methods for kernel systems in machine learning, with D. Cai, E. Chow, L. Erlandson and Y. Saad, preprint, 2017.

Preconditioning indefinite sparse linear systems

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.

Related References:

- Y. Xi and Y. Saad, A rational function preconditioner for indefinite sparse linear systems, SIAM J. Sci. Comput., 39 (2017), pp. A1145-A1167.(Journal article link)
- Y. Xi, R. Li, and Y. Saad, An algebraic multilevel preconditioner with low-rank corrections for sparse symmetric matrices, SIAM J. Matrix Anal. Appl., 37 (2016), pp. 235-259. (Journal article link)
- R. Li, Y. Xi, and Y. Saad, Schur complement based domain decomposition preconditioners with low-rank corrections, Numer. Linear Algebra Appl., 23(4) (2016), pp. 706-729. (Journal article link)
- G. Dillon, V. Kalantzis, Y. Xia, and Y. Saad,A hierarchical low-rank Schur complement preconditioner for indefinite linear systems, SIAM J. Sci. Comput., SIAM J. Sci. Comput., SIAM J. Sci. Comput. 40-4 (2018), pp. A2234-A2252. (Journal article link)

Spectrum-slicing eigensolvers

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.

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.

Related References:

- Y. Xi and Y. Saad, Computing partial spectra with least-squares rational filters, SIAM J. Sci. Comput., 38 (2016), pp. A3020-A3045.(Journal article link)
- R. Li, Y. Xi, E. Vecharynski, C. Yang and Y. Saad, A Thick-Restart Lanczos algorithm with polynomial filtering for Hermitian eigenvalue problems, SIAM J. Sci. Comput., 38 (2016), pp. A2512-A2534. (Journal article link)
- V. Kalantzis, Y. Xi and Y. Saad, Beyond AMLS: Domain Decomposition with rational filtering, SIAM J. Sci. Comput., 40 (2018), pp. C477-C502.(Journal article link)
- 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.
- EVSL: Eigenvalues slicing library: Algorithms, methods and software description, with L. Erlandson, R. Li and Y. Saad, preprint, 2017.

Spectral graph 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.

Related References:

- Fast computation of spectral densities for generalized eigenvalue problems, with R. Li and Y. Saad, submitted to SIAM J. Sci. Comput., 2017.

Published (Google Scholar)

- H. He, Y. Xi and J. Ho, Fast and Accurate Tensor Decomposotion without a High Performance Computing Machine, 2020 IEEE International Conference on Big Data.
- X. Chen, J. Herrig, J. Nagy, Y. Xi and B. Yu, An ADMM-LAP method for total variation myopic deconvolution of adaptive optics retinal images, Inverse Problems, 2020.(Journal article link)
- Q. Zheng, Y. Xi and Y. Saad, Multi-Color Low-Rank preconditioner for general sparse linear systems, Numer. Linear Algebra Appl., 2020, 27:e2316.(Journal article link)
- L. Erlandson, D. Cai, Y. Xi and E. Chow, Accelerating Parallel Hierarchical Matrix-Vector Products via Data-Driven Sampling, 34th IEEE International Parallel and Distributed Processing Symposium (IPDPS), New Orleans, LA, 2020.
- X. Liu, Y. Xi, Y. Saad and M. de Hoop, Solving the 3D high-frequency Helmholtz equation using contour integration and polynomial preconditioning, SIAM J. Matrix Anal. Appl., 41 (2020), pp. 58-82.(Journal article link)
- Z. Chen, J. Nagy, Y. Xi and B. Yu, Structured FISTA for image restoration, Numer. Linear Algebra Appl. e2278, (2019).(Journal article link)
- R. Li, Y. Xi, L. Erlandson and Y. Saad, EVSL: Eigenvalues slicing library: Algorithms, methods and software description, SIAM J. Sci. Comput., 41 (2019), pp. C393-C415.(Journal article link)
- Y. Xi, R. Li and Y. Saad, Fast computation of spectral densities for generalized eigenvalue problems, SIAM J. Sci. Comput., 40 (2018), pp. A2749-A2773.(Journal article link)
- J. Shi, R. Li, Y. Xi, Y. Saad and M.V. de Hoop, Computing Planetary Interior Normal Modes with A Highly Parallel Polynomial Filtering Eigensolver, International Conference for High Performance Computing, Networking, Storage, and Analysis (SC18), Dallas, TX, Nov. 11-16, 2018.
- D. Cai, E. Chow, L. Erlandson, Y. Saad and Y. Xi, SMASH: Structured matrix approximation by separation and hierarchy, Numer. Linear Algebra Appl., 25(6) (2018).(Journal article link)
- G. Dillon, V. Kalantzis, Y. Xi and Y. Saad, A hierarchical low-rank Schur complement preconditioner for indefinite linear systems, SIAM J. Sci. Comput. 40-4 (2018), pp. A2234-A2252. (Journal article link)
- V. Kalantzis, Y. Xi and Y. Saad, Beyond AMLS: Domain Decomposition with rational filtering, SIAM J. Sci. Comput., 40 (2018), pp. C477-C502.(Journal article link)
- Y. Xi and Y. Saad, A rational function preconditioner for indefinite sparse linear systems, SIAM J. Sci. Comput., 39 (2017), pp. A1145-A1167.(Journal article link)
- Y. Xi and Y. Saad, Computing partial spectra with least-squares rational filters, SIAM J. Sci. Comput., 38 (2016), pp. A3020-A3045.(Journal article link)
- Y. Xi and J. Xia, On the stability of some hierarchical rank structured matrix alogrithms, SIAM J. Matrix Anal. Appl., 37 (2016), pp. 1279-1303. (Journal article link)
- R. Li, Y. Xi, E. Vecharynski, C. Yang and Y. Saad, A Thick-Restart Lanczos algorithm with polynomial filtering for Hermitian eigenvalue problems, SIAM J. Sci. Comput., 38 (2016), pp. A2512-A2534. (Journal article link)
- R. Li, Y. Xi, and Y. Saad, Schur complement based domain decomposition preconditioners with low-rank corrections, Numer. Linear Algebra Appl., 23(4) (2016), pp. 706-729. (Journal article link)
- Y. Xi, R. Li, and Y. Saad, An algebraic multilevel preconditioner with low-rank corrections for sparse symmetric matrices, SIAM J. Matrix Anal. Appl., 37 (2016), pp. 235-259. (Journal article link)
- J. Xia, Y. Xi, S. Cauley, and V. Balakrishnan, Fast sparse selected inversion, SIAM J. Matrix Anal. Appl., 36 (2015), pp. 1283-1314. (Journal article link)
- 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)
- Y. Xi, J. Xia, and R. Chan, A fast randomized eigensolver with structured LDL factorization update, SIAM J. Matrix Anal. Appl., 35 (2014), pp. 974-996. (Journal article link)
- Y. Xi, J. Xia, S. Cauley, and V. Balakrishnan, Superfast and stable structured solvers for Toeplitz least squares via randomized sampling, SIAM J. Matrix Anal. Appl., 35 (2014), pp. 44-72. (Journal article link)
- J. Xia, Y. Xi, and M. Gu, A superfast structured solver for Toeplitz linear systems via randomized sampling, SIAM J. Matrix Anal. Appl., 33 (2012), pp. 837-858. (Journal article link)

Submitted

- A Rayleigh-Ritz method based approach to computing seismic normal modes in the presence of an essential spectrum, with J. Shi, R. Li, Y. Saad and M. de Hoop, submitted, 2019.
- Preconditioning via GMRES in polynomial space, with X. Ye and Y. Saad, submitted, 2020.
- A power Schur complement low-rank correction preconditioner for general sparse linear systems, with Q. Zheng and Y. Saad, submitted, 2020.
- Fast non-Hermitian eigensolvers based on rational filtering and matrix partitioning, with V. Kalantzis and L. Horesh, submitted, 2020.
- Anchor Net: Unraveling data geometry and efficient approximation of high dimensional kernel matrices, with D. Cai and J. Nagy, submitted, 2020.
- Planetary normal mode computation: Parallel algorithms, performance, and reproducibility, with J. Shi, R. Li, Y. Saad and M. de Hoop, submitted, 2020.

Teaching at Emory:

- Math 315. Numerical Analysis (Fall 2019, Spring 2020)
- Math 517. Iterative Methods for Linear Systems (Spring 2019)
- Math 515. Numerical Analysis I (Fall 2018, 2019)

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

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

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.