分块K—循环Toeplitz矩阵求逆的快速付氏变换法

1算法描述及推导 Toeplitz矩阵及Toeplitz系统的求解在谱分析、线性预测、误差控制码、自回归滤波器设计等领域内起着重要的作用~[1-3]，而分块Toeplitz矩阵在计算机的时序分析、自回归时序模型滤波中也经常出现~[4]。对一般Toeplitz矩阵求逆，其算术复杂性为O(n~2)~[5]-[6]，其中n为Toepleitz矩阵的阶，而K-循环Toeplitz矩阵的求逆，其算术复杂性可降为O(nlog_2n)，本文提供了mn附分块K-循环Toeplitz矩阵求逆的一种快速付氏变换算法，其算术复杂性为O（mnlog_2mn）.     

多重三角T阵与多元多项式的快速除法

我们在[1]中给出了求三角形T矩阵的逆和计算一元多项式除法的O(nlogn)算法,改进了这两个问题已有的工作量为O(nlog~2n)的快速算法。本文给出了多重三角T阵的乘积、求逆和多元多项式的快速除法等快速方法,推广了[1]和[2]的结果。为叙述简便,我们仅就二重上三角形T阵与二元多项式除法讨论。由此不难推广到一般情形。     

一个求三对角矩阵的逆的并行算法

三对角矩阵的求逆问题是实际计算中经常遇到的。本文是以附加矩阵求逆法为基础,提出求这类矩阵的逆矩阵的一个并行计算格式。对于n阶矩阵,这个格式的时间界是0(log_2n),所需的处理机台数是0(n~2)为界。而以高斯法为基础的求逆并行计算法,运算的时间界是0(n),所需的处理机台数是以0(n)为界。     

求鳞状因子循环矩阵的逆阵及广义逆阵的快速付氏变换法

借助快速付立叶变换(FFT),本文给出一种求n阶鳞状因子循环矩阵的逆阵、自反g-逆、群逆、Moore-Penrose逆的快速算法,该算法的计算复杂性为O(nlog2n),最后给出的两个数值算例表明了该算法的有效性.     

Vandermonde行列式的快速并行算法

n阶Vandermonder行列式的求值通常需要O(n~2)次算术运算．本文从计算复杂性的角度出发，给出一种求Vandermonde行列式、合流型Vandermonde行列式、广义Vandermonde行列式的快速算法．该算法仅需O(nlog~2n)次算术运算．若在n台处理机上并行计算，该算法需并行步数O(nlog_(2~2)n)．速度倍数为s_p=O(n)．并行效率为O(1)．     

r-对称循环矩阵及逆矩阵三角分解的快速算法

根据r-对称循环矩阵的特殊结构给出了求这类矩阵本身及其逆矩阵三角分解的快速算法,算法的运算量均为O(n2),一般矩阵及逆矩阵三角分解的运算量均为O(n3).     

关于并行计算中的等价性定理与Toeplitz三对角方程组的并行解

一、关于L.Csanky的等价性定理 1976年,L.Csanky发表了并行计算中的重要理论结果。这一结论指出,对阵列式理论模型,求解线性代数方程组、矩阵求逆、行列式求值和求矩阵的特征多项式,在并行时间复杂性上是等价的。Csanky还给出了N阶矩阵求逆的两种O(log_2~2N)算法,使用的处理机台数分别为O(N~5)和O(N~4)。在这之前,所有求逆算法的并行步数不低于O(N)。Wang Guo-rong等已给出了求广义逆A~ 和A_(MN)~ 的一种复杂性相当的并行算法,并建     

求Toeplitz矩阵各阶主子式和特征值的O(n~2)算法

形如T~(n)=(T_(ij)~(n))_(n×n),T_(ij)~(n)=t_(i-j),i,j=1～n的n阶矩阵称为Toeplitz矩阵。 Toeplitz矩阵(简称T矩阵)是一类很重要的特殊矩阵,地震预报、天气预测、石油勘探等许多应用领域的数学模型中常常遇到T型矩阵,因此研究其快速算法具有很大的实用价值。1964年,W.F.Trench在对称正定的条件下给出了T矩阵求逆的O(n~2)算法。1969年,S.Zohar进一步讨论了Trench的算法,主要工作是对推导的简化以及把对称正定的条件减弱为强非奇(即各阶主子式全不为零),算法的主要思想请参阅文[1]或[2]。     

分块带状矩阵的逆

1引言如果分块矩阵A=(A_(ij))_(n×n)满足A_(ij)=O(j-i＞p且i-j＞q),其中A_(ij)为m阶矩阵,则称A为(p,q)-分块带状矩阵．分块带状矩阵在一些实际问题中经常出现,例如在量子场论中用途很广的非线性Schr(?)dinger方程的差分离散问题,解热传导问题等,都会遇到分块带状矩阵．常见的分块三对角矩阵,分块五对角矩阵都是特殊的分块带状矩阵．采用通常的方法求解分块带状矩阵的逆矩阵时,需要进行O(n~3)次m阶矩阵的运算．本文首先将分块带状矩阵扩充成可逆的分块上(下)三角矩阵,利用其逆矩阵导出了分块带状矩阵的逆矩阵表达式;进而利用所得到的公式分别推导了分块三对角矩阵及分块五对角矩阵的逆矩阵的快速算法,所需运算量为O(n~2)次m阶矩阵的运算．本文的结果扩充了文[1]等关于分块三对角阵求逆的相关结果．     

关于(R,r)-循环分块矩阵求逆与相乘的一种快速算法

利用矩阵分块逐次降阶的方法和快速富里叶变换(FFT),给出了mn阶(R,r)-循环分块矩阵求逆与相乘的一种快速算法,证明了其计算复杂性为O(mnlog2mn).     

Inverses and eigenpairs of tridiagonal Toeplitz matrix with opposite-bordered rows

In this paper, tridiagonal Toeplitz matrix (type I, type II) with opposite-bordered rows are introduced. Main attention is paid to calculate the determinants, the inverses and the eigenpairs of these matrices. Specifically, the determinants of an $n\times n$ tridiagonal Toeplitz matrix with opposite-bordered rows can be explicitly expressed by using the $(n-1)$th Fibonacci number, the inversion of the tridiagonal Toeplitz matrix with opposite-bordered rows can also be explicitly expressed by using the Fibonacci numbers and unknown entries from the new matrix. Besides, we give the expression of eigenvalues and eigenvectors of the tridiagonal Toeplitz matrix with opposite-bordered rows. In addition, some algorithms are presented based on these theoretical results. Numerical results show that the new algorithms have much better computing efficiency than some existing algorithms studied recently.     

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.     

关于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 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.     

Analytical inversion of general periodic tridiagonal matrices

In this paper we present an analytical forms for the inversion of general periodic tridiagonal matrices, and provide some very simple analytical forms which immediately lead to closed formulae for some special cases such as symmetric or perturbed Toeplitz for both periodic and non-periodic tridiagonal matrices. An efficient computational algorithm for finding the inverse of any general periodic tridiagonal matrices from the analytical form is given, it is suited for implementation using Computer Algebra systems such as MAPLE, MATLAB, MACSYMA, and MATHEMATICA. An example is also given to illustrate the algorithm.     

Eigenvector sensitivity under general and structured perturbations of tridiagonal Toeplitz‐type matrices

The sensitivity of eigenvalues of structured matrices under general or structured perturbations of the matrix entries has been thoroughly studied in the literature. Error bounds are available, and the pseudospectrum can be computed to gain insight. Few investigations have focused on analyzing the sensitivity of eigenvectors under general or structured perturbations. This paper discusses this sensitivity for tridiagonal Toeplitz and Toeplitz‐type matrices.     

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.     

Bounds for the extremal eigenvalues of a class of symmetric tridiagonal matrices with applications

We consider a class of symmetric tridiagonal matrices which may be viewed as perturbations of Toeplitz matrices. The Toeplitz structure is destroyed since two elements on each off-diagonal are perturbed. Based on a careful analysis, we derive sharp bounds for the extremal eigenvalues of this class of matrices in terms of the original data of the given matrix. In this way, we also obtain a lower bound for the smallest singular value of certain matrices. Some numerical results indicate that our bounds are extremely good.     

The rate of convergence of GMRES on a tridiagonal toeplitz linear system. II

This paper continues the recent work of the authors’ [R.-C. Li, W. Zhang, The rate of convergence of GMRES on a tridiagonal Toeplitz linear system, Numer. Math. 112 (2009) 267-293 (electronically published on 19 December 2008)] on the rate of convergence of GMRES for a tridiagonal Toeplitz linear system Ax=b. Much simpler formulas than the earlier ones for GMRES residuals when b is the first or the last column of the identity matrix are established, and these formulas allow us to confirm the rate of convergence that was conjectured but only partially proven earlier. Simpler and sharper bounds than earlier ones when all b’s entries, except its first and last ones, are zeros are also obtained.     

Stability of Gaussian elimination without pivoting on tridiagonal Toeplitz matrices

Using the simple vehicle of tridiagonal Toeplitz matrices, the question of whether one must pivot during the Gauss elimination procedure is examined. An exact expression for the multipliers encountered during the elimination process is given. It is then shown that for a prototype Helmholtz problem, one cannot guarantee that elimination without pivoting is stable.