A positivity preserving inexact Noda iteration for computing the smallest eigenpair of a large irreducible M-matrix
From MaRDI portal
Publication:2353376
Abstract: In this paper, based on the Noda iteration, we present inexact Noda iterations (INI), to find the smallest eigenvalue and the associated positive eigenvector of a large irreducible nonsingular M-matrix. The positivity of approximations is critical in applications, and if the approximations lose the positivity then they will be physically meaningless. We propose two different inner tolerance strategies for solving the inner linear systems involved, and prove that the resulting INI algorithms are globally linear and superlinear with the convergence order , respectively. The proposed INI algorithms are structure preserving and maintains the positivity of approximate eigenvectors. We also revisit the exact Noda iteration and establish a new quadratic convergence result. All the above is first done for the problem of computing the Perron root and the positive Perron vector of an irreducible nonnegative matrix and then adapted to that of computing the smallest eigenpair of the irreducible nonsingular M-matrix. Numerical examples illustrate that the proposed INI algorithms are practical, and they always preserve the positivity of approximate eigenvectors. We compare them with the positivity non-preserving Jacobi--Davidson method and implicitly restarted Arnoldi method, which often compute physically meaningless eigenvectors, and illustrate that the overall efficiency of the INI algorithms is competitive with and can be considerably higher than the latter two methods.
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 \textit{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.
Recommendations
- Computing the Smallest Eigenvalue of an M-Matrix
- scientific article; zbMATH DE number 1138094
- Positive eigenvector of nonlinear eigenvalue problem with a singular M-matrix and Newton-SOR iterative solution
- FOM-inverse vector iteration method for computing a few smallest (largest) eigenvalues of pair (A,B)
- scientific article; zbMATH DE number 5847291
Cites work
- A Jacobi–Davidson Iteration Method for Linear Eigenvalue Problems
- A Krylov--Schur algorithm for large eigenproblems
- Accurate computation of the smallest eigenvalue of a diagonally dominant M-matrix
- Asymptotics for steady-state tail probabilities in structured markov queueing models
- Bounds for Perron eigenvectors and subdominant eigenvalues of positive matrices
- Computing the Smallest Eigenvalue of an M-Matrix
- Efficient Preconditioned Inner Solves For Inexact Rayleigh Quotient Iteration And Their Connections To The Single-Vector Jacobi–Davidson Method
- Einschliessungssatz für die charakteristischen Zahlen von Matrizen
- Google's PageRank and beyond. The science of search engine rankings
- scientific article; zbMATH DE number 48600 (Why is no real title available?)
- scientific article; zbMATH DE number 734901 (Why is no real title available?)
- scientific article; zbMATH DE number 1049353 (Why is no real title available?)
- scientific article; zbMATH DE number 1138094 (Why is no real title available?)
- scientific article; zbMATH DE number 6159604 (Why is no real title available?)
- scientific article; zbMATH DE number 1433445 (Why is no real title available?)
- scientific article; zbMATH DE number 3408799 (Why is no real title available?)
- Implicit Application of Polynomial Filters in a k-Step Arnoldi Method
- Inexact inverse iteration for symmetric matrices
- Inexact inverse subspace iteration with preconditioning applied to non-Hermitian eigenvalue problems
- Inexact Rayleigh quotient-type methods for eigenvalue computations
- Inner iterations in the shift-invert residual Arnoldi method and the Jacobi-Davidson method
- Inverse iteration for calculating the spectral radius of a non-negative irreducible matrix
- Matrix algorithms. Vol. 2: Eigensystems
- Matrix Analysis
- Note on the computation of the maximal eigenvalue of a non-negative irreducible matrix
- Numerical methods for large eigenvalue problems
- On convergence of the inexact Rayleigh quotient iteration with MINRES
- On convergence of the inexact Rayleigh quotient iteration with the Lanczos method used for solving linear systems
- 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. VI: Usual Rayleigh quotient for nonlinear elementary d
- On Two-Sided Bounds Related to Weakly Diagonally Dominant M-Matrices with Application to Digital Circuit Dynamics
- Unzerlegbare, nicht negative Matrizen
Cited in
(10)- Monotone convergence of Newton-like iteration for a structured nonlinear eigen-problem
- Inexact generalized Noda iterations for generalized eigenproblems
- FOM-inverse vector iteration method for computing a few smallest (largest) eigenvalues of pair (A,B)
- Solving multi-linear systems with \(\mathcal {M}\)-tensors
- Newton-noda iteration for finding the Perron pair of a weakly irreducible nonnegative tensor
- A Positivity Preserving Inverse Iteration for Finding the Perron Pair of an Irreducible Nonnegative Third Order Tensor
- Computing the Smallest Eigenvalue of an M-Matrix
- On Cvetković-Kostić-Varga type matrices
- Two-step Noda iteration for irreducible nonnegative matrices
- Noda iterations for generalized eigenproblems following Perron-Frobenius theory
This page was built for publication: A positivity preserving inexact Noda iteration for computing the smallest eigenpair of a large irreducible \(M\)-matrix
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2353376)
