UC Berkeley

The purpose of this work is to improve stability and performance of selected matrix decompositions in numerical linear algebra. Chapter 1 examines the Locally Optimal Block Preconditioned Conjugate Gradient (LOBPCG) algorithm used to compute eigenvector-eigenvalue pairs for large sparse symmetric matrices or symmetric matrix pencils. Modifications are developed and analyzed to improve both performance and reliability. Numerical experiments demonstrate the final algorithm often operates several times faster than competing versions and succeeds in processing difficult matrices for which other versions fail.

Chapters 2 extends the work on symmetric eigenvalue problems by developing an algorithm specialized to resolve eigenpairs in the interior of the spectrum of a symmetric matrix. An new Spectral Target Residual Descent (STRD) algorithm is proposed based on LOBPCG. This algorithm is demonstrated to reduce the number of iterations required to achieve convergence by roughly half. The component subroutines of STRD also have generalized versions to process interior eigenvalues of symmetric matrix pencils.

Chapter 3 explores a variation on the QR decomposition with Column Pivoting using randomized-sampling to process pivoting decisions. Randomized QRCP eliminates the leading order of communication by processing column pivots on a much smaller sample matrix. This produces blocks of column pivots that are processed with BLAS-3 operations on the original matrix. Sample update formulations are explored that allow full matrices to be factorized without re-compressing the matrix after each block iteration. Related low-rank factorizations are also developed and compared in numerical experiments. These experiments show approximation quality for structured matrices to be comparable, and often better than, approximations based on QRCP. Furthermore, performance is shown to be nearly as good as QR without pivoting, which is often an order of magnitude faster than QRCP.