Norman E. Gibbs, William G. Poole · Communications of the ACM · 1974
Tridiagonalizing a matrix by similarity transformations is an important computational tool in numerical linear algebra. Consider the class of sparse matrices which can be tridiagonalized using only row and corresponding column permutations. The advantages of using such a transformation include the absence of round-off errors and improved computation time when compared with standard transformations. A graph-theoretic algorithm which examines an arbitrary n × n matrix and determines whether or not it can be permuted into tridiagonal form is given. The algorithm requires no arithmetic while the number of comparisons, the number of assignments, and the number of increments are linear in n . This compares very favorably with standard transformation methods. If the matrix is permutable into tridiagonal form, the algorithm gives the explicit tridiagonal form. Otherwise, early rejection will occur.
Cited by 8Open access
V. E. Lynch, B.A. Carreras, John B. Drake et al. · OSTI OAI (U.S. Department of Energy Office of Scientific and Technical Information) · 1990
One approach to improving the real-time efficiency of plasma turbulence calculations is to use a parallel algorithm. A serial algorithm used for plasma turbulence calculations was modified to allocate a radial region in each node. In this way, convolutions at a fixed radius are performed in parallel, and communication is limited to boundary values for each radial region. For a semi-implicity numerical scheme (tridiagonal matrix solver), there is a factor of 3 improvement in efficiency with the Intel iPSC/860 machine using 64 processors over a single-processor Cray-II. For block-tridiagonal matrix cases (fully implicit code), a second parallelization takes place. The Fourier components are distributed in nodes. In each node, the block-tridiagonal matrix is inverted for each of allocated Fourier components. The algorithm for this second case has not yet been optimized. 10 refs., 4 figs.
Cited by 1Open access
Christopher Smith, Bruce Hendrickson, Elizabeth Jessup · 1994
We present a parallel algorithm for reducing a dense symmetric matrix to tridiagonal form. The algorithm employs a square torus--wrap mapping of matrix elements to processors to reduce communication and uses level 3 BLAS routines for efficient numerical kernels. We demonstrate the efficiency of this approach with performance results on the Intel Paragon. 1 Introduction The standard sequential algorithm for finding eigenvectors and eigenvalues of a dense symmetric matrix A proceeds in three steps. First, the matrix is tridiagonalized with a sequence of symmetric orthogonal transformations to yield a tridiagonal matrix T . Second, the eigenvectors and eigenvalues of T are found. And third, a backtransformation generates the eigenvectors or A from those of T . This paper describes our parallel tridiagonalization algorithm. In section x2, we review the sequential tridiagonalization algorithm, discuss the difficulties associated with its parallelization, and describe our parallel algorithm...
Cited by 0
R. A. Lafreniere, Michael Accorsi · Communications in Numerical Methods in Engineering · 1996
A new conjugate gradient algorithm is presented for extracting eigenvalues from large systems of equations encountered in finite element analysis. The new algorithm involves applying the conjugate gradient method (CGM) to a static problem to generate an equivalent tridiagonal matrix used for eigenvalue computation. The eigenvalues of the tridiagonal matrix are then extracted using a QR factorization. The similarity of the new CGM with the Lanczos method is discussed regarding the need for matrix inversion and reorthogonalization. Several examples using the new method are presented to illustrate its performance.
Cited by 0
Norman Brenner · Communications of the ACM · 1973
This algorithm uses a rational variant of the QR transformation with explicit shift for the computation of all of the eigenvalues of a real, symmetric, and tridiagonal matrix. Details are described in Ill. Procedures tredl or tred3 published in [2] may be used to reduce any real, symmetric matrix to tridiagonal form. Turn the matrix end-for-end if necessary to bring very large entries to the bottom right-hand corner.
Cited by 10Open access
G. W. Hill · Communications of the ACM · 1973
This algorithm uses a rational variant of the QR transformation with explicit shift for the computation of all of the eigenvalues of a real, symmetric, and tridiagonal matrix. Details are described in Ill. Procedures tredl or tred3 published in [2] may be used to reduce any real, symmetric matrix to tridiagonal form. Turn the matrix end-for-end if necessary to bring very large entries to the bottom right-hand corner.
Cited by 4Open access
Jamshid Ozodovich Khasanov, Hayriniso Hayitboyeva · Zenodo (CERN European Organization for Nuclear Research) · 2025
This study presents a mathematical model to forecast the dynamics of population density uuu and water resources vvv in Uzbekistan from 2025 to 2030, based on historical data from 2010 to 2024. A system of nonlinear partial differential equations (PDEs) is employed to describe the interaction between population growth and water consumption. The model is solved numerically using an implicit finite difference scheme and the tridiagonal matrix algorithm (TMA) with an iterative approach, using real data-derived initial conditions and a Gaussian distribution for the spatial representation of population and water resources. By 2030, Uzbekistan’s average population density may reach , while water resources decline to under a baseline scenario, or with a 0.5% reduction in depletion. The study recommends implementing water-saving technologies, such as drip irrigation, to ensure sustainable resource management in Uzbekistan.
Cited by 0Open access
Segura Montero, Oier · QRU Quaderns de Recerca en Urbanisme · 2024
The thesis focuses on finding new methods for inverting image convolution. It starts with the idea that matrix convolution can be transformed into matrix multiplication using some special matrix related with tridiagonal toeplitz matrices. An algorithm for its inversion is given and we also discover how deeply related the inverse is with the determinant of a general tridiagonal toeplitz matrix. So we also find a general formula for those. Experiments and implementations are given
Cited by 0Open access
2018
When a large system of linear algebraic equations has a special pattern, such as a tridiagonal pattern, it is usually worthwhile to develop special methods for that unique pattern. There are a number of direct elimination methods for solving systems of linear algebraic equations which have special patterns in the coefficient matrix. These methods are generally very efficient in computer time and storage. Such methods should be considered when the coefficient matrix fits the required pattern, and when computer storage and/or execution time are important. One algorithm that deserves special attention is the algorithm for tridiagonal matrices, often referred to as the Thomas (1949) algorithm. Large tridiagonal systems arise naturally in a number of problems, especially in the numerical solution of differential equations by implicit methods. Consequently, the Thomas algorithm has found a large number of applications.
Cited by 0
Willems, Paul R, Author, Lang, Bruno, Author, Voemel, Christof, Author · 2005
Abstract. We describe the design and implementation of a new algorithm for computing the singular value decomposition of a real bidiagonal matrix. This algorithm uses ideas developed by Großer and Lang that extend Parlett’s and Dhillon’s MRRR algorithm for the tridiagonal symmetric eigenproblem. One key feature of our new implementation is, that k singular triplets can be computed using only O(nk) storage units and floating point operations, where n is the dimension of the matrix. The algorithm will be made available as routine xBDSCR in the upcoming new release of the LAPACK library. Key words. Bidiagonal Singular Value Decomposition, Tridiagonal Symmetric Eigenproblem, MRRR algorithm, Coupling Relations, LAPACK library
Cited by 0
David L. Harrar, II, Margaret H. Kahn et al. · 2007
As part of the Fujitsu-ANU Parallel Mathematical Subroutine Library Project we have developed a suite of parallel eigenvalue decomposition routines to handle a variety of input matrices. For a dense real symmetric matrix there are routines using the Jacobi algorithm and routines which first reduce the symmetric matrix to tridiagonal form. All algorithms have been developed to fully exploit the vector capabilities of the VPP300. Many approaches require the eigendecomposition of a tridiagonal matrix and high performance for this step has been obtained by using a multisectioning algorithm to find the eigenvalues and inverse iteration to find the eigenvectors. The inverse iteration step achieves high performance because of a wraparound partitioning algorithm for solving a tridiagonal system. 1 Introduction The eigenproblem for the matrix A, that is, to find eigenvalues and eigenvectors x such that Ax = x, is a fundamental linear algebra problem. It arises in many applications in all are...
Cited by 0
2015
The complex Hermitian matrix A is first reduced to a real tridiagonal matrix by n − 2 unitary transformations and a subsequent diagonal transformation. The eigenvalues and eigenvectors are then derived using the QL algorithm, an adaptation of the QR algorithm.
Cited by 0
Siam J. Sci Comput, Qiang Dut, Ming Jint et al. · 2008
Abstract. In this article, thequasi-Laguerre iteration is established inthe spiritofLaguerre’s iteration for solving polynomial f with all real zeros. The new algorithm, which maintains the monotonicity and global convergence of the Laguerre iteration, no longer needs to evaluate f". The ultimate convergence rate is + 1. When applied to approximate the eigenvalues of a symmetric tridiagonal matrix, the algorithm substantially improves the speed of Laguerre’s iteration. Key words, eigenvalue, quasi-Laguerre iteration, symmetric tridiagonal matrix AMS subject classification. 65F15 1. Introduction. The
Cited by 0
Beresford Ν. Parlett, Jianxun He · 2002
Given a MIMO system we seek a full or partial realization of it that is in convenient form. One important application is to obtain a frequency response plot. Here we describe stable methods to produce a fishbone matrix which provides most of the benefits of a tridiagonal system matrix. A fishbone matrix is tridiagonal except for some extra rows or columns which form the bones of the fish. The idea behind the method is to change the two-sided Lanczos process when an instability is encountered, but to make the modifications as mild as possible. The two-sided Lanczos algorithm attempts to reduce A to tridiagonal form J.
Cited by 0
Benjamin Lev · Defense Technical Information Center (DTIC) · 1970
Many transportation problems are such that, when origins and destinations are suitably indexed, the cost matrix contains elements along the main diagonal, a band above it, and a band below it, while the other elements of the cost matrix are infinite. A procedure has been developed which yields optimal solution to such tridiagonal problems in n steps for a n-origin, n-destination problem. A second model has been solved for a tridiagonal and a coupling column of the cost matrix. A third model, a four-diagonal one, has been partially solved. The author suggested and showed a method to solve any other model which is close to a tridiagonal one, by Benders' Algorithm. The algorithm presented here works by eliminating all of diagonal variables in terms of the diagonal ones, and subsequentially models and small linear programming problems. (Author)
Cited by 0Open access
Arne Marthinsen · 1994
. In this work, we are concerned with the construction of a block diagonal, symmetric matrix, with tridiagonal blocks with prescribed eigenvalues. The method we use, is the Lanczos algorithm with complete and partial reorthogonalization. 1 Introduction Let G be an unsymmetric positive definite matrix, and let H be a block diagonal, symmetric matrix, with tridiagonal blocks. We want G and H to have the same eigenvalues. The problem to be discussed here, is how to construct H when G is known. The problem comes from block splitting of linear systems in weather models, see [2]. The matrix G has the eigendecomposition G = E E \\Gamma1 and we want to construct H and Q such that H = QQ T We will then have G = EQ T HQE \\Gamma1 = e EH e E \\Gamma1 The construction of H and Q can obviously be done blockwise, and the algorithm described below is performed for each block. The problem of computing a tridiagonal matrix, T , from a symmetric matrix A 2 R n\\Thetan and a vector ! 2 R n...
Cited by 0
J.J. Dongarra, G. A. Geist, C. H. Romine · 1993
. This paper describes programs to reduce a nonsymmetric matrix to tridiagonal form, compute the eigenvalues of the tridiagonal matrix, improve the accuracy of an eigenvalue, and compute the corresponding eigenvector. The intended purpose of the software is to find a few eigenpairs of a dense nonsymmetric matrix faster and more accurately than previous methods. The performance and accuracy of the new routines are compared to two EISPACK paths: RG and HQR-INVIT. The results show that the new routines always more accurate and also faster if less than 20% of the eigenpairs are needed. Categories and Subject Description. F.2.1 Analysis of Algorithms and Problem Complexity: Numerical Algorithms and Problems --- computations on matrices; G.1.3 Numerical Analysis: Numerical Linear Algebra --- eigenvalue problems; G.4 Mathematical Software --- algorithm analysis General Terms. Algorithms, eigenvalues, nonsymmetric Additional Key Words and Phrases. Condensed form, numerical algorithms 1 I...
Cited by 0
Robert C. Ward, L. J. Gray · OSTI OAI (U.S. Department of Energy Office of Scientific and Technical Information) · 1976
An algorithm is given for computing the eigenvalues and (optionally) the eigenvectors of either a skew-symmetric matrix or a symmetric tridiagonal matrix with constant diagonal. The algorithm uses only orthogonal similarity transformations, and is believed to be the most efficient algorithm available for computing all the eigenvalues or the complete eigensystem. 2 tables.
Cited by 0Open access
L.S. Shieh, A. Tajvari · IEE Proceedings D Control Theory and Applications · 1980
A new block-Routh array with block-Routh algorithm is developed to extract the greatest common matrix polynomial of two matrix polynomials that are not coprime, and to construct a block-transformation matrix that transforms a block-state equation from a block-companion form to a block-tridiagonal form. The newly developed block-state equation in the block-tridiagonal form is a minimal realisation of a matrix-transfer function. Also, the block-state equation is used to synthesise a driving-point impedance matrix. A stability criterion is then derived to test the stability of a class of matrix transfer functions.
Cited by 8
Grégoire Pichon, Azzam Haidar, Mathieu Faverge et al. · 2015
Computing eigenpairs of a symmetric matrix is a problem arising in many industrial applications, including quantum physics and finite-elements computation for automobiles. A classical approach is to reduce the matrix to tridiagonal form before computing eigenpairs of the tridiagonal matrix. Then, a back-transformation allows one to obtain the final solution. Parallelism issues of the reduction stage have already been tackled in different shared-memory libraries. In this article, we focus on solving the tridiagonal Eigen problem, and we describe a novel implementation of the Divide and Conquer algorithm. The algorithm is expressed as a sequential task-flow, scheduled in an out-of-order fashion by a dynamic runtime which allows the programmer to play with tasks granularity. The resulting implementation is between two and five times faster than the equivalent routine from the Intel MKL library, and outperforms the best MRRR implementation for many matrices.
Cited by 6