×

Probabilistic bounds for the matrix condition number with extended Lanczos bidiagonalization. (English) Zbl 1325.65051

Summary: Reliable estimates for the condition number of a large, sparse, real matrix \(A\) are important in many applications. To get an approximation for the condition number \(\kappa(A)\), an approximation for the smallest singular value is needed. Standard Krylov subspaces are usually unsuitable for finding a good approximation to the smallest singular value. Therefore, we study extended Krylov subspaces which turn out to be ideal for the simultaneous approximation of both the smallest and largest singular value of a matrix. First, we develop a new extended Lanczos bidiagonalization method. With this method we obtain a lower bound for the condition number. Moreover, the method also yields probabilistic upper bounds for \(\kappa(A)\). The user can select the probability with which the upper bound holds, as well as the ratio of the probabilistic upper bound and the lower bound.

MSC:

65F15 Numerical computation of eigenvalues and eigenvectors of matrices
65F35 Numerical computation of matrix norms, conditioning, scaling
65F50 Computational methods for sparse matrices
65F10 Iterative numerical methods for linear systems
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] T. A. Davis and Y. Hu, {\it The University of Florida sparse matrix collection}, ACM Trans. Math. Software, 38 (2011), article 1. · Zbl 1365.65123
[2] J. D. Dixon, {\it Estimating extremal eigenvalues and condition numbers of matrices}, SIAM J. Numer. Anal., 20 (1983), pp. 812-814. · Zbl 0536.65022
[3] V. L. Druskin and L. A. Knizhnerman, {\it Extended Krylov subspaces: Approximation of the matrix square root and related functions}, SIAM J. Matrix Anal. Appl., 19 (1998), pp. 755-771. · Zbl 0912.65022
[4] The University of Florida Sparse Matrix Collection, {\it A Repository for Test Matrices}, www.cise.ufl.edu/research/sparse/matrices/.
[5] G. Golub and W. Kahan, {\it Calculating the singular values and pseudo-inverse of a matrix}, J. Soc. Indust. Appl. Math. Ser. B Numer. Anal., 2 (1965), pp. 205-224. · Zbl 0194.18201
[6] T. Gudmundsson, C. S. Kenney, and A. J. Laub, {\it Small-sample statistical estimates for matrix norms}, SIAM J. Matrix Anal. Appl., 16 (1995), pp. 776-792. · Zbl 0831.65051
[7] N. Halko, P. G. Martinsson, and J. A. Tropp, {\it Finding structures with randomness: Probabilistic algorithms for constructing approximate matrix decompositions}, SIAM Rev., 53 (2011), pp. 217-288. · Zbl 1269.65043
[8] N. J. Higham and F. Tisseur, {\it A block algorithm for matrix \(1\)-norm estimation, with an application to \(1\)-norm pseudospectra}, SIAM J. Matrix Anal. Appl., 21 (2000), pp. 1185-1201. · Zbl 0959.65061
[9] M. E. Hochstenbach, {\it A Jacobi-Davidson type SVD method}, SIAM J. Sci. Comput., 23 (2001), pp. 606-628. · Zbl 1002.65048
[10] M. E. Hochstenbach, {\it Harmonic and refined extraction methods for the singular value problem, with applications in least squares problems}, BIT, 44 (2004), pp. 721-754. · Zbl 1079.65047
[11] M. E. Hochstenbach, {\it Probabilistic upper bounds for the matrix two-norm}, J. Sci. Comput., 57 (2013), pp. 464-476. · Zbl 1292.65037
[12] R. A. Horn and C. R. Johnson, {\it Topics in Matrix Analysis}, Cambridge University Press, Cambridge, UK, 1991. · Zbl 0729.15001
[13] C. Jagels and L. Reichel, {\it The extended Krylov subspace method and orthogonal Laurent polynomials}, Linear Algebra Appl., 431 (2009), pp. 441-458. · Zbl 1166.65019
[14] C. Jagels and L. Reichel, {\it Recursion relations for the extended Krylov subspace method}, Linear Algebra Appl., 434 (2011), pp. 1716-1732. · Zbl 1211.65039
[15] E. R. Jessup and I. C. F. Ipsen, {\it Improving the accuracy of inverse iteration}, SIAM J. Sci. Statist. Comput., 13 (1992), pp. 550-572. · Zbl 0758.65032
[16] L. Knizhnerman and V. Simoncini, {\it A new investigation of the extended Krylov subspace method for matrix function evaluations}, Numer. Linear Algebra Appl., 17 (2010), pp. 615-638. · Zbl 1240.65154
[17] J. Kuczyński and H. Woźniakowski, {\it Estimating the largest eigenvalue by the power and Lanczos algorithms with a random start}, SIAM J. Matrix Anal. Appl., 13 (1992), pp. 1094-1122. · Zbl 0759.65016
[18] The Matrix Market, \burlmath.nist.gov/MatrixMarket, a repository for test matrices.
[19] B. N. Parlett, {\it The Symmetric Eigenvalue Problem}, Classics Appl. Math. 20 SIAM, Philadelphia, 1998. · Zbl 0885.65039
[20] V. Simoncini, {\it A new iterative method for solving large-scale Lyapunov matrix equations}, SIAM J. Sci. Comput., 29 (2007), pp. 1268-1288. · Zbl 1146.65038
[21] J. L. M. van Dorsselaer, M. E. Hochstenbach, and H. A. van der Vorst, {\it Computing probabilistic bounds for extreme eigenvalues of symmetric matrices with the Lanczos method}, SIAM J. Matrix Anal. Appl., 22 (2000), pp. 837-852. · Zbl 0981.65044
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.