R. Vandebril, M. Van Barel, N. Mastronardi · Lirias (KU Leuven) · 2003
It is well known how any symmetric matrix can be reduced by an orthogonal similarity transformation into tridiagonal form. Once the tridiagonal matrix has been computed, several algorithms can be used to compute either the whole spectrum or part of it. In this paper, we propose an algorithm to reduce any symmetric matrix into a similar semiseparable one of semiseparability rank 1, by orthogonal similarity transformations. A remarkable feature of the algorithm is that, after few steps of it, the largest eigenvalues, in absolute value, are already computed with high precision. Once the semiseparable matrix has been computed, to compute the whole spectrum either the same algorithm can be iterated or algorithms for computing the eigendecomposition of diagonal plus semiseparable matrices, available in the literature, can be used. These features of the proposed algorithm are confirmed by some numerical experiments.
Cited by 1Open access
Nathan Mattor, Timothy J. Williams, D.W. Hewett et al. · University of North Texas Digital Library (University of North Texas) · 1997
We present a new algorithm for solving banded diagonal matrix problems efficiently on distributed-memory parallel computers, designed originally for use in dynamic alternating-direction implicit partial differential equation solvers. The algorithm optimizes efficiency with respect to the number of numerical operations and to the amount of interprocessor communication. This is called the ``delayed coupling method`` because the communication is deferred until needed. We focus here on tridiagonal and periodic tridiagonal systems.
Cited by 0Open access
An Ping Zhao · Microwave and Optical Technology Letters · 2002
Abstract In this article two special considerations or notes on the implementation of the alternating direction implicit finite‐difference–time‐domain (ADI‐FDTD) method are discussed. In particular, the two notes are (a) the mathematical algorithm used to solve the tridiagonal matrix equation, and (b) the way to apply the excitation. First, it is found that the ADI‐FDTD method is not always stable if the algorithm (for solving the tridiagonal matrix equation) proposed in the book Numerical Recipes in C is adopted. Consequently, a simple, efficient, and stable mathematical algorithm for solving the tridiagonal matrix equation of the ADI‐FDTD method is presented. Second, it is demonstrated that, to obtain more accurate results for all the field components, the excitation function should be applied to both the first subiteration and the second subiteration, rather than forced in the first subiteration only. The theory proposed in this article is validated through numerical examples. © 2002 Wiley Periodicals, Inc. Microwave Opt Technol Lett 33: 273–277, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/mop.10295
Cited by 44
Ausif Mahmood, D. J. Lynch, L. D. Philipp · 1991
A new algorithm for inverting banded matrices is developed which outperforms the existing approaches in terms of arithmetic operation counts. The algorithm treats the banded matrix as a block tridiagonal matrix and couples the inverse of each block to its neighboring block through the Schur's complement. Two passes are required through the diagonal blocks to complete the inverse in the banded portion. The inverse in the rest of the band follows from the inverse in the banded portion. The overall time complexity of the algorithm is O(n2 . bw), where n is the size and bw is the bandwidth of the matrix. It is approximately two times faster than the inverse method based on LU decomposition for small bandwidth. The algorithm developed is especially suited for inverting block tridiagonal matrices and achieves its highest efficiency in this case.
Cited by 0
Pierluigi Amodio, Francesca Mazzia · Mathematics of Computation · 1994
Tridiagonal systems play a fundamental role in matrix computation.In particular, in recent years parallel algorithms for the solution of tridiagonal systems have been developed.Among these, the cyclic reduction algorithm is particularly interesting.Here the stability of the cyclic reduction method is studied under the assumption of diagonal dominance.A backward error analysis is made, yielding a representation of the error matrix for the factorization and for the solution of the linear system.The results are compared with those for LU factorization.
Cited by 29Open access
Luo Zhi · 2000
A parallel algorithm for block tridiagonal linear systems on distributed memory multicomputers is presented. The algorithm is based on carefully estimating the computation load. The load of solving the system is evenly distributed among the processors. Authors make full use of overlapping between computation and communication to decrease the amount of processors' idle time. The processes will not break down when the block tridiagonal systems' coefficient matrix is diagonally dominant. The complexity of the algorithm is analyzed. The results of numerical experiments about the algorithm on a multicomputer show that the efficiency of this algorithm is much higher than that of the algorithm presented by K. L. Chung et al .
Cited by 2
Nicola Mastronardi, Shivkumar Chandrasekaran, Sabine Van Huffel · 1999
A two--way chasing algorithm to reduce a diagonal plus a symmetric semi-- separable matrix to a symmetric tridiagonal one and an algorithm to reduce a diagonal plus an unsymmetric semi--separable matrix to a bidiagonal one are considered. Both algorithms are fast and stable, requiring a computational cost of N²; where N is the order of the considered matrix.
Cited by 0
Haonan Feng, Tao Ding · IEEE Transactions on Power Systems · 2025
Computing three-phase short-circuit currents (3pSCCs) in large-scale high-voltage power systems needs to find the inverted nodal admittance matrix, which is generally time- consuming. However, it is unnecessary to obtain the full inverted matrix if only calculating selected 3pSCCs at some critical nodes. This letter proposes a block-based selected inversion algorithm. It targets selected elements to construct a block tridiagonal matrix, and obtains these selected elements of the inverted matrix by calculating the inverse of the selected block within the block tridiagonal matrix. Simulation results demonstrate that this approach significantly accelerates the computational speed while guaranteeing the high solution accuracy.
Cited by 1
Tzu-yi Chen · 2007
The problem of solving tridiagonal systems on parallel machines has been studied extensively. This paper examines an existing parallel solvers for tridiagonal systems and extends this divide-and-conquer algorithm to solving almost-tridiagonal systems, systems consisting of a tridiagonal matrix with non-zeros elements in the upper right and lower left corners. In addition to a sketch of a solver already used in global climate modeling code, where almost-tridiagonal systems arise because the problem domain wraps around a sphere, two new algorithms are proposed, one using a pipeline to send many small messages, and another sending a few large messages. In-depth descriptions are provided with pseudocode where considered helpful. The algorithms are generalized to the case where there are multiple matrices and multiple right hand side vectors to be solved for. The proposed algorithm which minimizes messages has been implemented in CMMD and a discussion of preliminary timing results is given....
Cited by 0
Terekhov, Andrew · arXiv (Cornell University) · 2009
A parallel algorithm for solving a series of matrix equations with a constant tridiagonal matrix and different right-hand sides is proposed and studied. The process of solving the problem is represented in two steps. The first preliminary step is fixing some rows of the inverse matrix of SLAEs. The second step consists in calculating solutions for all right-hand sides. For reducing the communication interactions, based on the formulated and proved main parallel sweep theorem, we propose an original algorithm for calculating share components of the solution vector. Theoretical estimates validating the efficiency of the approach for both the common- and distributed-memory supercomputers are obtained. Direct and iterative methods of solving a 2D Poisson equation, which include procedures of tridiagonal matrix inversion, are realized using the mpi technology. Results of computational experiments on a multicomputer demonstrate a high efficiency and scalability of the parallel sweep algorithm.
Cited by 0Open access
Application To Kalman-Bucy, Amir Asif · 2000
Weinvestigate the properties of block matrices with block banded inverses to derive efficient matrix inversion algorithms for such matrices. In particular, wederive the following: (1) a recursive algorithm to invert a full matrix whose inverse is structured as a block tridiagonal matrix# (2) a recursive algorithm to compute the inverse of a structured block tridiagonal matrix. These algorithms are exact. They reduce the computational complexity respectively by two and one orders of magnitude over the direct inversion of the associated matrices. We apply these algorithms to develop a computationally efficient approximate implementation of the Kalman-Bucy filter (KBf) that we refer to as the local KBf. The computational effort of the local KBf is reduced by a factor of I over the exact KBf while exhibiting near-optimal performance.
Cited by 0
Robert Erra, Robert Erra, Programme Calcul Scienti Que et al. · OpenGrey (Institut de l'Information Scientifique et Technique) · 1995
This work deals with various finite algorithms that solve two special Structured Inverse Eigenvalue Problem (Siep). The first problem we consider is the Jacobi Inverse Eigenvalue Problem (Jiep): given some constraints on two sets of real, find a Jacobi matrix J (real symmetric tridiagonal with positive nondiagonal entries) that admits as spectrum and principal subspectrum the two given sets. Two classes of finite algorithms are considered. The polynomial algorithm is based on a special Euclid-Sturm algorithm (Householder's terminology) which has been rediscovered several times. The matrix algorithm is a symmetric Lanczos algorithm with a special initial vector. Some characterization of the matrix insures the equivalence of the two algorithms in exact arithmetic. The results of the symmetric situation are extended to the non-symmetric case: this is the second Siep which is considered : the Tridiagonal Inverse Eigenvalue Problem (Tiep). Possible breakdowns may occur in the polynomial...
Cited by 0Open access
Noble, J. H. · Data Archiving and Networked Services (DANS) · 2017
We describe a matrix diagonalization algorithm for complex symmetric (not Hermitian) matrices, A = A^T , which is based on a two-step algorithm involving generalized Householder reflections based on the indefinite inner product _* = sum_i u_i v_i. This inner product is linear in both arguments and avoids complex conjugation. The complex symmetric input matrix is transformed to tridiagonal form using generalized Householder transformations (first step). An iterative, generalized QL decomposition of the tridiagonal matrix employing an implicit shift converges toward diagonal form (second step). The QL algorithm employs iterative deflation techniques when a machine-precision zero is encountered “prematurely” on the super-/sub-diagonal. The algorithm allows for a reliable and computationally efficient computation of resonance and antiresonance energies which emerge from complex-scaled Hamiltonians, and for the numerical determination of the real energy eigenvalues of pseudo–Hermitian and PT-symmetric Hamilton matrices. Numerical reference values are provided.
Cited by 0Open access
Paweł Keller, Iwona Wróbel · arXiv (Cornell University) · 2015
If $A$ is a tridiagonal matrix, then the equations $AX=I$ and $XA=I$ defining the inverse $X$ of $A$ are in fact the second order recurrence relations for the elements in each row and column of $X$. Thus, the recursive algorithms should be a natural and commonly used way for inverting tridiagonal matrices -- but they are not. Even though a variety of such algorithms were proposed so far, none of them can be applied to numerically invert an arbitrary tridiagonal matrix. Moreover, some of the methods suffer a huge instability problem. In this paper, we investigate these problems very thoroughly. We locate and explain the different reasons the recursive algorithms for inverting such matrices fail to deliver satisfactory (or any) result, and then propose new formulae for the elements of $X=A^{-1}$ that allow to construct the asymptotically fastest possible algorithm for computing the inverse of an arbitrary tridiagonal matrix $A$, for which both residual errors, $\|AX-I\|$ and $\|XA-I\|$, are always very small.
Cited by 0Open access
N.K. Volosova, К. А. Волосов, А. K. Volosova et al. · Вестник Пермского университета Математика Механика Информатика · 2023
In this paper we consider for the first time the possibility of applying the tridiagonal runthrough formulas for text data encryption. The encryption algorithm consists in computing the right part of a linear algebraic equations system with a tridiagonal matrix. In the problem, all the equations coefficients, the right-hand side and the solution take the values of the residues modulo a prime number p. The decryption algorithm consists in solving the SLAE on the class of prime modulo p deductions. The decryption algorithm uses the tridiagonal run method. Two theorems are proved for the algorithm correctness. Theorem 2 is a sufficient condition for correctness. Theorem 3 is the necessary conditions for correctness. Three encryptions of the text of 65, 67 symbols examples are given for illustrate the theorems applicability conditions. The keys spatial power is estimated.
Cited by 0Open access
Pierluigi Amodio, Francesca Mazzia · Mathematics of Computation · 1994
Tridiagonal systems play a fundamental role in matrix computation. In particular, in recent years parallel algorithms for the solution of tridiagonal systems have been developed. Among these, the cyclic reduction algorithm is particularly interesting. Here the stability of the cyclic reduction method is studied under the assumption of diagonal dominance. A backward error analysis is made, yielding a representation of the error matrix for the factorization and for the solution of the linear system. The results are compared with those for <italic>LU</italic> factorization.
Cited by 11
Peter Arbenz, Gene H. Golub · Numerical Linear Algebra with Applications · 1995
Abstract The QR algorithm is a basic algorithm for computing the eigenvalues of dense matrices. For efficiency reasons it is prerequisite that the algorithm is applied only after the original matrix has been reduced to a matrix of a particular shape, most notably Hessenberg and tridiagonal, which is preserved during the iterative process. In certain circumstances a reduction to another matrix shape may be advantageous. In this paper, we identify which zero patterns of symmetric matrices are preserved under the QR algorithm.
Cited by 15
S. R. Vatsya, H. O. Pritchard · International Journal of Computer Mathematics · 1983
An explicit expression for the inverse of an invertible, real tridiagonal matrix is obtained, and its principal structural properties are determined. An efficient and stable algorithm is developed by utilising these properties.
Cited by 7
Jundong Tan, Zihao Li, Qi Guo et al. · IEEE Antennas and Wireless Propagation Letters · 2018
This letter presents an efficient parallel algorithm for solving locally one-dimensional (LOD) finite-difference time domain (FDTD) in cloud computing environment. As opposed to the existing LOD-FDTD algorithm parallelization scheme, the proposed method solves the implicit tridiagonal system in parallel by using the Sherman-Morrison formula to decompose the tridiagonal matrix into smaller matrices. The parallel nodes in cloud computers solve the matrices simultaneously. Numerical results show that the proposed method is more efficient in cloud computing environment than the conventional parallelization scheme and shows better scalability.
Cited by 7
Li‐Wen Chang, John A. Stratton, Hee-Seok Kim et al. · 2012 International Conference for High Performance Computing, Networking, Storage and Analysis · 2012
In this paper, we present a scalable, numerically stable, high-performance tridiagonal solver. The solver is based on the SPIKE algorithm for partitioning a large matrix into small independent matrices, which can be solved in parallel. For each small matrix, our solver applies a general 1-by-1 or 2-by-2 diagonal pivoting algorithm, which is also known to be numerically stable. Our paper makes two major contributions. First, our solver is the first numerically stable tridiagonal solver for GPUs. Our solver provides comparable quality of stable solutions to Intel MKL and Matlab, at speed comparable to the GPU tridiagonal solvers in existing packages like CUSPARSE. It is also scalable to multiple GPUs and CPUs. Second, we present and analyze two key optimization strategies for our solver: a high-throughput data layout transformation for memory efficiency, and a dynamic tiling approach for reducing the memory access footprint caused by branch divergence.
Cited by 33