In the current article we propose a new efficient, reliable and breakdown-free algorithm for solving general opposite-bordered tridiagonal linear systems. An explicit formula for computing the determinant of an opposi...In the current article we propose a new efficient, reliable and breakdown-free algorithm for solving general opposite-bordered tridiagonal linear systems. An explicit formula for computing the determinant of an opposite-bordered tridiagonal matrix is investigated. Some illustrative examples are given.展开更多
A new method for solving the 1D Poisson equation is presented using the finite difference method. This method is based on the exact formulation of the inverse of the tridiagonal matrix associated with the Laplacian. T...A new method for solving the 1D Poisson equation is presented using the finite difference method. This method is based on the exact formulation of the inverse of the tridiagonal matrix associated with the Laplacian. This is the first time that the inverse of this remarkable matrix is determined directly and exactly. Thus, solving 1D Poisson equation becomes very accurate and extremely fast. This method is a very important tool for physics and engineering where the Poisson equation appears very often in the description of certain phenomena.展开更多
An interesting semi-analytic solution is given for the Helmholtz equation. This solution is obtained from a rigorous discussion of the regularity and the inversion of the tridiagonal symmetric matrix. Then, applicatio...An interesting semi-analytic solution is given for the Helmholtz equation. This solution is obtained from a rigorous discussion of the regularity and the inversion of the tridiagonal symmetric matrix. Then, applications are given, showing very good accuracy. This work provides also the analytical inverse of the skew-symmetric tridiagonal matrix.展开更多
An algorithm for the inverse of a general tridiagonal matrix is presented. For a tridiagonal matrix having the Doolittle factorization, an inversion algorithm is established. The algorithm is then generalized to deal ...An algorithm for the inverse of a general tridiagonal matrix is presented. For a tridiagonal matrix having the Doolittle factorization, an inversion algorithm is established. The algorithm is then generalized to deal with a general tridiagonal matrix without any restriction. Comparison with other methods is provided, indicating low computational complexity of the proposed algorithm, and its applicability to general tridiagonal matrices.展开更多
This paper establishes an improvement on the QL algorithm for a symmetric tridiagonal matrix T so that we can work out the eigenvalues of T faster. Meanwhile, the new algorithm don’t worsen the stability and precisio...This paper establishes an improvement on the QL algorithm for a symmetric tridiagonal matrix T so that we can work out the eigenvalues of T faster. Meanwhile, the new algorithm don’t worsen the stability and precision of the former algorithm.展开更多
QL(QR) method is an efficient method to find eigenvalues of a matrix. Especially we use QL(QR) method to find eigenvalues of a symmetric tridiagonal matrix. In this case it only costs O(n2) flops, to find all eigenval...QL(QR) method is an efficient method to find eigenvalues of a matrix. Especially we use QL(QR) method to find eigenvalues of a symmetric tridiagonal matrix. In this case it only costs O(n2) flops, to find all eigenvalues. So it is one of the most efficient method for symmetric tridiagonal matrices. Many experts have researched it. Even the method is mature, it still has many problems need to be researched. We put forward five problems here. They are: (1) Convergence and convergence rate; (2) The convergence of diagonal elements; (3) Shift designed to produce the eigenvalues in monotone order; (4) QL algorithm with multi-shift; (5) Error bound. We intoduce our works on these problems, some of them were published and some are new.展开更多
Numeric algorithms for solving the linear systems of tridiagonal type have already existed. The well-known Thomas algorithm is an example of such algorithms. The current paper is mainly devoted to constructing symboli...Numeric algorithms for solving the linear systems of tridiagonal type have already existed. The well-known Thomas algorithm is an example of such algorithms. The current paper is mainly devoted to constructing symbolic algorithms for solving tridiagonal linear systems of equations via transformations. The new symbolic algorithms remove the cases where the numeric algorithms fail. The computational cost of these algorithms is given. MAPLE procedures based on these algorithms are presented. Some illustrative examples are given.展开更多
A code developed recently by the authors, for counting and computing the eigenvalues of a complex tridiagonal matrix, as well as the roots of a complex polynomial, which lie in a given region of the complex plane, is ...A code developed recently by the authors, for counting and computing the eigenvalues of a complex tridiagonal matrix, as well as the roots of a complex polynomial, which lie in a given region of the complex plane, is modified to run in parallel on multi-core machines. A basic characteristic of this code (eventually pointing to its parallelization) is that it can proceed with: 1) partitioning the given region into an appropriate number of subregions;2) counting eigenvalues in each subregion;and 3) computing (already counted) eigenvalues in each subregion. Consequently, theoretically speaking, the whole code in itself parallelizes ideally. We carry out several numerical experiments with random complex tridiagonal matrices, and random complex polynomials as well, in order to study the behaviour of the parallel code, especially the degree of declination from theoretical expectations.展开更多
The paper contains two parts. First, by applying the results about the eigenvalue perturbation bounds for Hermitian block tridiagonal matrices in paper [1], we obtain a new efficient method to estimate the perturbatio...The paper contains two parts. First, by applying the results about the eigenvalue perturbation bounds for Hermitian block tridiagonal matrices in paper [1], we obtain a new efficient method to estimate the perturbation bounds for singular values of block tridiagonal matrix. Second, we consider the perturbation bounds for eigenvalues of Hermitian matrix with block tridiagonal structure when its two adjacent blocks are perturbed simultaneously. In this case, when the eigenvalues of the perturbed matrix are well-separated from the spectrum of the diagonal blocks, our eigenvalues perturbation bounds are very sharp. The numerical examples illustrate the efficiency of our methods.展开更多
One of the most important properties of M-matrices is element-wise non-negative of its inverse. In this paper, we consider element-wise perturbations of tridiagonal M-matrices and obtain bounds on the perturbations so...One of the most important properties of M-matrices is element-wise non-negative of its inverse. In this paper, we consider element-wise perturbations of tridiagonal M-matrices and obtain bounds on the perturbations so that the non-negative inverse persists. The largest interval is given by which the diagonal entries of the inverse of tridiagonal M-matrices can be perturbed without losing the property of total nonnegativity. A numerical example is given to illustrate our findings.展开更多
In the current paper, the authors present a symbolic algorithm for solving doubly bordered k-tridiagonal linear system having n equations and n unknowns. The proposed algorithm is derived by using partition together w...In the current paper, the authors present a symbolic algorithm for solving doubly bordered k-tridiagonal linear system having n equations and n unknowns. The proposed algorithm is derived by using partition together with UL factorization. The cost of the algorithm is O(n). The algorithm is implemented using the computer algebra system, MAPLE. Some illustrative examples are given.展开更多
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.展开更多
文摘In the current article we propose a new efficient, reliable and breakdown-free algorithm for solving general opposite-bordered tridiagonal linear systems. An explicit formula for computing the determinant of an opposite-bordered tridiagonal matrix is investigated. Some illustrative examples are given.
文摘A new method for solving the 1D Poisson equation is presented using the finite difference method. This method is based on the exact formulation of the inverse of the tridiagonal matrix associated with the Laplacian. This is the first time that the inverse of this remarkable matrix is determined directly and exactly. Thus, solving 1D Poisson equation becomes very accurate and extremely fast. This method is a very important tool for physics and engineering where the Poisson equation appears very often in the description of certain phenomena.
文摘An interesting semi-analytic solution is given for the Helmholtz equation. This solution is obtained from a rigorous discussion of the regularity and the inversion of the tridiagonal symmetric matrix. Then, applications are given, showing very good accuracy. This work provides also the analytical inverse of the skew-symmetric tridiagonal matrix.
基金supported by the National Natural Science Foundation of China (No. 10771030)the Key Project of Ministry of Education of China (No. 107098)+1 种基金the Specialized Research Fund for the Doc-toral Program of Higher Education of China (No. 20070614001)the Applied Basic ResearchProject of Sichuan Province (No. 2008JY0052)
文摘An algorithm for the inverse of a general tridiagonal matrix is presented. For a tridiagonal matrix having the Doolittle factorization, an inversion algorithm is established. The algorithm is then generalized to deal with a general tridiagonal matrix without any restriction. Comparison with other methods is provided, indicating low computational complexity of the proposed algorithm, and its applicability to general tridiagonal matrices.
文摘This paper establishes an improvement on the QL algorithm for a symmetric tridiagonal matrix T so that we can work out the eigenvalues of T faster. Meanwhile, the new algorithm don’t worsen the stability and precision of the former algorithm.
文摘QL(QR) method is an efficient method to find eigenvalues of a matrix. Especially we use QL(QR) method to find eigenvalues of a symmetric tridiagonal matrix. In this case it only costs O(n2) flops, to find all eigenvalues. So it is one of the most efficient method for symmetric tridiagonal matrices. Many experts have researched it. Even the method is mature, it still has many problems need to be researched. We put forward five problems here. They are: (1) Convergence and convergence rate; (2) The convergence of diagonal elements; (3) Shift designed to produce the eigenvalues in monotone order; (4) QL algorithm with multi-shift; (5) Error bound. We intoduce our works on these problems, some of them were published and some are new.
文摘Numeric algorithms for solving the linear systems of tridiagonal type have already existed. The well-known Thomas algorithm is an example of such algorithms. The current paper is mainly devoted to constructing symbolic algorithms for solving tridiagonal linear systems of equations via transformations. The new symbolic algorithms remove the cases where the numeric algorithms fail. The computational cost of these algorithms is given. MAPLE procedures based on these algorithms are presented. Some illustrative examples are given.
文摘A code developed recently by the authors, for counting and computing the eigenvalues of a complex tridiagonal matrix, as well as the roots of a complex polynomial, which lie in a given region of the complex plane, is modified to run in parallel on multi-core machines. A basic characteristic of this code (eventually pointing to its parallelization) is that it can proceed with: 1) partitioning the given region into an appropriate number of subregions;2) counting eigenvalues in each subregion;and 3) computing (already counted) eigenvalues in each subregion. Consequently, theoretically speaking, the whole code in itself parallelizes ideally. We carry out several numerical experiments with random complex tridiagonal matrices, and random complex polynomials as well, in order to study the behaviour of the parallel code, especially the degree of declination from theoretical expectations.
文摘The paper contains two parts. First, by applying the results about the eigenvalue perturbation bounds for Hermitian block tridiagonal matrices in paper [1], we obtain a new efficient method to estimate the perturbation bounds for singular values of block tridiagonal matrix. Second, we consider the perturbation bounds for eigenvalues of Hermitian matrix with block tridiagonal structure when its two adjacent blocks are perturbed simultaneously. In this case, when the eigenvalues of the perturbed matrix are well-separated from the spectrum of the diagonal blocks, our eigenvalues perturbation bounds are very sharp. The numerical examples illustrate the efficiency of our methods.
文摘One of the most important properties of M-matrices is element-wise non-negative of its inverse. In this paper, we consider element-wise perturbations of tridiagonal M-matrices and obtain bounds on the perturbations so that the non-negative inverse persists. The largest interval is given by which the diagonal entries of the inverse of tridiagonal M-matrices can be perturbed without losing the property of total nonnegativity. A numerical example is given to illustrate our findings.
文摘In the current paper, the authors present a symbolic algorithm for solving doubly bordered k-tridiagonal linear system having n equations and n unknowns. The proposed algorithm is derived by using partition together with UL factorization. The cost of the algorithm is O(n). The algorithm is implemented using the computer algebra system, MAPLE. Some illustrative examples are given.
基金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.
