Meiyue Shao

The locally optimal block preconditioned conjugate gradient (LOBPCG) algorithm is a popular approach for computing a few smallest eigenvalues and the corresponding eigenvectors of a large Hermitian positive definite matrix A. In this work, we propose a mixed precision variant of LOBPCG that uses a (sparse) Cholesky factorization of A computed in lower precision as the preconditioner. To further enhance performance, a mixed precision orthogonalization strategy is proposed. To analyze the impact of reducing precision in the preconditioner on performance, we carry out a rounding error and convergence analysis of PINVIT, a simplified variant of LOBPCG. Our theoretical results predict and our numerical experiments confirm that the impact on convergence remains marginal. In practice, our mixed precision LOBPCG algorithm typically reduces the computation time by a factor of 1.4-2.0 on both CPUs and GPUs.

SPRINGER2023

Algorithm 953: Parallel Library Software for the Multishift QR Algorithm with Aggressive Early Deflation

Bo Kågström, Daniel Kressner, Meiyue Shao

Library software implementing a parallel small-bulge multishift QR algorithm with Aggressive Early Deflation (AED) targeting distributed memory high-performance computing systems is presented. Starting from recent developments of the parallel multishift QR algorithm [Granat et al., SIAM J. Sci. Comput. 32(4), 2010], we describe a number of algorithmic and implementation improvements. These include communication avoiding algorithms via data redistribution and a refined strategy for balancing between multishift QR sweeps and AED. Guidelines concerning several important tunable algorithmic parameters are provided. As a result of these improvements, a computational bottleneck within AED has been removed in the parallel multishift QR algorithm. A performance model is established to explain the scalability behavior of the new parallel multishift QR algorithm. Numerous computational experiments confirm that our new implementation significantly outperforms previous parallel implementations of the QR algorithm.

Assoc Computing Machinery2015

Aggressively Truncated Taylor Series Method For Accurate Computation Of Exponentials Of Essentially Nonnegative Matrices

Meiyue Shao

Small relative perturbations to the entries of an essentially nonnegative matrix introduce small relative errors to entries of its exponential. It is thus desirable to compute the exponential with high componentwise relative accuracy. Taylor series approximation coupled with scaling and squaring is used to compute the exponential of an essentially nonnegative matrix. An a priori componentwise relative error bound of truncation is established, from which one can choose the degree of Taylor series expansion and the scale factor so that the exponential is computed with desired componentwise relative accuracy. To reduce the computational cost, the degree of the Taylor series expansion is chosen small, while the scale factor is chosen sufficiently large to achieve the desired accuracy. The rounding errors in the squaring stage are not serious as squaring is forward stable for nonnegative matrices. We also establish a posteriori componentwise error bounds and derive a novel interval algorithm for the matrix exponential of an essentially nonnegative matrix. Rounding error analysis and numerical experiments demonstrate the efficiency and accuracy of the proposed methods.

Siam Publications2014

An indefinite variant of LOBPCG for definite matrix pencils

Daniel Kressner, Meiyue Shao

In this paper, we propose a novel preconditioned solver for generalized Hermitian eigenvalue problems. More specifically, we address the case of a definite matrix pencil , that is, A, B are Hermitian and there is a shift such that is definite. Our new method can be seen as a variant of the popular LOBPCG method operating in an indefinite inner product. It also turns out to be a generalization of the recently proposed LOBP4DCG method by Bai and Li for solving product eigenvalue problems. Several numerical experiments demonstrate the effectiveness of our method for addressing certain product and quadratic eigenvalue problems.

Springer2014

On the finite section method for computing exponentials of doubly-infinite skew-Hermitian matrices

Meiyue Shao

Computing the exponential of large-scale skew-Hermitian matrices or parts thereof is frequently required in applications. In this work, we consider the task of extracting finite diagonal blocks from a doubly-infinite skew-Hermitian matrix. These matrices usually have unbounded entries which impede the application of many classical techniques from approximation theory. We analyze the decay property of matrix exponentials for several classes of banded skew-Hermitian matrices. Then finite section methods based on the decay property are presented. We use several examples to demonstrate the effectiveness of these methods. (C) 2014 Elsevier Inc. All rights reserved.

Elsevier Science Inc2014

Meiyue Shao

A mixed precision LOBPCG algorithm

Algorithm 953: Parallel Library Software for the Multishift QR Algorithm with Aggressive Early Deflation

Aggressively Truncated Taylor Series Method For Accurate Computation Of Exponentials Of Essentially Nonnegative Matrices

An indefinite variant of LOBPCG for definite matrix pencils

On the finite section method for computing exponentials of doubly-infinite skew-Hermitian matrices

On aggressive early deflation in parallel variants of the QR algorithm

Aggressively Truncated Taylor Series Method For Accurate Computation Of Exponentials Of Essentially Nonnegative Matrices

Algorithm 953: Parallel Library Software for the Multishift QR Algorithm with Aggressive Early Deflation

An indefinite variant of LOBPCG for definite matrix pencils

On the finite section method for computing exponentials of doubly-infinite skew-Hermitian matrices

A mixed precision LOBPCG algorithm

On aggressive early deflation in parallel variants of the QR algorithm