×

A positivity preserving inexact Noda iteration for computing the smallest eigenpair of a large irreducible \(M\)-matrix. (English) Zbl 1320.65055

The paper deals with the numerical computation of the smallest eigenvalue and the associated positive eigenvector of a large irreducible nonsingular \(M\)-matrix. The authors start their considerations from the inverse iteration method, introduced by T. Noda in [Numer. Math. 17, 382–386 (1971; Zbl 0226.65026)], and propose two different inner tolerance strategies for solving the inner linear systems involved. Moreover, they establish a new quadratic convergence result and provide numerical experiments and comparisons with other iterative solvers.

MSC:

65F15 Numerical computation of eigenvalues and eigenvectors of matrices
65F50 Computational methods for sparse matrices
15B48 Positive matrices and their generalizations; cones of matrices

Citations:

Zbl 0226.65026
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Abate, J., Choudhury, L., Whitt, W.: Asymptotics for steady-state tail probabilities in structured Markov queueing models. Commun. Stat. Stoch. Models 1, 99-143 (1994) · Zbl 0801.60082 · doi:10.1080/15326349408807290
[2] AIM@SHAPE: Advanced and innovative models and tools for the development of semantic-based systems for handling, acquiring, and processing knowledge embedded in multidimensional digital objects. http://shapes.aim-at-shape.net · Zbl 0801.60082
[3] Alfa, A.S., Xue, J., Ye, Q.: Accurate computation of the smallest eigenvalue of a diagonally dominant \[M\] M-matrix. Math. Comput. 71, 217-236 (2002) · Zbl 0984.65033 · doi:10.1090/S0025-5718-01-01325-4
[4] Berman, A., Plemmons, R.J.: Nonnegative matrices in the mathematical sciences. In: Classics in Applied Mathematics, Vol. 9. SIAM, Philadelphia (1994) · Zbl 0815.15016
[5] Berns-Müller, J., Graham, I.G., Spence, A.: Inexact inverse iteration for symmetric matrices. Linear Algebra Appl. 416, 389-413 (2006) · Zbl 1101.65037 · doi:10.1016/j.laa.2005.11.019
[6] Collatz, L.: Einchliessungenssatz für die characteristischen Zahlen von Matrizen. Math. Z. 48, 221-226 (1942) · Zbl 0027.00604 · doi:10.1007/BF01180013
[7] DIMACS10: DIMACS10 test set and the University of Florida Sparse Matrix Collection. http://www.cise.ufl.edu/research/sparse/dimacs10/ · Zbl 1269.65036
[8] Elsner, L.: Inverse iteration for calculating the spectral radius of a nonnegative irreducible matrix. Linear Algebra Appl. 15, 235-242 (1976) · Zbl 0359.65030 · doi:10.1016/0024-3795(76)90029-X
[9] Golub, G.H., Van Loan, C.F.: Matrix Computations, 4th edn. The John Hopkins University Press, Baltimore (2012) · Zbl 1268.65037
[10] Gu, X.D., Huang, T.-M., Huang, W.-Q., Lin, S.-S., Lin, W.-W., Yau, S.-T.: High performance computing for spherical conformal and Riemann mappings. In: Technical Report, Department of Applied Mathematics, National Chiao Tung University, Taiwan (2013) · Zbl 1312.65054
[11] Hernández, V., Román, J.E., Tomás, A., Vidal, V.: Krylov-Schur methods in SLEPc. In: SLEPc Technical Report STR-7 (2007). http://www.grycap.upv.es/slepc · Zbl 0763.65025
[12] Horn, R.A., Johnson, C.R.: Matrix Analysis. The Cambridge University Press, Cambridge (1985) · Zbl 0576.15001 · doi:10.1017/CBO9780511810817
[13] Jia, Z.: On convergence of the inexact Rayleigh quotient iteration with MINRES. J. Comput. Appl. Math. 236, 4276-4295 (2012) · Zbl 1254.65048 · doi:10.1016/j.cam.2012.05.016
[14] Jia, Z.: On convergence of the inexact Rayleigh quotient iteration with the Lanczos method used for solving linear systems. Sci. China Math. 56, 2145-2160 (2013) · Zbl 1292.65038 · doi:10.1007/s11425-013-4571-7
[15] Jia, Z., Li, C.: On inner iterations in the shift-invert residual Arnoldi method and the Jacobi-Davidson method. Sci. China Math. 57, 1733-1752 (2014) · Zbl 1312.65054 · doi:10.1007/s11425-014-4791-5
[16] Langville, A., Meyer, C.: Google’s PageRank and Beyond: The Science of Search Engine Rankings. The Princeton University Press, Princeton (2006) · Zbl 1104.68042 · doi:10.1515/9781400830329
[17] Lee, C.: Residual Arnoldi method: theory, package and experiments. Ph.D. thesis, TR-4515, Department of Computer Science, University of Maryland at College Park (2007)
[18] Lai, Y.-L., Lin, K.-Y., Lin, W.-W.: An inexact inverse iteration for large sparse eigenvalue problems. Numer. Linear Algebra Appl. 4, 425-437 (1997) · Zbl 0889.65038 · doi:10.1002/(SICI)1099-1506(199709/10)4:5<425::AID-NLA117>3.0.CO;2-G
[19] Liu, C.-S.: Inexact iterative methods for solving eigenvalue problems. Ph.D. thesis, Department of Mathematics, National Tsinghua University, Hsinchu (2012) · Zbl 1292.65038
[20] Lynn, M.S., Timlake, W.P.: Bounds for Perron eigenvectors and subdominant eigenvalues of positive matrices. Linear Algebra Appl. 2, 143-152 (1969) · Zbl 0174.31703 · doi:10.1016/0024-3795(69)90023-8
[21] Noda, T.: Note on the computation of the maximal eigenvalue of a non-negative irreducible matrix. Numer. Math. 17, 382-386 (1971) · Zbl 0226.65026 · doi:10.1007/BF01436087
[22] Notay, Y.: JDCG and JDRPCG codes. http://homepages.ulb.ac.be/ynotay/ · Zbl 0763.65025
[23] Ostrowski, A.M.: On the convergence of the Rayleigh quotient iteration for the computation of the characteristic roots and vectors. V. (Usual Rayleigh quotient for non-Hermitian matrices and linear elementary divisors). Arch. Ration. Mech. Anal. 3, 472-481 (1959) · Zbl 0090.33901 · doi:10.1007/BF00284194
[24] Parlett, B.N.: The symmetric eigenvalue problem. In: Classics in Applied Mathematics, Vol. 20. SIAM, Philadelphia (1998) · Zbl 0885.65039
[25] Robbé, M., Sadkane, M., Spence, A.: Inexact inverse subspace iteration with preconditioning applied to non-Hermitian eigenvalue problems. SIAM J. Matrix Anal. Appl. 31, 92-113 (2009) · Zbl 1269.65036 · doi:10.1137/060673795
[26] Robertazzi, G.: Computer Networks and Systems: Queueing Theory and Performance Evaluation. Springer-Verlag, New York (1990) · Zbl 0729.68005
[27] Saad, Y.: Numerical methods for large eigenvalue problems, revised version. In: Classics in Applied Mathematics, Vol. 66. SIAM, Philadelphia (2011) · Zbl 1242.65068
[28] Sorensen, D.C.: Implicit application of polynomial filters in a \[k\] k-step Arnoldi method. SIAM J. Matrix Anal. Appl. 13, 357-385 (1992) · Zbl 0763.65025 · doi:10.1137/0613025
[29] Shivakumar, P., Williams, J., Ye, Q., Marinov, C.: On two-sided bounds related to weakly diagonally dominant \[M\] M-matrices with applications to digital circuit dynamics. SIAM J. Matrix Anal. Appl. 17, 298-312 (1996) · Zbl 0853.15013 · doi:10.1137/S0895479894276370
[30] Simoncini, V., Elden, L.: Inexact Rayleigh quotient-type methods for eigenvalue computations. BIT 42, 159-182 (2002) · Zbl 1003.65033 · doi:10.1023/A:1021930421106
[31] Sleijpen, G.L.G., van der Vorst, H.A.: A Jacobi-Davidson iteration method for linear eigenvalue problems. SIAM J. Matrix Anal. Appl. 17, 401-425 (1996) · Zbl 0860.65023 · doi:10.1137/S0895479894270427
[32] Sleijpen, G.L.G.: JDQR and JDQZ codes. http://www.math.uu.nl/people/sleijpen · Zbl 1003.65033
[33] Stewart, G.W.: Matrix Algorithms, vol. II. SIAM, Philadelphia (2001) · Zbl 0984.65031 · doi:10.1137/1.9780898718058
[34] Stewart, G.W.: A Krylov-Schur algorithm for large eigenproblems. SIAM J. Matrix Anal. Appl. 23, 601-614 (2001) · Zbl 1003.65045 · doi:10.1137/S0895479800371529
[35] Varga, R.S.: Matrix Iterative Analysis, 2nd edn. Spinger-Verlag, Berlin (2000) · Zbl 0998.65505 · doi:10.1007/978-3-642-05156-2
[36] Wei, M.Q., Pang, M.Y., Fan, C.L.: Survey on planar parameterization of triangular meshes. In: Proceedings of the 2010 International Conference on Measuring Technology and Mechatronics Automation, pp. 702-705 (2010) · Zbl 1254.65048
[37] Wielandt, H.: Unzerelegbare, nicht negativen Matrizen. Math. Z. 52, 642-648 (1950) · Zbl 0035.29101 · doi:10.1007/BF02230720
[38] Wilkinson, J.H.: The Algebraic Eigenvalue Problem. Clarendon Press, Oxford (1965) · Zbl 0258.65037
[39] Xue, F., Szyld, D.B.: Efficient preconditioned inner solves for inexact Rayleigh quotient iteration and their connections to the single-vector Jacobi-Davidson method. SIAM J. Matrix Anal. Appl. 32, 993-1018 (2011) · Zbl 1238.65028 · doi:10.1137/100807922
[40] Xue, J.: Computing the smallest eigenvalue of an \[M\] M-matrix. SIAM J. Matrix Anal. Appl. 17, 748-762 (1996) · Zbl 0863.65015 · doi:10.1137/S0895479894276953
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.