A pivoting strategy for symmetric tridiagonal matrices

The LBL^T factorization of Bunch for solving linear systems involving a symmetric indefinite tridiagonal matrix T is a stable, efficient method. It computes a unit lower triangular matrix L and a block 1 × 1 and 2 × 2 matrix B such that T=LBL^T. Choosing the pivot size requires knowing a priori the largest element σ of T in magnitude. In some applications, it is required to factor T as it is formed without necessarily knowing σ. In this paper, we present a modification of the Bunch algorithm that can satisfy this requirement. We demonstrate that this modification exhibits the same bound on the growth factor as the Bunch algorithm and is likewise normwise backward stable. Copyright © 2005 John Wiley & Sons, Ltd.     

A bandstructure-invariant deflation for real symmetric matrices

By means of an eigenvector and eigenvalue of a real symmetric matrix A, a unitary matrix U is constructed such that U¹AU deflates A and, moreover, the transformation preserves the bandstructure.     

On deflation and singular symmetric positive semi-definite matrices

For various applications, it is well-known that the deflated ICCG is an efficient method for solving linear systems with invertible coefficient matrix. We propose two equivalent variants of this deflated ICCG which can also solve linear systems with singular coefficient matrix, arising from discretization of the discontinuous Poisson equation with Neumann boundary conditions. It is demonstrated both theoretically and numerically that the resulting methods accelerate the convergence of the iterative process.     

Extremal eigenvalue intervals of symmetric tridiagonal interval matrices

Computing the extremal eigenvalue bounds of interval matrices is non‐deterministic polynomial‐time (NP)‐hard. We investigate bounds on real eigenvalues of real symmetric tridiagonal interval matrices and prove that for a given real symmetric tridiagonal interval matrices, we can achieve its exact range of the smallest and largest eigenvalues just by computing extremal eigenvalues of four symmetric tridiagonal matrices.     

A simplified pivoting strategy for symmetric tridiagonal matrices

The pivoting strategy of Bunch and Marcia for solving systems involving symmetric indefinite tridiagonal matrices uses two different methods for solving 2 × 2 systems when a 2 × 2 pivot is chosen. In this paper, we eliminate this need for two methods by adding another criterion for choosing a 1 × 1 pivot. We demonstrate that all the results from the Bunch and Marcia pivoting strategy still hold. Copyright © 2006 John Wiley & Sons, Ltd.     

Homotopy method for the eigenvalues of symmetric tridiagonal matrices

We will present the homotopy method for finding eigenvalues of symmetric, tridiagonal matrices. This method finds eigenvalues separately, which can be a large advantage on systems with parallel processors. We will introduce the method and establish some bounds that justify the use of Newton’s method in constructing the homotopy curves.     

A new shift of the QL algorithm for irreducible symmetric tridiagonal matrices

A new shift in the QL algorithm for symmetric tridiagonal matrices is described. The shift is a combination of the Rayleigh quotient shift and Wilkinson's shift. It is shown that QL is globally convergent with this shift and that the asymptotic rate is always cubic.     

A fully stable rational version of theQR algorithm for tridiagonal matrices

Summary A rational version of theQR algorithm for symmetric tridiagonal matrices is presented. Stability is ensured by calculating the elements of the transformed matrix by various formulas, depending on the angle of rotation. Virtual origin shifts are determined from perturbation estimates for the leading 2×2 and 3×3 submatrices; the size of these shifts can optionally serve as a convergence criterion. A number of test matrices, including one with several degeneracies, were diagonalized; an average of 1.3–1.5QR iterations per eigenvalue was needed for 12-figure precision, and of 1.7–2.0 for 22-figure precision.     

Complex symmetric matrices with strongly stable iterates

We study complex-valued symmetric matrices. A simple expression for the spectral norm of such matrices is obtained, by utilizing a unitarily congruent invariant form. Consequently, we provide a sharp criterion for identifying those symmetric matrices whose spectral norm does not exceed one: such strongly stable matrices are usually sought in connection with convergent difference approximations to partial differential equations. As an example, we apply the derived criterion to conclude the strong stability of a Lax-Wendroff scheme.     

A property of eigenvalue bounds for a class of symmetric tridiagonal interval matrices

The eigenvalue bounds of interval matrices are often required in some mechanical and engineering fields. In this paper, we consider an interval eigenvalue problem with symmetric tridiagonal matrices. A theoretical result is obtained that under certain assumptions the upper and lower bounds of interval eigenvalues of the problem must be achieved just at some vertex matrices of the interval matrix. Then a sufficient condition is provided to guarantee the assumption to be satisfied. The conclusion is illustrated also by a numerical example. Copyright © 2010 John Wiley & Sons, Ltd.     

The manifold of isospectral symmetric tridiagonal matrices and realization of cycles by aspherical manifolds

We consider the classical N. Steenrod’s problem of realization of cycles by continuous images of manifolds. Our goal is to find a class \(\mathcal{M}_n \) of oriented n-dimensional closed smooth manifolds such that each integral homology class can be realized with some multiplicity by an image of a manifold from the class \(\mathcal{M}_n \). We prove that as the class \(\mathcal{M}_n \) one can take a set of finite-fold coverings of the manifold M ⁿ of isospectral symmetric tridiagonal real (n + 1) × (n + 1) matrices. It is well known that the manifold M ⁿ is aspherical, its fundamental group is torsion-free, and its universal covering is diffeomorphic to ? ⁿ . Thus, every integral homology class of an arcwise connected space can be realized with some multiplicity by an image of an aspherical manifold with a torsion-free fundamental group. In particular, for any closed oriented manifold Q ⁿ , there exists an aspherical manifold that has torsion-free fundamental group and can be mapped onto Q ⁿ with nonzero degree.     

Inversion of tridiagonal matrices

Summary This paper presents a simple algorithm for inverting nonsymmetric tridiagonal matrices that leads immediately to closed forms when they exist. Ukita's theorem is extended to characterize the class of matrices that have tridiagonal inverses.Journal Paper No. J-10137 of the Iowa Agriculture and Home Economics Experiment Station, Ames, Iowa. Project 1669, Partial support by National Institutes of Health, Grant GM 13827     

Toeplitz matrices commuting with tridiagonal matrices

we prove that if R is a nonscalar Toeplitz matrix R_{i, j}=r_?i?j? which commutes with a tridiagonal matrix with simple spectrum, then

$\text{r}{}_{\mathrm{k}}\text{r}{}_1\text{=}\text{u}{}_{\mathrm{k-1}}\text{r}{}_2\text{r}{}_1\text{cos p}\text{u}{}_{\mathrm{k-1}}\text{(cos p)}$

, k=4, 5,…, with U_k the Chebychev polynomial of the second kind, where p is determined from

$\text{cos p=}\text{1}\text{2}\text{r}{}^2{}_1\text{?r}{}_1\text{r}{}_3\text{r}{}^2{}_2\text{?r}{}_1\text{r}{}_3$

.     

Bounds for the extremal eigenvalues of a class of symmetric tridiagonal matrices with applications

We consider a class of symmetric tridiagonal matrices which may be viewed as perturbations of Toeplitz matrices. The Toeplitz structure is destroyed since two elements on each off-diagonal are perturbed. Based on a careful analysis, we derive sharp bounds for the extremal eigenvalues of this class of matrices in terms of the original data of the given matrix. In this way, we also obtain a lower bound for the smallest singular value of certain matrices. Some numerical results indicate that our bounds are extremely good.     

On tridiagonal conjugate-normal matrices

Conjugate-normal matrices play the same role in the theory of unitary congruences as conventional normal matrices do with respect to unitary similarities. Naturally, the properties of both matrix classes are fairly similar up to the distinction between the congruence and similarity. However, in certain respects, conjugate-normal matrices differ substantially from normal ones. Our goal in this paper is to indicate one of such distinctions. It is shown that none of the familiar characterizations of normal matrices having the irreducible tridiagonal form has a natural counterpart in the case of conjugate-normal matrices.     

Inversion of general tridiagonal matrices

In the current work, the authors present a symbolic algorithm for finding the inverse of any general nonsingular tridiagonal matrix. The algorithm is mainly based on the work presented in [Y. Huang, W.F. McColl, Analytic inversion of general tridiagonal matrices, J. Phys. A 30 (1997) 7919–7933] and [M.E.A. El-Mikkawy, A fast algorithm for evaluating nth order tridiagonal determinants, J. Comput. Appl. Math. 166 (2004) 581–584]. It removes all cases where the numeric algorithm in [Y. Huang, W.F. McColl, Analytic inversion of general tridiagonal matrices, J. Phys. A 30 (1997) 7919–7933] fails. The symbolic algorithm is suited for implementation using Computer Algebra Systems (CAS) such as MACSYMA, MAPLE and MATHEMATICA. An illustrative example is given.