Research Summary of Andrew Knyazev, Math Dept UC Denver

Research Accomplishments by Andrew Knyazev, Dept. of Mathematics UC Denver

My research has mostly been in three different areas of numerical mathematics: development and analysis of preconditioned iterative methods for large symmetric eigenvalue problems, the Rayleigh-Ritz method and two-sided bounds for eigenvalues, and numerical solution of elliptic problems with highly discontinuous coefficients.

The study of preconditioners for iterative methods for solving large linear systems of equations has become a major focus of numerical analysts and engineers. For eigenvalue computations, preconditioning is much more difficult. Among my accomplishments in the area are:

a new iterative method, a preconditioned locally optimal block conjugate gradient method for sparse symmetric generalized eigenproblems [1,2], possibly the optimal method in the class of polynomial preconditioned eigensolvers,
a formal definition of preconditioned eigensolvers and a systematic classification, separating the choice of a preconditioner from the choice of an iterative method [1,2,6],
sharp convergence estimates for a variety of preconditioned eigensolvers [1,2,5,8,10],
an optimal strategy for inner iterations of the inner-outer preconditioned Lanczos method [10],
a new class of domain decomposition methods, with and without an overlap, with optimal convergence [6,8].

The Rayleigh-Ritz method is a classical method of approximation of symmetric eigenvalue problems. I proved in [4,10] new sharp error estimates for the method and found in [4] that a Ritz vector is super-orthogonal to eigenvectors well approximated by a trial subspace. The Rayleigh-Ritz method provides approximation of the spectrum from the inside; outside bounds are also of a great interest and can be found using the Temple-Lehmann method which is considered to be one of the most effective methods for two-sided estimating of eigenvalues. I derived sharp a priori error estimates of the method, similar to those of the Rayleigh-Ritz method, and proved that the approximations to eigenvectors in the Temple-Lehmann and the Rayleigh-Ritz methods are asymptotically the same, [10].

Elliptic problems with highly discontinuous coefficients are hard to solve numerically as they are not uniformly well posed with respect to the jump in the coefficients. However, in a series of joint papers with N. Bakhvalov, see [7,9] and references there, a natural implicit splitting of the original problem with jumps into two well-posed problems was suggested. Based on this idea, a uniform convergence of a preconditioned iterative method with a special initial guess was proved in [7,9]. Preconditioned iterative algorithms for solving Stokes and Lame equations with large jumps in the coefficients were suggested in [9], where some results from [7] were extended to incompressible and nearly incompressible medium. For the Lame equations, the case of absolutely compressible media has been also covered [9].

All previously mentioned results were on uniform convergence of iterative methods for differential equations with rough coefficients. Standard Finite Element error estimates for such problems deteriorate when the jumps in coefficients gets larger as the constant goes to infinity. In [3], under some natural assumptions we obtained a somewhat surprising error estimate with a constant uniform in the jump. We also proved a novel regularity result uniform in the jump of the coefficients.

Two books (in Russian) and more than 30 papers and reports were published.

My research in the near future will concern:

parallel implementations of the Locally Optimal Block Preconditioned Conjugate Gradient (LOBPCG) method in Hypre and PETSc and applications of the method in different areas of engineering;
development of the LOBPCG-like methods for nonsymmetric and nonlinear eigenvalue computations using the PLTMG package by Randolph Bank;
development of eigensolvers for electronic structure calculations and their implementation in real and plane wave software packages, such as ABINIT.
computation of angles between subspaces and their applications in data mining and DNA microarray system data analysis using spectral clustering and biclustering;
development of new fast algorithms for data clustering with applications to image segmentation and registration.
Mixed FEM and iterative solution of PDEs with highly discontinuous coefficients and thier applications in geosciences.

Publications -- ten most relevant/recent:

1. ``Toward the Optimal Preconditioned Eigensolver: Locally Optimal Block Preconditioned Conjugate Gradient Method.'' SIAM Journal on Scientific Computing 23 (2001), no. 2, pp. 517-541.

2. ``Preconditioned eigensolvers.'' In Templates for the Solution of Algebraic Eigenvalue Problems: A Practical Guide. Editors: Zhaojun Bai, James Demmel, Jack Dongarra, Axel Ruhe, and Henk Van der Vorst, SIAM, pp. 337-368, 2000.

3. ''Lavrentiev Regularization + Ritz Approximation = Uniform Finite Element Error Estimates for Differential Equations with Rough Coefficients,'' with Olof Widlund. Math. Comp., 72 (2003), 17-40.

4. ``New estimates for Ritz vectors,'' Math. Comp. 66 (1997), no. 219, 985-995.

5. ``A geometric theory for preconditioned inverse iteration. III: A short and sharp convergence estimate for generalized eigenvalue problems,'' with Klaus Neymeyr, Linear Algebra and Its Applications, 358 (2003), Issues 1-3, 95-114.

6. `` Preconditioned eigensolvers - an oxymoron?,'' ETNA 7 (1998), 104-123.

7. ``Fictitious domain methods and computation of homogenized properties of composites with a periodic structure of essentially different components,'' with N. S. Bakhvalov. In Numerical Methods and Applications, Ed. Gury I. Marchuk, CRC Press, 221-276, 1994.

8. ``The preconditioned gradient-type iterative methods in a subspace for partial generalized symmetric eigenvalue problem,'' with A. L. Skorokhodov. SIAM J. Num. Anal., 31 (1994), no. 4, 1226-1239.

9. `` An Efficient Iterative Method for solving Lame equations for nearly incompressible media and Stokes equations with highly discontinuous coefficients,'' with N. S. Bakhvalov and R. R. Parashkevov. Numerical Linear Algebra with Applications, 9 (2002), no. 2, 115-139.

10. ``Computation of eigenvalues and eigenvectors for mesh problems: algorithms and error estimates.'' Monograph Dept. Num. Math. USSR Ac. Sci., Moscow, 1986, 187 pp. (in Russian). A condensed survey in English: ``Convergence rate estimates for iterative methods for mesh symmetric eigenvalue problem.'' Sov. J. Num. Anal. Math. Modeling, 2 (1987), N 5, p. 371--396.