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.展开更多
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.展开更多
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 presents new numeric and symbolic algorithms for solving doubly bordered tridiagonal linear system. The proposed algorithms are derived using partition together with UL factorization. Inversion algorithm fo...This paper presents new numeric and symbolic algorithms for solving doubly bordered tridiagonal linear system. The proposed algorithms are derived using partition together with UL factorization. Inversion algorithm for doubly bordered tridiagonal matrix is also considered based on the Sherman-Morrison-Woodbury formula. The algorithms are implemented using the computer algebra system, MAPLE. 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.展开更多
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.展开更多
This paper aims at extending our previous work on the solution of the one-dimensional Dirac equation using the Tridiagonal Representation Approach (TRA). In the approach, we expand the spinor wavefunction in terms of ...This paper aims at extending our previous work on the solution of the one-dimensional Dirac equation using the Tridiagonal Representation Approach (TRA). In the approach, we expand the spinor wavefunction in terms of suitable square integrable basis functions that support a tridiagonal matrix representation of the wave operator. This will transform the problem from solving a system of coupled first order differential equations to solving an algebraic three-term recursion relation for the expansion coefficients of the wavefunction. In some cases, solutions to this recursion relation can be related to well-known classes of orthogonal polynomials whereas in other situations solutions represent new class of polynomials. In this work, we will discuss various solvable potentials that obey the tridiagonal representation requirement with special emphasis on simple cases with spin-symmetric and pseudospin-symmetric potential couplings. We conclude by mentioning some potential applications in graphene.展开更多
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.展开更多
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 block representation of the BLU factorization for block tridiagonal matrices is presented. Some properties on the factors obtained in the course of the factorization are studied. Simpler expressions for errors incur...A block representation of the BLU factorization for block tridiagonal matrices is presented. Some properties on the factors obtained in the course of the factorization are studied. Simpler expressions for errors incurred at the process of the factorization for block tridiagonal matrices are considered.展开更多
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.展开更多
The aim of this work is to find exact solutions of the Dirac equation in(1+1) space-time beyond the already known class.We consider exact spin(and pseudo-spin) symmetric Dirac equations where the scalar potential is e...The aim of this work is to find exact solutions of the Dirac equation in(1+1) space-time beyond the already known class.We consider exact spin(and pseudo-spin) symmetric Dirac equations where the scalar potential is equal to plus(and minus) the vector potential.We also include pseudo-scalar potentials in the interaction.The spinor wavefunction is written as a bounded sum in a complete set of square integrable basis,which is chosen such that the matrix representation of the Dirac wave operator is tridiagonal and symmetric.This makes the matrix wave equation a symmetric three-term recursion relation for the expansion coefficients of the wavefunction.We solve the recursion relation exactly in terms of orthogonal polynomials and obtain the state functions and corresponding relativistic energy spectrum and phase shift.展开更多
In this paper, we present a unified approach to decomposing a special class of block tridiagonal matrices <i>K</i> (<i>α</i> ,<i>β</i> ) into block diagonal matrices using similar...In this paper, we present a unified approach to decomposing a special class of block tridiagonal matrices <i>K</i> (<i>α</i> ,<i>β</i> ) into block diagonal matrices using similarity transformations. The matrices <i>K</i> (<i>α</i> ,<i>β</i> )∈ <i>R</i><sup><i>pq</i>× <i>pq</i></sup> are of the form <i>K</i> (<i>α</i> ,<i>β</i> = block-tridiag[<i>β B</i>,<i>A</i>,<i>α B</i>] for three special pairs of (<i>α</i> ,<i>β</i> ): <i>K</i> (1,1), <i>K</i> (1,2) and <i>K</i> (2,2) , where the matrices <i>A</i> and <i>B</i>, <i>A</i>, <i>B</i>∈ <i>R</i><sup><i>p</i>× <i>q</i></sup> , are general square matrices. The decomposed block diagonal matrices <img src="Edit_00717830-3b3b-4856-8ecd-a9db983fef19.png" width="15" height="15" alt="" />(<i>α</i> ,<i>β</i> ) for the three cases are all of the form: <img src="Edit_71ffcd27-6acc-4922-b5e2-f4be15b9b8dc.png" width="15" height="15" alt="" />(<i>α</i> ,<i>β</i> ) = <i>D</i><sub>1</sub> (<i>α</i> ,<i>β</i> ) ⊕ <i>D</i><sub>2</sub> (<i>α</i> ,<i>β</i> ) ⊕---⊕ <i>D</i><sub>q</sub> (<i>α</i> ,<i>β</i> ) , where <i>D<sub>k</sub></i> (<i>α</i> ,<i>β</i> ) = <i>A</i>+ 2cos ( <i>θ<sub>k</sub></i> (<i>α</i> ,<i>β</i> )) <i>B</i>, in which <i>θ<sub>k</sub></i> (<i>α</i> ,<i>β</i> ) , k = 1,2, --- q , depend on the values of <i>α</i> and <i>β</i>. Our decomposition method is closely related to the classical fast Poisson solver using Fourier analysis. Unlike the fast Poisson solver, our approach decomposes <i>K</i> (<i>α</i> ,<i>β</i> ) into <i>q</i> diagonal blocks, instead of <i>p</i> blocks. Furthermore, our proposed approach does not require matrices <i>A</i> and <i>B</i> to be symmetric and commute, and employs only the eigenvectors of the tridiagonal matrix <i>T</i> (<i>α</i> ,<i>β</i> ) = tridiag[<i>β b</i>, <i>a</i>,<i>αb</i>] in a block form, where <i>a</i> and <i>b</i> are scalars. The transformation matrices, their inverses, and the explicit form of the decomposed block diagonal matrices are derived in this paper. Numerical examples and experiments are also presented to demonstrate the validity and usefulness of the approach. Due to the decoupled nature of the decomposed matrices, this approach lends itself to parallel and distributed computations for solving both linear systems and eigenvalue problems using multiprocessors.展开更多
The present article is mainly devoted for solving bordered k-tridiagonal linear systems of equations. Two efficient and reliable symbolic algorithms for solving such systems are constructed. The computational cost of ...The present article is mainly devoted for solving bordered k-tridiagonal linear systems of equations. Two efficient and reliable symbolic algorithms for solving such systems are constructed. The computational cost of the algorithms is obtained. Some illustrative examples are given.展开更多
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 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.
文摘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.
基金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 presents new numeric and symbolic algorithms for solving doubly bordered tridiagonal linear system. The proposed algorithms are derived using partition together with UL factorization. Inversion algorithm for doubly bordered tridiagonal matrix is also considered based on the Sherman-Morrison-Woodbury formula. The algorithms are implemented using the computer algebra system, MAPLE. 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.
文摘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.
文摘This paper aims at extending our previous work on the solution of the one-dimensional Dirac equation using the Tridiagonal Representation Approach (TRA). In the approach, we expand the spinor wavefunction in terms of suitable square integrable basis functions that support a tridiagonal matrix representation of the wave operator. This will transform the problem from solving a system of coupled first order differential equations to solving an algebraic three-term recursion relation for the expansion coefficients of the wavefunction. In some cases, solutions to this recursion relation can be related to well-known classes of orthogonal polynomials whereas in other situations solutions represent new class of polynomials. In this work, we will discuss various solvable potentials that obey the tridiagonal representation requirement with special emphasis on simple cases with spin-symmetric and pseudospin-symmetric potential couplings. We conclude by mentioning some potential applications in graphene.
文摘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.
文摘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 block representation of the BLU factorization for block tridiagonal matrices is presented. Some properties on the factors obtained in the course of the factorization are studied. Simpler expressions for errors incurred at the process of the factorization for block tridiagonal matrices are considered.
文摘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.
基金King Fahd University of Petroleum and Minerals (KFUPM) for their support under research grant RG1502the material support and encouragements of the Saudi Center for Theoretical Physics (SCTP)
文摘The aim of this work is to find exact solutions of the Dirac equation in(1+1) space-time beyond the already known class.We consider exact spin(and pseudo-spin) symmetric Dirac equations where the scalar potential is equal to plus(and minus) the vector potential.We also include pseudo-scalar potentials in the interaction.The spinor wavefunction is written as a bounded sum in a complete set of square integrable basis,which is chosen such that the matrix representation of the Dirac wave operator is tridiagonal and symmetric.This makes the matrix wave equation a symmetric three-term recursion relation for the expansion coefficients of the wavefunction.We solve the recursion relation exactly in terms of orthogonal polynomials and obtain the state functions and corresponding relativistic energy spectrum and phase shift.
文摘In this paper, we present a unified approach to decomposing a special class of block tridiagonal matrices <i>K</i> (<i>α</i> ,<i>β</i> ) into block diagonal matrices using similarity transformations. The matrices <i>K</i> (<i>α</i> ,<i>β</i> )∈ <i>R</i><sup><i>pq</i>× <i>pq</i></sup> are of the form <i>K</i> (<i>α</i> ,<i>β</i> = block-tridiag[<i>β B</i>,<i>A</i>,<i>α B</i>] for three special pairs of (<i>α</i> ,<i>β</i> ): <i>K</i> (1,1), <i>K</i> (1,2) and <i>K</i> (2,2) , where the matrices <i>A</i> and <i>B</i>, <i>A</i>, <i>B</i>∈ <i>R</i><sup><i>p</i>× <i>q</i></sup> , are general square matrices. The decomposed block diagonal matrices <img src="Edit_00717830-3b3b-4856-8ecd-a9db983fef19.png" width="15" height="15" alt="" />(<i>α</i> ,<i>β</i> ) for the three cases are all of the form: <img src="Edit_71ffcd27-6acc-4922-b5e2-f4be15b9b8dc.png" width="15" height="15" alt="" />(<i>α</i> ,<i>β</i> ) = <i>D</i><sub>1</sub> (<i>α</i> ,<i>β</i> ) ⊕ <i>D</i><sub>2</sub> (<i>α</i> ,<i>β</i> ) ⊕---⊕ <i>D</i><sub>q</sub> (<i>α</i> ,<i>β</i> ) , where <i>D<sub>k</sub></i> (<i>α</i> ,<i>β</i> ) = <i>A</i>+ 2cos ( <i>θ<sub>k</sub></i> (<i>α</i> ,<i>β</i> )) <i>B</i>, in which <i>θ<sub>k</sub></i> (<i>α</i> ,<i>β</i> ) , k = 1,2, --- q , depend on the values of <i>α</i> and <i>β</i>. Our decomposition method is closely related to the classical fast Poisson solver using Fourier analysis. Unlike the fast Poisson solver, our approach decomposes <i>K</i> (<i>α</i> ,<i>β</i> ) into <i>q</i> diagonal blocks, instead of <i>p</i> blocks. Furthermore, our proposed approach does not require matrices <i>A</i> and <i>B</i> to be symmetric and commute, and employs only the eigenvectors of the tridiagonal matrix <i>T</i> (<i>α</i> ,<i>β</i> ) = tridiag[<i>β b</i>, <i>a</i>,<i>αb</i>] in a block form, where <i>a</i> and <i>b</i> are scalars. The transformation matrices, their inverses, and the explicit form of the decomposed block diagonal matrices are derived in this paper. Numerical examples and experiments are also presented to demonstrate the validity and usefulness of the approach. Due to the decoupled nature of the decomposed matrices, this approach lends itself to parallel and distributed computations for solving both linear systems and eigenvalue problems using multiprocessors.
文摘The present article is mainly devoted for solving bordered k-tridiagonal linear systems of equations. Two efficient and reliable symbolic algorithms for solving such systems are constructed. The computational cost of the algorithms is obtained. Some illustrative examples are given.
文摘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.
