Browsing by Author "Liu, Ching-Sung"

Now showing 1 - 5 of 5

A modified Newton iteration for finding nonnegative Z-eigenpairs of a nonnegative tensor
(2019-02-01)
Guo, Chun-Hua
;
Lin, Wen-Wei
;
Liu, Ching-Sung
;
應用數學系
;
Department of Applied Mathematics
We propose a modified Newton iteration for finding some nonnegative Z-eigenpairs of a nonnegative tensor. When the tensor is irreducible, all nonnegative eigenpairs are known to be positive. We prove local quadratic convergence of the new iteration to any positive eigenpair of a nonnegative tensor, under the usual assumption guaranteeing the local quadratic convergence of the original Newton iteration. A big advantage of the modified Newton iteration is that it seems capable of finding a nonnegative eigenpair starting with any positive unit vector. Special attention is paid to transition probability tensors.
A positivity preserving inexact Noda iteration for computing the smallest eigenpair of a large irreducible M-matrix
(2015-08-01)
Jia, Zhongxiao
;
Lin, Wen-Wei
;
Liu, Ching-Sung
;
應用數學系
;
Department of Applied Mathematics
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 -matrix. The positivity of approximations is critical in applications, and if the approximations lose the positivity then they may be meaningless and could not be interpreted. We propose two different inner tolerance strategies for solving the inner linear systems involved, and prove that the convergence of resulting INI algorithms is 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 is then adapted to computing the smallest eigenpair of the irreducible nonsingular -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 Jacobi-Davidson method, the implicitly restarted Arnoldi method and the explicitly restarted Krylov-Schur method, all of which cannot guarantee the positivity of approximate eigenvectors, and illustrate that the overall efficiency of the INI algorithms is competitive with and can be considerably higher than the latter three methods.
A POSITIVITY PRESERVING INVERSE ITERATION FOR FINDING THE PERRON PAIR OF AN IRREDUCIBLE NONNEGATIVE THIRD ORDER TENSOR
(2016-01-01)
Liu, Ching-Sung
;
Guo, Chun-Hua
;
Lin, Wen-Wei
;
應用數學系
;
Department of Applied Mathematics
We propose an inverse iterative method for computing the Perron pair of an irreducible nonnegative third order tensor. The method involves the selection of a parameter theta(k) in the kth iteration. For every positive starting vector, the method converges quadratically and is positivity preserving in the sense that the vectors approximating the Perron vector are strictly positive in each iteration. It is also shown that theta(k) - 1 near convergence. The computational work for each iteration of the proposed method is less than four times (three times if the tensor is symmetric in modes two and three, and twice if we also take the parameter to be 1 directly) that for each iteration of the Ng-Qi-Zhou algorithm, which is linearly convergent for essentially positive tensors.
Continuation methods for computing Z-/H-eigenpairs of nonnegative tensors
(2018-10-01)
Kuo, Yueh-Cheng
;
Lin, Wen-Wei
;
Liu, Ching-Sung
;
應用數學系
;
Department of Applied Mathematics
In this paper, a homotopy continuation method for the computation of nonnegative Z-/H-eigenpairs of a nonnegative tensor is presented. We show that the homotopy continuation method is guaranteed to compute a nonnegative eigenpair. Additionally, using degree analysis, we show that the number of positive Z-eigenpairs of an irreducible nonnegative tensor is odd. A novel homotopy continuation method is proposed to compute an odd number of positive Z-eigenpairs, and some numerical results are presented. (C) 2018 Elsevier B.V. All rights reserved.
Newton-Noda iteration for finding the Perron pair of a weakly irreducible nonnegative tensor
(2017-09-01)
Liu, Ching-Sung
;
Guo, Chun-Hua
;
Lin, Wen-Wei
;
應用數學系
;
Department of Applied Mathematics
We present a Newton-Noda iteration (NNI) for computing the Perron pair of a weakly irreducible nonnegative mth-order tensor A, by combining the idea of Newton's method with the idea of the Noda iteration. The method requires the selection of a positive parameter theta(k) in the kth iteration, and produces a scalar sequence approximating the spectral radius of A and a positive vector sequence approximating the Perron vector. We propose a halving procedure to determine the parameters theta(k), starting with theta(k) for each k, such that the scalar sequence is monotonically decreasing. Convergence of this sequence to the spectral radius of A (and convergence of the vector sequence to the Perron vector) is guaranteed for any initial positive unit vector, as long as the sequence {theta(k)} so chosen is bounded below by a positive constant. In this case, we always have theta(k) = 1 near convergence and the convergence is quadratic. Very often, the halving procedure will return theta(k)(= 1 i.e., no halving is actually used) for each k. If the tensor is semisymmetric, m >= 4, and theta(k) = 1, then the computational work in the kth iteration of NNI is roughly the same as that for one iteration of the Ng-Qi-Zhou algorithm, which is linearly convergent for the smaller class of weakly primitive tensors.