NUMERICAL EQUIVALENCES AMONG KRYLOV SUBSPACE ALGORITHMS FOR SKEW-SYMMETRIC MATRICES

作者：Greif C^*; Paige C C; Titley Peloquin D; Varah J M

来源：SIAM Journal on Matrix Analysis and Applications, 2016, 37(3): 1071-1087.

DOI：10.1137/15M1030078

• Krylov subspace methods
• skew-symmetric systems
• Lanczos tridiagonalization
• Golub-Kahan bidiagonalization
• CGNE
• Craig's method
• CGNR
• LSQR
• LSMR

We briefly review Krylov subspace methods based on the Galerkin and minimum residual conditions for solving Ax = b with real A and b, followed by two implementations: the conjugate gradient (CG) based methods CGNE and CGNR. We then show the numerical equivalence of Lanczos tridiagonalization and Golub-Kahan bidiagonalization for any real skew-symmetric matrix A. We give short derivations of two algorithms for solving Ax = b with skew-symmetric A and use the above equivalence to show that these are numerically equivalent to the Golub-Kahan bidiagonalization variants of CGNE and CGNR. These last two numerical equivalences add to the theoretical equivalences in the work by Eisenstat [Equivalence of Krylov Subspace Methods for Skew-Symmetric Linear Systems, Department of Computer Science, Yale University, preprint, arXiv: 1512.00311, 2015] that unified and extended earlier work. We next present a method based on the Lanczos tridiagonalization process for minimizing parallel to A(T) (b - Ax(k))parallel to(2) when A(T) = -A and show that for skew-symmetric systems it is numerically equivalent to LSMR developed by Fong and Saunders [SIAM J. Sci. Comput., 33 (2011), pp. 2950-2971]. Finally, we illustrate the typical convergence behaviors of these algorithms with a numerical example and use these and an analysis to give new insights into algorithm choices for general large sparse matrix solution of equations problems.

• 出版日期2016
• 单位McGill