A fast algorithm for solving Toeplitz penta-diagonal systems

In this paper a fast algorithm for solving a large system with a symmetric Toeplitz penta-diagonal coefficient matrix is presented. This efficient method is based on the idea of a system perturbation followed by corrections and is competitive with standard methods. The error analysis is also given.     

A fast algorithm for solving a Toeplitz system

In this paper, we present a fast algorithm for solving Symmetric penta-diagonal systems. We give the feasibility and Stability analysis of the algorithm. Moreover, parallel computations can be implemented in the algorithm. The numerical examples verify the efficiency of the algorithm.     

A continuation method for solving symmetric Toeplitz systems

A fast algorithm is proposed for solving symmetric Toeplitz systems. This algorithm continuously transforms the identity matrix into the inverse of a given Toeplitz matrix T. The memory requirements for the algorithm are O(n), and its complexity is O(log κ(T)nlogn), where (T) is the condition number of T. Numerical results are presented that confirm the efficiency of the proposed algorithm.     

A mean value algorithm for Toeplitz matrix completion

In this paper, we propose a new mean value algorithm for the Toeplitz matrix completion based on the singular value thresholding (SVT) algorithm. The completion matrices generated by the new algorithm keep a feasible Toeplitz structure. Meanwhile, we prove the convergence of the new algorithm under some reasonal conditions. Finally, we show the new algorithm is much more effective than the ALM (augmented Lagrange multiplier) algorithm through numerical experiments and image inpainting.     

Band Toeplitz preconditioners for block Toeplitz systems

We consider the solutions of block Toeplitz systems with Toeplitz blocks by the preconditioned conjugate gradient (PCG) method. Here the block Toeplitz matrices are generated by nonnegative functions f(x,y). We use band Toeplitz matrices as preconditioners. The generating functions g(x,y) of the preconditioners are trigonometric polynomials of fixed degree and are determined by minimizing (f − g)/f∞. We prove that the condition number of the preconditioned system is O(1). An a priori bound on the number of iterations for convergence is obtained.     

Fast algorithm for solving the Hankel/Toeplitz Structured Total Least Squares problem

The Structured Total Least Squares (STLS) problem is a natural extension of the Total Least Squares (TLS) problem when constraints on the matrix structure need to be imposed. Similar to the ordinary TLS approach, the STLS approach can be used to determine the parameter vector of a linear model, given some noisy measurements. In many signal processing applications, the imposition of this matrix structure constraint is necessary for obtaining Maximum Likelihood (ML) estimates of the parameter vector. In this paper we consider the Toeplitz (Hankel) STLS problem (i.e., an STLS problem in which the Toeplitz (Hankel) structure needs to be preserved). A fast implementation of an algorithm for solving this frequently occurring STLS problem is proposed. The increased efficiency is obtained by exploiting the low displacement rank of the involved matrices and the sparsity of the associated generators. The fast implementation is compared to two other implementations of algorithms for solving the Toeplitz (Hankel) STLS problem. The comparison is carried out on a recently proposed speech compression scheme. The numerical results confirm the high efficiency of the newly proposed fast implementation: the straightforward implementations have a complexity of O((m+n)³) and O(m³) whereas the proposed implementation has a complexity of O(mn+n²). This revised version was published online in June 2006 with corrections to the Cover Date.     

A communication-less parallel algorithm for tridiagonal Toeplitz systems

Diagonally dominant tridiagonal Toeplitz systems of linear equations arise in many application areas and have been well studied in the past. Modern interest in numerical linear algebra is often focusing on solving classic problems in parallel. In McNally [Fast parallel algorithms for tri-diagonal symmetric Toeplitz systems, MCS Thesis, University of New Brunswick, Saint John, 1999], an m processor Split & Correct algorithm was presented for approximating the solution to a symmetric tridiagonal Toeplitz linear system of equations. Nemani [Perturbation methods for circulant-banded systems and their parallel implementation, Ph.D. Thesis, University of New Brunswick, Saint John, 2001] and McNally (2003) adapted the works of Rojo [A new method for solving symmetric circulant tri-diagonal system of linear equations, Comput. Math. Appl. 20 (1990) 61–67], Yan and Chung [A fast algorithm for solving special tri-diagonal systems, Computing 52 (1994) 203–211] and McNally et al. [A split-correct parallel algorithm for solving tri-diagonal symmetric Toeplitz systems, Internat. J. Comput. Math. 75 (2000) 303–313] to the non-symmetric case. In this paper we present relevant background from these methods and then introduce an m processor scalable communication-less approximation algorithm for solving a diagonally dominant tridiagonal Toeplitz system of linear equations.     

A fast modified sine transform for solving block-tridiagonal systems with Toeplitz blocks

In this report we consider block-tridiagonal systems with Toeplitz blocks. Each block is of sizen×n consisting ofn _c×n _c matrices as entries, and there arem×m blocks in the system. The solution of those systems consists of 2n _c m modified sine transforms and an intermediate solution ofn block-tridiagonal systems. Symmetries in the data vectors are exploited such that one modified sine transform can be computed in terms of one Fourier transform of half the length of the original one, hence requiringO(2.5nlog₂ n) operations. Similarly, we only have to solve (n+1)/2 of the intermediate systems due to symmetry.This work was supported by the Swedish National Board for Industrial and Technical Development, NUTEK, under contract No. 89-02539 P.     

三对角与五对角Toeplitz矩阵求逆的算法

提出了一种求三对角与五对角Toeplitz矩阵逆的快速算法,其思想为先将Toeplitz矩阵扩展为循环矩阵,再快速求循环矩阵的逆,进而运用恰当矩阵分块求原Toeplitz矩阵的逆的算法.算法稳定性较好且复杂度较低.数值例子显示了算法的有效性和稳定性,并指出了算法的适用范围.     

Preconditioned HSS method for large multilevel block Toeplitz linear systems via the notion of matrix‐valued symbol

We perform a spectral analysis of the preconditioned Hermitian/skew‐Hermitian splitting (PHSS) method applied to multilevel block Toeplitz linear systems in which the coefficient matrix T_n(f) is associated with a Lebesgue integrable matrix‐valued function f. When the preconditioner is chosen as a Hermitian positive definite multilevel block Toeplitz matrix T_n(g), the resulting sequence of PHSS iteration matrices M_n belongs to the generalized locally Toeplitz class. In this case, we are able to compute the symbol ?(f,g) describing the asymptotic eigenvalue distribution of M_nwhen n→∞ and the matrix size diverges. By minimizing the infinity norm of the spectral radius of the symbol ?(f,g), we are also able to identify effective PHSS preconditioners T_n(g) for the matrix T_n(f). A number of numerical experiments are presented and commented, showing that the theoretical results are confirmed and that the spectral analysis leads to efficient PHSS methods. Copyright © 2015 John Wiley & Sons, Ltd.     

SQP algorithms for solving Toeplitz matrix approximation problem

Given an n × n matrix F, we find the nearest symmetric positive semi‐definite Toeplitz matrix T to F. The problem is formulated as a non‐linear minimization problem with positive semi‐definite Toeplitz matrix as constraints. Then a computational framework is given. An algorithm with rapid convergence is obtained by l₁ Sequential Quadratic Programming (SQP) method. Copyright © 2002 John Wiley & Sons, Ltd.     

Superlinear PCG methods for symmetric Toeplitz systems

In this paper we deal with the solution, by means of preconditioned conjugate gradient (PCG) methods, of symmetric Toeplitz systems with nonnegative generating function . Here the function is assumed to be continuous and strictly positive, or is assumed to have isolated zeros of even order. In the first case we use as preconditioner the natural and the optimal approximation of proposed by Bini and Di Benedetto, and we prove that the related PCG method has a superlinear rate of convergence and a total arithmetic cost of ops. Under the second hypothesis we cannot guarantee that the natural matrix is positive definite, while for the optimal we show that, in the ill-conditioned case, this can be really a bad choice. Consequently, we define a new matrix for preconditioning the given system; then, by applying the Sherman-Morrison-Woodbury inversion formula to the preconditioned system, we introduce a small, constant number of subsidiary systems which can be solved again by means of the previous PCG method. Finally, we perform some numerical experiments that show the effectiveness of the devised technique and the adherence with the theoretical analysis.

     

关于Toeplitz矩阵的某些注记

In this paper,we study real symmetric Toeplitz matrices commutable with tridi-agonal matrices, present more detailed results than those in [1], and extend them to non-symmetric Toeplitz matrices. Also, complex Toeplitz matrices, especially the corresponding matrices of lower order, are discussed.     

A parallel algorithm for solving the linear complementarity problem

The concept of multitasking mathematical programs is discussed, and an application of multitasking to the multiple-cost-row linear programming problem is considered. Based on this, an algorithm for solving the Linear Complementarity Problem (LCP) in parallel is presented. A variety of computational results are presented using this multitasking approach on the CRAY X-MP/48. These results were obtained for randomly generated LCP's where thenxn dense matrixM has no special properties (hence, the problem is NP-hard). based on these results, an average time performance ofO(n ⁴) is observed.     

Parallel algorithms for solving tridiagonal and near-circulant systems

Many problems in mathematics and applied science lead to the solution of linear systems having circulant coefficient matrices. This paper presents a new stable method for the exact solution of non-symmetric tridiagonal circulant linear systems of equations. The method presented in this paper is quite competitive with Gaussian elimination both in terms of arithmetic operations and storage requirements. It is also competitive with the modified double sweep method. This method can be applied to solve the near-circulant tridiagonal system. In addition, the method is modified to allow for parallel processing.     

A derivation of the Levinson algorithm for solving linear systems with symmetric positive definite Toeplitz matrix

Based on an orthogonalization technique, published earlier in this journal, a derivation is given of the Levinson algorithm for solving systems with a symmetric positive definite Toeplitz matrix.