An implicit QR algorithm for symmetric semiseparable matrices

The QR algorithm is one of the classical methods to compute the eigendecomposition of a matrix. If it is applied on a dense n × n matrix, this algorithm requires O(n³) operations per iteration step. To reduce this complexity for a symmetric matrix to O(n), the original matrix is first reduced to tridiagonal form using orthogonal similarity transformations. In the report (Report TW360, May 2003) a reduction from a symmetric matrix into a similar semiseparable one is described. In this paper a QR algorithm to compute the eigenvalues of semiseparable matrices is designed where each iteration step requires O(n) operations. Hence, combined with the reduction to semiseparable form, the eigenvalues of symmetric matrices can be computed via intermediate semiseparable matrices, instead of tridiagonal ones. The eigenvectors of the intermediate semiseparable matrix will be computed by applying inverse iteration to this matrix. This will be achieved by using an O(n) system solver, for semiseparable matrices. A combination of the previous steps leads to an algorithm for computing the eigenvalue decompositions of semiseparable matrices. Combined with the reduction of a symmetric matrix towards semiseparable form, this algorithm can also be used to calculate the eigenvalue decomposition of symmetric matrices. The presented algorithm has the same order of complexity as the tridiagonal approach, but has larger lower order terms. Numerical experiments illustrate the complexity and the numerical accuracy of the proposed method. Copyright © 2005 John Wiley & Sons, Ltd.     

A Lanczos‐type algorithm for the QR factorization of regular Cauchy matrices

We present a fast algorithm for computing the QR factorization of Cauchy matrices with real nodes. The algorithm works for almost any input matrix, does not require squaring the matrix, and fully exploits the displacement structure of Cauchy matrices. We prove that, if the determinant of a certain semiseparable matrix is non‐zero, a three term recurrence relation among the rows or columns of the factors exists. Copyright © 2002 John Wiley & Sons, Ltd.     

Fast algorithms for computing the Boltzmann collision operator

The development of accurate and fast numerical schemes for the five-fold Boltzmann collision integral represents a challenging problem in scientific computing. For a particular class of interactions, including the so-called hard spheres model in dimension three, we are able to derive spectral methods that can be evaluated through fast algorithms. These algorithms are based on a suitable representation and approximation of the collision operator. Explicit expressions for the errors in the schemes are given and spectral accuracy is proved. Parallelization properties and adaptivity of the algorithms are also discussed.

     

Fast algorithms for hierarchically semiseparable matrices

Semiseparable matrices and many other rank‐structured matrices have been widely used in developing new fast matrix algorithms. In this paper, we generalize the hierarchically semiseparable (HSS) matrix representations and propose some fast algorithms for HSS matrices. We represent HSS matrices in terms of general binary HSS trees and use simplified postordering notation for HSS forms. Fast HSS algorithms including new HSS structure generation and HSS form Cholesky factorization are developed. Moreover, we provide a new linear complexity explicit ULV factorization algorithm for symmetric positive definite HSS matrices with a low‐rank property. The corresponding factors can be used to solve the HSS systems also in linear complexity. Numerical examples demonstrate the efficiency of the algorithms. All these algorithms have nice data locality. They are useful in developing fast‐structured numerical methods for large discretized PDEs (such as elliptic equations), integral equations, eigenvalue problems, etc. Some applications are shown. Copyright © 2009 John Wiley & Sons, Ltd.     

对称r-循环矩阵的快速算法和并行算法

借助于快速付立叶变换(FFT),给出了一种判断对称r-循环线性系统是否有解的快速算法,并且在有解的情况下求出其解,该算法的计算复杂度为O(nlogn),且具有很好的并行性,若使用n台处理机并行处理该算法则只需要O(logn)步.当r=0时,对称r-循环矩阵变成一个上三角型Hankel矩阵,我们也给出了此类矩阵求逆的一种算法.最后将该算法推广到线性同余系统,其运算量仅为O(nlogn).     

A small note on the scaling of symmetric positive definite semiseparable matrices

In this paper we will adapt a known method for diagonal scaling of symmetric positive definite tridiagonal matrices towards the semiseparable case. Based on the fact that a symmetric, positive definite tridiagonal matrix satisfies property A, one can easily construct a diagonal matrix such that has the lowest condition number over all matrices , for any choice of diagonal matrix . Knowing that semiseparable matrices are the inverses of tridiagonal matrices, one can derive similar properties for semiseparable matrices. Here, we will construct the optimal diagonal scaling of a semiseparable matrix, based on a new inversion formula for semiseparable matrices. Some numerical experiments are performed. In a first experiment we compare the condition numbers of the semiseparable matrices before and after the scaling. In a second numerical experiment we compare the scalability of matrices coming from the reduction to semiseparable form and matrices coming from the reduction to tridiagonal form. *The research was partially supported by the Research Council K.U. Leuven, project OT/00/16 (SLAP: Structured Linear Algebra Package), by the Fund for Scientific Research–Flanders (Belgium), projects G.0078.01 (SMA: Structured Matrices and their Applications), G.0176.02 (ANCILA: Asymptotic aNalysis of the Convergence behavior of Iterative methods in numerical Linear Algebra), G.0184.02 (CORFU: Constructive study of Orthogonal Functions) and G.0455.0 (RHPH: Riemann–Hilbert problems, random matrices and Padé–Hermite approximation), and by the Belgian Programme on Interuniversity Poles of Attraction, initiated by the Belgian State, Prime Minister's Office for Science, Technology and Culture, project IUAP V-22 (Dynamical Systems and Control: Computation, Identification & Modelling). The scientific responsibility rests with the authors. The second author participates in the SCCM program, Gates 2B, Stanford University, CA, USA and is also partially supported by the NSF. The first author visited the second one with a grant by the Fund for Scientific Research–Flanders (Belgium).     

Fast and Stable Reduction of Diagonal Plus Semi-Separable Matrices to Tridiagonal and Bidiagonal Form

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.     

A divide-and-conquer algorithm for the eigendecomposition of symmetric block-diagonal plus semiseparable matrices

Summary. We present a fast and numerically stable algorithm for computing the eigendecomposition of a symmetric block diagonal plus semiseparable matrix. We report numerical experiments that indicate that our algorithm is significantly faster than the standard method which treats the given matrix as a general symmetric dense matrix. Mathematics Subject Classification (1991):15A09, 15A23, 65F05, 65L10, 65R20This research was supported in part by NSF Career Award CCR-9734290.This research was supported in part by NSF Career Award CCR-9702866 and by Alfred Sloan Research Fellowship BR-3720.Received: 10, September 2001     

Fast and stable two‐way algorithm for diagonal plus semi‐separable systems of linear equations

An algorithm for the solution of linear systems of equations where the coefficient matrix is diagonal plus a semi‐separable matrix is considered. The algorithm is stable with linear complexity. Furthermore, it is suitable for an implementation on a system of two processors. Copyright © 2001 John Wiley & Sons, Ltd.     

An efficient method for computing the inverse of arrowhead matrices

In this paper we propose a simple and effective method to find the inverse of arrowhead matrices which often appear in wide areas of applied science and engineering such as wireless communications systems, molecular physics, oscillators vibrationally coupled with Fermi liquid, and eigenvalue problems. A modified Sherman–Morrison inverse matrix method is proposed for computing the inverse of an arrowhead matrix. The effectiveness of the proposed method is illustrated and numerical results are presented along with comparative results.     

Orthogonal similarity transformation of a symmetric matrix into a diagonal-plus-semiseparable one with free choice of the diagonal

In this paper we describe an orthogonal similarity transformation for transforming arbitrary symmetric matrices into a diagonal-plus-semiseparable matrix, where we can freely choose the diagonal. Very recently an algorithm was proposed for transforming arbitrary symmetric matrices into similar semiseparable ones. This reduction is strongly connected to the reduction to tridiagonal form. The class of semiseparable matrices can be considered as a subclass of the diagonalplus- semiseparable matrices. Therefore we can interpret the proposed algorithm here as an extension of the reduction to semiseparable form. A numerical experiment is performed comparing thereby the accuracy of this reduction algorithm with respect to the accuracy of the traditional reduction to tridiagonal form, and the reduction to semiseparable form. The experiment indicates that all three reduction algorithms are equally accurate. Moreover it is shown in the experiments that asymptotically all the three approaches have the same complexity, i.e. that they have the same factor preceding the n³ term in the computational complexity. Finally we illustrate that special choices of the diagonal create a specific convergence behavior. The research was partially supported by the Research Council K.U.Leuven, project OT/05/40 (Large rank structured matrix computations), by the Fund for Scientific Research–Flanders (Belgium), projects G.0078.01 (SMA: Structured Matrices and their Applications), G.0176.02 (ANCILA: Asymptotic aNalysis of the Convergence behavior of Iterative methods in numerical Linear Algebra), G.0184.02 (CORFU: Constructive study of Orthogonal Functions) and G.0455.0 (RHPH: Riemann-Hilbert problems, random matrices and Padé-Hermite approximation), and by the Belgian Programme on Interuniversity Poles of Attraction, initiated by the Belgian State, Prime Minister's Office for Science, Technology and Culture, project IUAP V-22 (Dynamical Systems and Control: Computation, Identification & Modelling). The scientific responsibility rests with the authors.     

A method for computing the Perron root for primitive matrices

Following the Perron theorem, the spectral radius of a primitive matrix is a simple eigenvalue. It is shown that for a primitive matrix A, there is a positive rank one matrix X such that B = A ° X , where ° denotes the Hadamard product of matrices, and such that the row (column) sums of matrix B are the same and equal to the Perron root. An iterative algorithm is presented to obtain matrix B without an explicit knowledge of X. The convergence rate of this algorithm is similar to that of the power method but it uses less computational load. A byproduct of the proposed algorithm is a new method for calculating the first eigenvector.     

Divide and conquer: the engineering of delegation

Computational Management Science - Members of an organization have conflicting preferences. Principal-agent theory analyzes how and under which conditions this conflict can be resolved by means of...     

Block matrices and symmetric perturbations

We prove that if A=[A_ij]∈R^N,N is a block symmetric matrix and y is a solution of a nearby linear system (A+E)y=b, then there exists F=F^T such that y solves a nearby symmetric system (A+F)y=b, if A is symmetric positive definite or the matricial norm μ(A)=(‖A_ij‖₂) is diagonally dominant. Our blockwise analysis extends existing normwise and componentwise results on preserving symmetric perturbations (cf. [J.R. Bunch, J.W. Demmel, Ch. F. Van Loan, The strong stability of algorithms for solving symmetric linear systems, SIAM J.Matrix Anal. Appl. 10 (4) (1989) 494-499; D. Herceg, N. Kreji?, On the strong componentwise stability and H-matrices, Demonstratio Mathematica 30 (2) (1997) 373-378; A. Smoktunowicz, A note on the strong componentwise stability of algorithms for solving symmetric linear systems, Demonstratio Mathematica 28 (2) (1995) 443-448]).     

A block algorithm for computing antitriangular factorizations of symmetric matrices

Any symmetric matrix can be reduced to antitriangular form in finitely many steps by orthogonal similarity transformations. This form reveals the inertia of the matrix and has found applications in, e.g., model predictive control and constraint preconditioning. Originally proposed by Mastronardi and Van Dooren, the existing algorithm for performing the reduction to antitriangular form is primarily based on Householder reflectors and Givens rotations. The poor memory access pattern of these operations implies that the performance of the algorithm is bound by the memory bandwidth. In this work, we develop a block algorithm that performs all operations almost entirely in terms of level 3 BLAS operations, which feature a more favorable memory access pattern and lead to better performance. These performance gains are confirmed by numerical experiments that cover a wide range of different inertia.     

The inverse eigenvalue problem for symmetric quasi anti-bidiagonal matrices

In this paper we construct the symmetric quasi anti-bidiagonal matrix that its eigenvalues are given, and show that the problem is also equivalent to the inverse eigenvalue problem for a certain symmetric tridiagonal matrix which has the same eigenvalues. Not only elements of the tridiagonal matrix come from quasi anti-bidiagonal matrix, but also the places of elements exchange based on some conditions.     

New fast divide‐and‐conquer algorithms for the symmetric tridiagonal eigenvalue problem

In this paper, two accelerated divide‐and‐conquer (ADC) algorithms are proposed for the symmetric tridiagonal eigenvalue problem, which cost O(N²r) flops in the worst case, where N is the dimension of the matrix and r is a modest number depending on the distribution of eigenvalues. Both of these algorithms use hierarchically semiseparable (HSS) matrices to approximate some intermediate eigenvector matrices, which are Cauchy‐like matrices and are off‐diagonally low‐rank. The difference of these two versions lies in using different HSS construction algorithms, one (denoted by ADC1) uses a structured low‐rank approximation method and the other (ADC2) uses a randomized HSS construction algorithm. For the ADC2 algorithm, a method is proposed to estimate the off‐diagonal rank. Numerous experiments have been carried out to show their stability and efficiency. These algorithms are implemented in parallel in a shared memory environment, and some parallel implementation details are included. Comparing the ADCs with highly optimized multithreaded libraries such as Intel MKL, we find that ADCs could be more than six times faster for some large matrices with few deflations. Copyright © 2016 John Wiley & Sons, Ltd.     

A Levinson-like algorithm for symmetric strongly nonsingular higher order semiseparable plus band matrices

In this paper, we will derive a solver for a symmetric strongly nonsingular higher order generator representable semiseparable plus band matrix. The solver we will derive is based on the Levinson algorithm, which is used for solving strongly nonsingular Toeplitz systems.