Look-ahead Levinson and Schur algorithms for non-Hermitian Toeplitz systems

Summary. We present generalizations of the nonsymmetric Levinson and Schur algorithms for non-Hermitian Toeplitz matrices with some singular or ill-conditioned leading principal submatrices. The underlying recurrences allow us to go from any pair of successive well-conditioned leading principal submatrices to any such pair of larger order. If the look-ahead step size between these pairs is bounded, our generalized Levinson and Schur recurrences require $ operations, and the Schur recurrences can be combined with recursive doubling so that an $ algorithm results. The overhead (in operations and storage) of look-ahead steps is very small. There are various options for applying these algorithms to solving linear systems with Toeplitz matrix. Received July 26, 1993     

A look-ahead algorithm for the solution of general Hankel systems

Summary The solution of systems of linear equations with Hankel coefficient matrices can be computed with onlyO(n ²) arithmetic operations, as compared toO(n ³) operations for the general cases. However, the classical Hankel solvers require the nonsingularity of all leading principal submatrices of the Hankel matrix. The known extensions of these algorithms to general Hankel systems can handle only exactly singular submatrices, but not ill-conditioned ones, and hence they are numerically unstable. In this paper, a stable procedure for solving general nonsingular Hankel systems is presented, using a look-ahead technique to skip over singular or ill-conditioned submatrices. The proposed approach is based on a look-ahead variant of the nonsymmetric Lanczos process that was recently developed by Freund, Gutknecht, and Nachtigal. We first derive a somewhat more general formulation of this look-ahead Lanczos algorithm in terms of formally orthogonal polynomials, which then yields the look-ahead Hankel solver as a special case. We prove some general properties of the resulting look-ahead algorithm for formally orthogonal polynomials. These results are then utilized in the implementation of the Hankel solver. We report some numerical experiments for Hankel systems with ill-conditioned submatrices.The research of the first author was supported by DARPA via Cooperative Agreement NCC 2-387 between NASA and the Universities Space Research Association (USRA).The research of the second author was supported in part by NSF grant DRC-8412314 and Cooperative Agreement NCC 2-387 between NASA and the Universities Space Research Association (USRA).     

Symmetric Gaussian elimination for cauchy-type matrices with application to positive definite Toeplitz matrices

The problem of solving linear equations with a Toeplitz matrix appears in many applications. Often is positive definite but ill-conditioned with many small eigenvalues. In this case fast and superfast algorithms may show a very poor behavior or even break down. In recent papers the transformation of a Toeplitz matrix into a Cauchy-type matrix is proposed. The resulting new linear equations can be solved in operations using standard pivoting strategies which leads to very stable fast methods also for ill-conditioned systems. The basic tool is the formulation of Gaussian elimination for matrices with low displacement rank. In this paper, we will transform a Hermitian Toeplitz matrix into a Cauchy-type matrix by applying the Fourier transform. We will prove some useful properties of and formulate a symmetric Gaussian elimination algorithm for positive definite . Using the symmetry and persymmetry of we can reduce the total costs of this algorithm compared with unsymmetric Gaussian elimination. For complex Hermitian , the complexity of the new algorithm is then nearly the same as for the Schur algorithm. Furthermore, it is possible to include some strategies for ill-conditioned positive definite matrices that are well-known in optimization. Numerical examples show that this new algorithm is fast and reliable. Received March 24, 1995 / Revised version received December 13, 1995     

Recurrence relation for biorthogonal polynomials

We use a geometric approach to obtain a recurrence relation for two families of biorthogonal polynomials associated to a nonsingular, strongly regular matrix M. We propose a “look-ahead procedure” for computing the biorthogonal polynomials when M has singular or ill-conditioned leading principal submatrices. These polynomials lead to two recursive triangular factorizations for the inverse of a nonsingular matrix M which is not necessarily strongly regular.     

QR factorization of Toeplitz matrices

Summary This paper presents a new algorithm for computing theQR factorization of anm×n Toeplitz matrix inO(mn) operations. The algorithm exploits the procedure for the rank-1 modification and the fact that both principal (m–1)×(n–1) submatrices of the Toeplitz matrix are identical. An efficient parallel implementation of the algorithm is possible.     

Computation of matrix-valued formally orthogonal polynomials and applications

We present a computational procedure for generating formally orthogonal polynomials associated with a given bilinear Hankel form with rectangular matrix-valued moments. Our approach covers the most general case of moments of any size and is not restricted to square moments. Moreover, our algorithm has a built-in deflation procedure to handle linearly dependent or almost linearly dependent columns and rows of the block Hankel matrix associated with the bilinear form. Possible singular or close-to-singular leading principal submatrices of the deflated block Hankel matrix are avoided by means of look-ahead techniques. Applications of the computational procedure to eigenvalue computations, reduced-order modeling, the solution of multiple linear systems, and the fast solution of block Hankel systems are also briefly described.     

Stability analysis and fast algorithms for triangularization of Toeplitz matrices

Summary. A new algorithm for triangularizing an Toeplitz matrix is presented. The algorithm is based on the previously developed recursive algorithms that exploit the Toeplitz structure and compute each row of the triangular factor via updating and downdating steps. A forward error analysis for this existing recursive algorithm is presented, which allows us to monitor the conditioning of the problem, and use the method of corrected semi-normal equations to obtain higher accuracy for certain ill-conditioned matrices. Numerical experiments show that the new algorithm improves the accuracy significantly while the computational complexity stays in . Received April 30, 1995 / Revised version received February 12, 1996     

Using the Sherman-Morrison-Woodbury inversion formula for a fast solution of tridiagonal block Toeplitz systems

A fast numerical algorithm for solving systems of linear equations with tridiagonal block Toeplitz matrices is presented. The algorithm is based on a preliminary factorization of the generating quadratic matrix polynomial associated with the Toeplitz matrix, followed by the Sherman-Morrison-Woodbury inversion formula and solution of two bidiagonal and one diagonal block Toeplitz systems. Tight estimates of the condition numbers are provided for the matrix system and the main matrix systems generated during the preliminary factorization. The emphasis is put on rigorous stability analysis to rounding errors of the Sherman-Morrison-Woodbury inversion. Numerical experiments are provided to illustrate the theory.     

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.     

Backward stability of a pivoting strategy for sign-regular linear systems

A matrixA issign-regular if, for each orderk, allk×k submatrices ofA have determinant with the same sign. In this paper, a pivoting strategy ofO(n) operations for the Gaussian elimination of linear systems whose coefficient matrices are sign-regular is proposed. Backward error analysis of this pivoting strategy is performed and small error bounds are obtained. Our results can also be applied to linear systems whose coefficient matrices have sign-regular inverses.     

A method of matrix inverse triangular decomposition based on contiguous principal submatrices

An algorithm is presented which performs the triangular decomposition of the inverse of a given matrix. The method is applicable to any matrix all contiguous principal submatrices of which are nonsingular. The algorithm is particularly efficient when the matrix has certain partial symmetries exhibited by the Toeplitz structure.     

Convergence of the Multigrid Method of Ill-conditioned Block Toeplitz Systems

We study the solutions of block Toeplitz systems A _mn u = b by the multigrid method (MGM). Here the block Toeplitz matrices A _mn are generated by a nonnegative function f (x,y) with zeros. Since the matrices A _mn are ill-conditioned, the convergence factor of classical iterative methods will approach 1 as the size of the matrices becomes large. These classical methods, therefore, are not applicable for solving ill-conditioned systems. The MGM is then proposed in this paper. For a class of block Toeplitz matrices, we show that the convergence factor of the two-grid method (TGM) is uniformly bounded below 1 independent of mn and the full MGM has convergence factor depending only on the number of levels. The cost per iteration for the MGM is of O(mn log mn) operations. Numerical results are given to explain the convergence rate.     

MGM Optimal convergence for certain (multilevel) structured linear systems

We present a multigrid algorithm to solve linear systems whose coefficient metrices belongs to circulant, Hartley or τ multilevel algebras and are generated by a nonnegative multivariate polynomial f. It is known that these matrices are banded (with respect to their multilevel structure) and their eigenvalues are obtained by sampling f on uniform meshes, so they are ill‐conditioned (or singular, and need some corrections) whenever f takes the zero value. We prove the proposed metod to be optimal even in presence of ill‐conditioning: if the multilevel coefficient matrix has dimension ni at level i, i = 1, … , d, then only ni operations are required on each iteration, but the convergence rate keeps constant with respect to N(n) as it depends only on f. The algorithm can be extended to multilevel Toeplitz matrices too.     

Improved Newton’s method without direct function evaluations

For solving systems of nonlinear equations, we have recently developed a Newton’s method to manage issues with inaccurate function values or problems with high computational cost. In this work we introduce a modification of the above method, reducing the total computational cost and improving, in general, its overall performance. Moreover, the proposed version retains the quadratic convergence, the good behavior over singular and ill-conditioned cases of Jacobian matrix, and its capability to be ideal for imprecise function problems. Numerical results demonstrate the efficiency of the new proposed method.     

A direct method to solve block banded block Toeplitz systems with non-banded Toeplitz blocks

A fast solution algorithm is proposed for solving block banded block Toeplitz systems with non-banded Toeplitz blocks. The algorithm constructs the circulant transformation of a given Toeplitz system and then by means of the Sherman-Morrison-Woodbury formula transforms its inverse to an inverse of the original matrix. The block circulant matrix with Toeplitz blocks is converted to a block diagonal matrix with Toeplitz blocks, and the resulting Toeplitz systems are solved by means of a fast Toeplitz solver.The computational complexity in the case one uses fast Toeplitz solvers is equal to ξ(m,n,k)=O(mn³)+O(k³n³) flops, there are m block rows and m block columns in the matrix, n is the order of blocks, 2k+1 is the bandwidth. The validity of the approach is illustrated by numerical experiments.     

A fast algorithm for solving diagonally dominant symmetric pentadiagonal Toeplitz systems

Banded Toeplitz systems of linear equations arise in many application areas and have been well studied in the past. Recently, significant advancement has been made in algorithm development of fast parallel scalable methods to solve tridiagonal Toeplitz problems. In this paper we will derive a new algorithm for solving symmetric pentadiagonal Toeplitz systems of linear equations based upon a technique used in [J.M. McNally, L.E. Garey, R.E. Shaw, A split-correct parallel algorithm for solving tri-diagonal symmetric Toeplitz systems, Int. J. Comput. Math. 75 (2000) 303-313] for tridiagonal Toeplitz systems. A common example which arises in natural quintic spline problems will be used to demonstrate the algorithm’s effectiveness. Finally computational results and comparisons will be presented.     

Optimized look-ahead recurrences for adjacent rows in the Padé table

A new look-ahead algorithm for recursively computing Padé approximants is introduced. It generates a subsequence of the Padé approximants on two adjacent rows (defined by fixed numerator degree) of the Padé table. Its two basic versions reduce to the classical Levinson and Schur algorithms if no look-ahead is required. The new algorithm can be viewed as a combination of the look-ahead sawtooth and the look-ahead Levinson and Schur algorithms that we proposed before, but now the look-ahead step size is minimal (as in the sawtooth version) and the computational costs are as low as in the least expensive competing algorithms (including our look-ahead Levinson and Schur algorithms). The underlying recurrences link well-conditioned basic pairs,i.e., pairs of sufficiently different neighboring Padé forms.The algorithm can be used to solve Toeplitz systems of equationsTx = b. In this application it comes in several versions: anO(N ²) Levinson-type form, anO(N ²) Schur-type form, and a superfastO(N log² N) Schur-type version. As an option of the first two versions, the corresponding block LDU decompositions ofT ^–1 orT, respectively, can be found.     

基于均值的Toeplitz矩阵填充的子空间算法

本文提出一种基于均值的Toeplitz矩阵填充的子空间算法.通过在左奇异向量空间中对已知元素的最小二乘逼近,形成了新的可行矩阵;并利用对角线上的均值化使得迭代后的矩阵保持Toeplitz结构,从而减少了奇异向量空间的分解时间.理论上,证明了在一定条件下该算法收敛于一个低秩的Toeplitz矩阵.通过不同已知率的矩阵填充数值实验展示了Toeplitz矩阵填充的新算法比阈值增广Lagrange乘子算法在时间上和精度上更有效.     

Matrices of small Toeplitz rank,certain representations of the solution to an unstable system of linear equations with Toeplitz coefficient matrices,and related fast algorithms for solving such systems

Formulas for inverting regularized systems of linear equations whose coefficient matrices are complex, Toeplitz, and singular or nearly singular are derived. They make it possible to develop economical algorithms for solving such systems in mass calculations.     

Stability and performance analysis of a block elimination solver for bordered linear systems

A new block elimination method for bordered systems is proposedand its numerical properties are analysed. In the case wherethe leading principal block is ill-conditioned or singular andthe method becomes unstable a perturbation approach is usedto enhance the stability. Results of experiments performed onthe SGI Power Challenge 8000 and on the Cray J-9x illustratethe performance of the new algorithm and compare it with thecurrent best approach. It is shown that the new method worksfaster while preserving stability.