The explicit solution to the Poisson equation corresponding to the Q-matrix of a single birth process is obtained,thus the explicit inverse(if exists)is presented directly.As an application,inspired by the inverse pow...The explicit solution to the Poisson equation corresponding to the Q-matrix of a single birth process is obtained,thus the explicit inverse(if exists)is presented directly.As an application,inspired by the inverse power method,combining the explicit inverse with CollatzWielandt formula,a powerful approximation theorem for the maximal eigenpair corresponding to the Q-matrix of a single birth process is presented.Different from the classical acceleration method using some fixed shift in the iteration,the shift in each iteration step is varying and the sequence formed by these shifts is strictly monotone and increases to the eigenvalue needed,which effectively reduces the number of iterations.Some examples are studied to illustrate the power of these results.展开更多
In this paper, the left and right inverse eigenpairs problem of orthogonal matrices and its optimal approximation solution are considered. Based on the special properties of eigenvalue and the special relations of lef...In this paper, the left and right inverse eigenpairs problem of orthogonal matrices and its optimal approximation solution are considered. Based on the special properties of eigenvalue and the special relations of left and right eigenpairs for orthogonal matrices, we find the equivalent problem, and derive the necessary and sufficient conditions for the solvability of the problem and its general solutions. With the properties of continuous function in bounded closed set, the optimal approximate solution is obtained. In addition, an algorithm to obtain the optimal approximation and numerical example are provided.展开更多
This paper proposes a new technique based on inverse Markov chain Monte Carlo algorithm for finding the smallest generalized eigenpair of the large scale matrices. Some numerical examples show that the proposed method...This paper proposes a new technique based on inverse Markov chain Monte Carlo algorithm for finding the smallest generalized eigenpair of the large scale matrices. Some numerical examples show that the proposed method is efficient.展开更多
A hybrid method is presented for determining maximal eigenvalue and its eigenvector(called eigenpair)of a large,dense,symmetric matrix.Many problems require finding only a small part of the eigenpairs,and some require...A hybrid method is presented for determining maximal eigenvalue and its eigenvector(called eigenpair)of a large,dense,symmetric matrix.Many problems require finding only a small part of the eigenpairs,and some require only the maximal one.In a series of papers,efficient algorithms have been developed by Mufa Chen for computing the maximal eigenpairs of tridiagonal matrices with positive off-diagonal elements.The key idea is to explicitly construet effective initial guess of the maximal eigenpair and then to employ a self-closed iterative algorithm.In this paper we will extend Mufa Chen's algorithm to find maximal eigenpair for a large scale,dense,symmetric matrix.Our strategy is to first convert the underlying matrix into the tridiagonal form by using similarity transformations.We then handle the cases that prevent us from applying Chen's algorithm directly,e.g.,the cases with zero or negative super-or sub-diagonal elements.Serval numerical experiments are carried out to demonstrate the efficiency of the proposed hybrid method.展开更多
This paper presents methods for computing a second-order sensitivity matrix and the Hessian matrix of eigenvalues and eigenvectors of multiple parameter structures. Second-order perturbations of eigenvalues and eigenv...This paper presents methods for computing a second-order sensitivity matrix and the Hessian matrix of eigenvalues and eigenvectors of multiple parameter structures. Second-order perturbations of eigenvalues and eigenvectors are transformed into multiple parameter forms,and the second-order perturbation sensitivity matrices of eigenvalues and eigenvectors are developed.With these formulations,the efficient methods based on the second-order Taylor expansion and second-order perturbation are obtained to estimate changes of eigenvalues and eigenvectors when the design parameters are changed. The presented method avoids direct differential operation,and thus reduces difficulty for computing the second-order sensitivity matrices of eigenpairs.A numerical example is given to demonstrate application and accuracy of the proposed method.展开更多
This paper is a continuation of our previous work [Front. Math. China, 2016, 11（6）： 1379-1418] where an efficient algorithm for computing the maximal eigenpalr was introduced first for tridiagonal matrices and then...This paper is a continuation of our previous work [Front. Math. China, 2016, 11（6）： 1379-1418] where an efficient algorithm for computing the maximal eigenpalr was introduced first for tridiagonal matrices and then extended to the irreducible matrices with nonnegative off-diagonal elements. This paper introduces mainly two global algorithms for computing the maximal eigenpair in a rather general setup, including even a class of real （with some negative off-diagonal elements） or complex matrices.展开更多
Based on a series of recent papers, a powerful algorithm is reformulated for computing the maximal eigenpair of self-adjoint complex tridiagonal matrices. In parallel, the same problem in a particular case for computi...Based on a series of recent papers, a powerful algorithm is reformulated for computing the maximal eigenpair of self-adjoint complex tridiagonal matrices. In parallel, the same problem in a particular case for computing the sub-maximal eigenpair is also introduced. The key ideas for each critical improvement are explained. To illustrate the present algorithm and compare it with the related algorithms, more than 10 examples are included.展开更多
This paper is a continuation of our previous paper[Front.Math.China,2017,12(5):10231043]where global algorithms for computing the maximal cigcnpair were introduced in a rather general setup.The efficiency of the globa...This paper is a continuation of our previous paper[Front.Math.China,2017,12(5):10231043]where global algorithms for computing the maximal cigcnpair were introduced in a rather general setup.The efficiency of the global algorithms is improved in this paper in terms of a good use of power iteration and two quasi-symmetric techniques.Finally,the new algorithms are applied to Hua’s economic optimization model.展开更多
The top eigenpairs at the title mean the maximal, the submaximal, or a few of the subsequent eigenpairs of an Hermitizable matrix. Restricting on top ones is to handle with the matrices having large scale, for which o...The top eigenpairs at the title mean the maximal, the submaximal, or a few of the subsequent eigenpairs of an Hermitizable matrix. Restricting on top ones is to handle with the matrices having large scale, for which only little is known up to now. This is different from some mature algorithms, that are clearly limited only to medium-sized matrix for calculating full spectrum. It is hoped that a combination of this paper with the earlier works, to be seen soon, may provide some effective algorithms for computing the spectrum in practice, especially for matrix mechanics.展开更多
This paper is a continuation of the author＇s previous papers [Front. Math. China, 2016, 11（6）： 1379-1418; 2017, 12（5）： 1023-1043], where the linear case was studied. A shifted inverse iteration algorithm is int...This paper is a continuation of the author＇s previous papers [Front. Math. China, 2016, 11（6）： 1379-1418; 2017, 12（5）： 1023-1043], where the linear case was studied. A shifted inverse iteration algorithm is introduced, as an acceleration of the inverse iteration which is often used in the non-linear context （the p-Laplacian operators for instance）. Even though the algorithm is formally similar to the Rayleigh quotient iteration which is well-known in the linear situation, but they are essentially different. The point is that the standard Rayleigh quotient cannot be used as a shift in the non-linear setup. We have to employ a different quantity which has been obtained only recently. As a surprised gift, the explicit formulas for the algorithm restricted to the linear case （p = 2） is obtained, which improves the author＇s approximating procedure for the leading eigenvalues in different context, appeared in a group of publications. The paper begins with p-Laplacian, and is closed by the non-linear operators corresponding to the well-known Hardy-type inequalities.展开更多
Let m, m＇, n be positive integers such that m ≠ m＇. Let A be an ruth order n-dimensional tensor, and let B be an m＇th order n-dimensional tensor. ）, ∈ C is called a B-eigenvalue of A if Ax^m-1 = λBx^m＇-1 and B...Let m, m＇, n be positive integers such that m ≠ m＇. Let A be an ruth order n-dimensional tensor, and let B be an m＇th order n-dimensional tensor. ）, ∈ C is called a B-eigenvalue of A if Ax^m-1 = λBx^m＇-1 and Bx^m＇ = 1 for some x ∈ Cn／{0}. In this paper, we propose a linear homotopy method for solving this eigenproblem. We prove that the method finds all isolated B- eigenpairs. Moreover, it is easy to implement. Numerical results are provided to show the efficiency of the proposed method.展开更多
Most iterative algorithms for eigenpair computation consist of two main steps:a subspace update(SU)step that generates bases for approximate eigenspaces,followed by a Rayleigh-Ritz(RR)projection step that extracts app...Most iterative algorithms for eigenpair computation consist of two main steps:a subspace update(SU)step that generates bases for approximate eigenspaces,followed by a Rayleigh-Ritz(RR)projection step that extracts approximate eigenpairs.So far the predominant methodology for the SU step is based on Krylov subspaces that builds orthonormal bases piece by piece in a sequential manner.In this work,we investigate block methods in the SU step that allow a higher level of concurrency than what is reachable by Krylov subspace methods.To achieve a competitive speed,we propose an augmented Rayleigh-Ritz(ARR)procedure.Combining this ARR procedure with a set of polynomial accelerators,as well as utilizing a few other techniques such as continuation and deflation,we construet a block algorithm designed to reduce the number of RR steps and elevate concurrency in the SU steps.Extensive computational experiments are conducted in C on a representative set of test problems to evaluate the performance of two variants of our algorithm.Numerical results,obtained on a many-core computer without explicit code parallelization,show that when computing a relatively large number of eigenpairs,the performance of our algorithms is competitive with that of several state-of-the-art eigensolvers.展开更多
Based on the generalized characteristic polynomial introduced by J. Canny in Generalized characteristic polynomials [J. Symbolic Comput., 1990, 9（3）： 241-250], it is immediate that for any m-order n-dimensional rea...Based on the generalized characteristic polynomial introduced by J. Canny in Generalized characteristic polynomials [J. Symbolic Comput., 1990, 9（3）： 241-250], it is immediate that for any m-order n-dimensional real tensor, the number of distinct H-eigenvalues is less than or equal to n（m-1）n-1. However, there is no known bounds on the maximal number of distinct H- eigenvectors in general. We prove that for any m ~〉 2, an m-order 2-dimensional tensor sd exists such that d has 2（m - 1） distinct H-eigenpairs. We give examples of 4-order 2-dimensional tensors with six distinct H-eigenvalues as well as six distinct H-eigenvectors. We demonstrate the structure of eigenpairs for a higher order tensor is far more complicated than that of a matrix. Further- more, we introduce a new class of weakly symmetric tensors, called p-symmetric tensors, and show under certain conditions, p-symmetry will effectively reduce the maximal number of distinct H-eigenveetors for a given two-dimensional tensor. Lastly, we provide a complete classification of the H-eigenvectors of a given 4-order 2-dimensional nonnegative p-symmetric tensor. Additionally, we give sufficient conditions which prevent a given 4-order 2-dimensional nonnegative irreducible weakly symmetric tensor from possessing six pairwise distinct H-eigenveetors.展开更多
基金Supported by the National Natural Science Foundation of China(Grant Nos.12101186,11771046)the Scientific Research Foundation for Young Teachers in Capital University of Economics and Business(Grant No.XRZ2021036)。
文摘The explicit solution to the Poisson equation corresponding to the Q-matrix of a single birth process is obtained,thus the explicit inverse(if exists)is presented directly.As an application,inspired by the inverse power method,combining the explicit inverse with CollatzWielandt formula,a powerful approximation theorem for the maximal eigenpair corresponding to the Q-matrix of a single birth process is presented.Different from the classical acceleration method using some fixed shift in the iteration,the shift in each iteration step is varying and the sequence formed by these shifts is strictly monotone and increases to the eigenvalue needed,which effectively reduces the number of iterations.Some examples are studied to illustrate the power of these results.
文摘In this paper, the left and right inverse eigenpairs problem of orthogonal matrices and its optimal approximation solution are considered. Based on the special properties of eigenvalue and the special relations of left and right eigenpairs for orthogonal matrices, we find the equivalent problem, and derive the necessary and sufficient conditions for the solvability of the problem and its general solutions. With the properties of continuous function in bounded closed set, the optimal approximate solution is obtained. In addition, an algorithm to obtain the optimal approximation and numerical example are provided.
文摘This paper proposes a new technique based on inverse Markov chain Monte Carlo algorithm for finding the smallest generalized eigenpair of the large scale matrices. Some numerical examples show that the proposed method is efficient.
基金This work is partially supported by the Special Project on High-Performance Computing of the National Key R&D Program under No.2016YFB0200604the National Natural Science Foundation of China(NSFC)Grant No.11731006,and the NSFC/Hong Kong RRC Joint Research Scheme(NFSC/RGC 11961160718)The work of J.Yang is supported by NSFC-11871264 and Natural Science Foundation of Guangdong Province(2018A0303130123).
文摘A hybrid method is presented for determining maximal eigenvalue and its eigenvector(called eigenpair)of a large,dense,symmetric matrix.Many problems require finding only a small part of the eigenpairs,and some require only the maximal one.In a series of papers,efficient algorithms have been developed by Mufa Chen for computing the maximal eigenpairs of tridiagonal matrices with positive off-diagonal elements.The key idea is to explicitly construet effective initial guess of the maximal eigenpair and then to employ a self-closed iterative algorithm.In this paper we will extend Mufa Chen's algorithm to find maximal eigenpair for a large scale,dense,symmetric matrix.Our strategy is to first convert the underlying matrix into the tridiagonal form by using similarity transformations.We then handle the cases that prevent us from applying Chen's algorithm directly,e.g.,the cases with zero or negative super-or sub-diagonal elements.Serval numerical experiments are carried out to demonstrate the efficiency of the proposed hybrid method.
基金Project supported by the 985-Engineering Innovation of Graduate Students of Jilin Universitythe Science and Technology Development Foundation of Jilin Province(20070541)
文摘This paper presents methods for computing a second-order sensitivity matrix and the Hessian matrix of eigenvalues and eigenvectors of multiple parameter structures. Second-order perturbations of eigenvalues and eigenvectors are transformed into multiple parameter forms,and the second-order perturbation sensitivity matrices of eigenvalues and eigenvectors are developed.With these formulations,the efficient methods based on the second-order Taylor expansion and second-order perturbation are obtained to estimate changes of eigenvalues and eigenvectors when the design parameters are changed. The presented method avoids direct differential operation,and thus reduces difficulty for computing the second-order sensitivity matrices of eigenpairs.A numerical example is given to demonstrate application and accuracy of the proposed method.
文摘This paper is a continuation of our previous work [Front. Math. China, 2016, 11（6）： 1379-1418] where an efficient algorithm for computing the maximal eigenpalr was introduced first for tridiagonal matrices and then extended to the irreducible matrices with nonnegative off-diagonal elements. This paper introduces mainly two global algorithms for computing the maximal eigenpair in a rather general setup, including even a class of real （with some negative off-diagonal elements） or complex matrices.
基金supported in part the National Natural Science Foundation of China (Grant No. 11771046)the Project from the Ministry of Education in Chinathe Project Funded by the Priority Academic Program Development of Jiangsu Higher Education Institutions.
文摘Based on a series of recent papers, a powerful algorithm is reformulated for computing the maximal eigenpair of self-adjoint complex tridiagonal matrices. In parallel, the same problem in a particular case for computing the sub-maximal eigenpair is also introduced. The key ideas for each critical improvement are explained. To illustrate the present algorithm and compare it with the related algorithms, more than 10 examples are included.
基金This work was supported in part by the National Natural Science Foundation of China(Grant No.11771046)the Project from the Ministry of Education in China,and the Project Funded by the Priority Academic Program Development of Jiangsu Higher Education Institutions.
文摘This paper is a continuation of our previous paper[Front.Math.China,2017,12(5):10231043]where global algorithms for computing the maximal cigcnpair were introduced in a rather general setup.The efficiency of the global algorithms is improved in this paper in terms of a good use of power iteration and two quasi-symmetric techniques.Finally,the new algorithms are applied to Hua’s economic optimization model.
基金This work was supported in part by the National Natural Science Foundation of China(Grant Nos.12090011,11771046,11771188,11771189)the National Key R&D Program of China(No.2020YFA0712900)+1 种基金the Natural Science Foundation of Jiangsu Province(Grant No.BK20171162)the project from the Ministry of Education in China,and the Project Funded by the Priority Academic Program Development of Jiangsu Higher Education Institutions.
文摘The top eigenpairs at the title mean the maximal, the submaximal, or a few of the subsequent eigenpairs of an Hermitizable matrix. Restricting on top ones is to handle with the matrices having large scale, for which only little is known up to now. This is different from some mature algorithms, that are clearly limited only to medium-sized matrix for calculating full spectrum. It is hoped that a combination of this paper with the earlier works, to be seen soon, may provide some effective algorithms for computing the spectrum in practice, especially for matrix mechanics.
基金Acknowledgements The author thanks Yue-Shuang Li＇s contribution in the earlier stage of looking for the new algorithm, especially a lot of work on computer checking. Thanks are also given to Zhong-Wei Liao for his corrections on the earlier version of the paper. The author acknowledges the referees for their careful comments and corrections. This work was supported in part by the National Natural Science Foundation of China （Grant Nos. 11626245, 11771046）, the Project from the Ministry of Education in China, and the Project Funded by the Priority Academic Program Development of Jiangsu Higher Education Institutions.
文摘This paper is a continuation of the author＇s previous papers [Front. Math. China, 2016, 11（6）： 1379-1418; 2017, 12（5）： 1023-1043], where the linear case was studied. A shifted inverse iteration algorithm is introduced, as an acceleration of the inverse iteration which is often used in the non-linear context （the p-Laplacian operators for instance）. Even though the algorithm is formally similar to the Rayleigh quotient iteration which is well-known in the linear situation, but they are essentially different. The point is that the standard Rayleigh quotient cannot be used as a shift in the non-linear setup. We have to employ a different quantity which has been obtained only recently. As a surprised gift, the explicit formulas for the algorithm restricted to the linear case （p = 2） is obtained, which improves the author＇s approximating procedure for the leading eigenvalues in different context, appeared in a group of publications. The paper begins with p-Laplacian, and is closed by the non-linear operators corresponding to the well-known Hardy-type inequalities.
文摘Let m, m＇, n be positive integers such that m ≠ m＇. Let A be an ruth order n-dimensional tensor, and let B be an m＇th order n-dimensional tensor. ）, ∈ C is called a B-eigenvalue of A if Ax^m-1 = λBx^m＇-1 and Bx^m＇ = 1 for some x ∈ Cn／{0}. In this paper, we propose a linear homotopy method for solving this eigenproblem. We prove that the method finds all isolated B- eigenpairs. Moreover, it is easy to implement. Numerical results are provided to show the efficiency of the proposed method.
文摘Most iterative algorithms for eigenpair computation consist of two main steps:a subspace update(SU)step that generates bases for approximate eigenspaces,followed by a Rayleigh-Ritz(RR)projection step that extracts approximate eigenpairs.So far the predominant methodology for the SU step is based on Krylov subspaces that builds orthonormal bases piece by piece in a sequential manner.In this work,we investigate block methods in the SU step that allow a higher level of concurrency than what is reachable by Krylov subspace methods.To achieve a competitive speed,we propose an augmented Rayleigh-Ritz(ARR)procedure.Combining this ARR procedure with a set of polynomial accelerators,as well as utilizing a few other techniques such as continuation and deflation,we construet a block algorithm designed to reduce the number of RR steps and elevate concurrency in the SU steps.Extensive computational experiments are conducted in C on a representative set of test problems to evaluate the performance of two variants of our algorithm.Numerical results,obtained on a many-core computer without explicit code parallelization,show that when computing a relatively large number of eigenpairs,the performance of our algorithms is competitive with that of several state-of-the-art eigensolvers.
文摘Based on the generalized characteristic polynomial introduced by J. Canny in Generalized characteristic polynomials [J. Symbolic Comput., 1990, 9（3）： 241-250], it is immediate that for any m-order n-dimensional real tensor, the number of distinct H-eigenvalues is less than or equal to n（m-1）n-1. However, there is no known bounds on the maximal number of distinct H- eigenvectors in general. We prove that for any m ~〉 2, an m-order 2-dimensional tensor sd exists such that d has 2（m - 1） distinct H-eigenpairs. We give examples of 4-order 2-dimensional tensors with six distinct H-eigenvalues as well as six distinct H-eigenvectors. We demonstrate the structure of eigenpairs for a higher order tensor is far more complicated than that of a matrix. Further- more, we introduce a new class of weakly symmetric tensors, called p-symmetric tensors, and show under certain conditions, p-symmetry will effectively reduce the maximal number of distinct H-eigenveetors for a given two-dimensional tensor. Lastly, we provide a complete classification of the H-eigenvectors of a given 4-order 2-dimensional nonnegative p-symmetric tensor. Additionally, we give sufficient conditions which prevent a given 4-order 2-dimensional nonnegative irreducible weakly symmetric tensor from possessing six pairwise distinct H-eigenveetors.
