The Exact Formulation of the Inverse of the Tridiagonal Matrix for Solving the 1D Poisson Equation with the Finite Difference Method

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.

Semi-Analytical Solution of the 1D Helmholtz Equation, Obtained from Inversion of Symmetric Tridiagonal Matrix

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 IMPROVEMENT ON THE QL ALGORITHM FOR SYMMETRIC 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 Method for Symmetric Tridiagonal Matrices

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 inversion algorithm for general 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 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.

Solving Doubly Bordered Tridiagonal Linear Systems via Partition

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.

Parallelizing a Code for Counting and Computing Eigenvalues of Complex Tridiagonal Matrices and Roots of Complex Polynomials

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.

Algorithms for Solving Linear Systems of Equations of Tridiagonal Type via Transformations

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.

Analytical Solutions of the 1D Dirac Equation Using the Tridiagonal Representation Approach

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.

Application and Generalization of Eigenvalues Perturbation Bounds for Hermitian Block Tridiagonal Matrices

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.

A New Symbolic Algorithm for Solving General Opposite-Bordered Tridiagonal Linear Systems

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.

BLU Factorization for Block Tridiagonal Matrices and Its Error Analysis

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.

Inverse Nonnegativity of Tridiagonal <i>M</i>-Matrices under Diagonal Element-Wise Perturbation

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.

Decompositions of Some Special Block Tridiagonal Matrices

In this paper, we present a unified approach to decomposing a special class of block tridiagonal matrices K (α ,β ) into block diagonal matrices using similarity transformations. The matrices K (α ,β )∈ Rpq× pq are of the form K (α ,β = block-tridiag[β B,A,α B] for three special pairs of (α ,β ): K (1,1), K (1,2) and K (2,2) , where the matrices A and B, A, B∈ Rp× q , are general square matrices. The decomposed block diagonal matrices (α ,β ) for the three cases are all of the form: (α ,β ) = D1 (α ,β ) ⊕ D2 (α ,β ) ⊕---⊕ Dq (α ,β ) , where Dk (α ,β ) = A+ 2cos ( θk (α ,β )) B, in which θk (α ,β ) , k = 1,2, --- q , depend on the values of α and β. Our decomposition method is closely related to the classical fast Poisson solver using Fourier analysis. Unlike the fast Poisson solver, our approach decomposes K (α ,β ) into q diagonal blocks, instead of p blocks. Furthermore, our proposed approach does not require matrices A and B to be symmetric and commute, and employs only the eigenvectors of the tridiagonal matrix T (α ,β ) = tridiag[β b, a,αb] in a block form, where a and b 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.

New Algorithms for Solving Bordered <i>k</i>-Tridiagonal Linear Systems

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.

A Generalized Symbolic Thomas Algorithm for Solving Doubly Bordered <i>k</i>-Tridiagonal Linear Systems

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.

Schur Complement Based Preconditioners for Twofold and Block Tridiagonal Saddle Point Problems

In this paper,we consider using Schur complements to design preconditioners for twofold and block tridiagonal saddle point problems.One type of the preconditioners are based on the nested(or recursive)Schur complement,the other is based on an additive type Schur complement after permuting the original saddle point systems.We analyze different preconditioners incorporating the exact Schur complements.We show that some of them will lead to positively stable preconditioned systems if proper signs are selected in front of the Schur complements.These positive-stable preconditioners outperform other preconditioners if the Schur complements are further approximated inexactly.Numerical experiments for a 3-field formulation of the Biot model are provided to verify our predictions.

实对称区间矩阵特征值确界的交错定理及其应用

本文将实对称矩阵特征值的交错定理推广到实对称区间矩阵,给出了实对称区间矩阵特征值确界的交错定理,并应用该定理构造了估计实对称三对角区间矩阵特征值界的算法.文中数值例子表明,本文所给算法与一些现有算法相比在使用范围、计算精度和计算量等方面都具有一定的优越性.

三对角分块矩阵的性质和应用研究

物理性质的许多稳定过程都归结为椭圆型偏微分方程,而椭圆型方程边值问题的精确解只在一些特殊情况下可以求得,更多情况下需要近似地求解这些问题。讨论了三对角分块矩阵的相关概念及其性质,并利用差分格式给出了三对角分块矩阵在求解椭圆型方程边值问题中的应用,最后通过数值算例验证了该方法的有效性。

几类允许代数正的符号模式矩阵

考虑三对角符号模式矩阵和爪形符号模式矩阵,讨论了三对角符号模式矩阵和爪形符号模式矩阵是否允许代数正.借助组合矩阵论和图论的方法,给出了这两类符号模式矩阵允许代数正的必要条件.最后,分别给出了n阶三对角符号模式矩阵和n阶爪形符号模式矩阵允许代数正的等价条件.