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.     

矩阵值Caratheodory函数广义块Pick矩阵的秩不变性

Lasarow^[1]推导出矩阵值Carath\'{e}odory函数的第一、第二型广义块Pick矩阵及其变型的秩不变性. 这些矩阵由同一个Carath\'{e}odory函数的值与它的直到某阶的导数值确定. 利用文献[2]中提出的块Toeplitz向量方法, 该文断言,这些块矩阵的秩分别相关并重合于具有秩不变性的块Toeplitz矩阵的秩, 从而改进了这两类广义块Pick矩阵的秩不变性结论的证明.     

Toeplitz operators on weightedl p spaces and associated asymptotics

Asymptotic information is found in this paper for finite Toeplitz matrices generated by a piecewise continuous function. The eigenvalues for certain finite matrices are shown to lie near the range of the generating function. An asymptotic formula for f( _i ) where _i are the eigenvalues is also given. The basic technique of the paper is to get the above type of asymptotic information by studying the ordinary Toeplitz operators on weightedl _p spaces.     

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.     

Block band Toeplitz preconditioners derived from generating function approximations: analysis and applications

We are concerned with the study and the design of optimal preconditioners for ill-conditioned Toeplitz systems that arise from a priori known real-valued nonnegative generating functions f(x,y) having roots of even multiplicities. Our preconditioned matrix is constructed by using a trigonometric polynomial θ(x,y) obtained from Fourier/kernel approximations or from the use of a proper interpolation scheme. Both of the above techniques produce a trigonometric polynomial θ(x,y) which approximates the generating function f(x,y), and hence the preconditioned matrix is forced to have clustered spectrum. As θ(x,y) is chosen to be a trigonometric polynomial, the preconditioner is a block band Toeplitz matrix with Toeplitz blocks, and therefore its inversion does not increase the total complexity of the PCG method. Preconditioning by block Toeplitz matrices has been treated in the literature in several papers. We compare our method with their results and we show the efficiency of our proposal through various numerical experiments.This research was co-funded by the European Union in the framework of the program “Pythagoras I” of the “Operational Program for Education and Initial Vocational Training” of the 3rd Community Support Framework of the Hellenic Ministry of Education, funded by national sources (25%) and by the European Social Fund - ESF (75%). The work of the second and of the third author was partially supported by MIUR (Italian Ministry of University and Research), grant number 2004015437.     

Semiconvergence of block SOR method for singular linear systems with p-cyclic matrices

In this paper, we discuss semiconvergence of the block SOR method for solving singular linear systems with p-cyclic matrices. Some sufficient conditions for the semiconvergence of the block SOR method for solving a general p-cyclic singular system are proved.     

Rotationally Invariant Rank 1 Convex Functions

Let f be a function on the set M ⁿ xn of all n by n real matrices. If f is rotationally invariant with respect to the proper orthogonal group, it has a representation \tilde f through the signed singular values of the matrix argument ?∈ M^nxn. Necessary and sufficient conditions are given for the rank 1 convexity of f in terms of \tilde f . Accepted 20 December 2000. Online Publication 18 May, 2001.     

The Szegő and Avram–Parter theorems for general test functions

The Szegő and Avram–Parter theorems give the limit of the arithmetic mean of the values of certain test functions at the eigenvalues of Hermitian Toeplitz matrices and the singular values of arbitrary Toeplitz matrices, respectively, as the matrix dimension goes to infinity. We show that, surprisingly, these theorems are not true for every continuous, nonnegative, and monotonously increasing test function and thus do not hold whenever they make sense. On the other hand, we prove the two theorems in a general form which includes all versions known so far. To cite this article: A. Böttcher et al., C. R. Acad. Sci. Paris, Ser. I 346 (2008).     

Inverse generating function approach for the preconditioning of Toeplitz‐block systems

As proposed by R. H. Chan and M. K. Ng (1993), linear systems of the form T [ f ] x = b , where T [ f ] denotes the n×n Toeplitz matrix generated by the function f, can be solved using iterative solvers with as a preconditioner. This article aims at generalizing this approach to the case of Toeplitz‐block matrices and matrix‐valued generating functions F . We prove that if F is Hermitian positive definite, most eigenvalues of the preconditioned matrix T [ F ⁻¹]T[ F ] are clustered around one. Numerical experiments demonstrate the performance of this preconditioner.     

Construction of Matrices with Prescribed Singular Values and Eigenvalues

Two issues concerning the construction of square matrices with prescribe singular values an eigenvalues are addressed. First, a necessary and sufficient condition for the existence of an n × n complex matrix with n given nonnegative numbers as singular values an m ( n) given complex numbers to be m of the eigenvalues is determined. This extends the classical result of Weyl and Horn treating the case when m = n. Second, an algorithm is given to generate a triangular matrix with prescribe singular values an eigenvalues. Unlike earlier algorithms, the eigenvalues can be arranged in any prescribe order on the diagonal. A slight modification of this algorithm allows one to construct a real matrix with specified real an complex conjugate eigenvalues an specified singular values. The construction is done by multiplication by diagonal unitary matrices, permutation matrices and rotation matrices. It is numerically stable and may be useful in developing test software for numerical linear algebra packages.     

Pushing the envelope of the test functions in the Szegö and Avram–Parter theorems

The Szegö and Avram–Parter theorems give the limit of the arithmetic mean of the values of certain test functions at the eigenvalues of Hermitian Toeplitz matrices and the singular values of arbitrary Toeplitz matrices, respectively, as the matrix dimension goes to infinity. The question on whether these theorems are true whenever they make sense is essentially the question on whether they are valid for all continuous, nonnegative, and monotonously increasing test functions. We show that, surprisingly, the answer to this question is negative. On the other hand, we prove the two theorems in a general form which includes all versions known so far.     

On Semiconvexity Properties of Rotationally Invariant Functions in Two Dimensions

Let f be a function defined on the set M ^2×2 of all 2 by 2 matrices that is invariant with respect to left and right multiplications of its argument by proper orthogonal matrices. The function f can be represented as a function of the signed singular values of its matrix argument. The paper expresses the ordinary convexity, polyconvexity, and rank 1 convexity of f in terms of its representation      

Existence of Solutions to a Singular Initial Value Problem

Under the sign assumptions we investigate the global existence of solutions of the initial value problem x＇ =f（t, x, x＇）, x（0） = A, where the scalar function f（t, x,p） may be singular at x = A.     

Formulas for the Inverses of Toeplitz Matrices with Polynomially Singular Symbols

We consider large finite Toeplitz matrices with symbols of the form (1– cos )^p f() where p is a natural number and f is a sufficiently smooth positive function. By employing techniques based on the use of predictor polynomials, we derive exact and asymptotic formulas for the entries of the inverses of these matrices. We show in particular that asymptotically the inverse matrix mimics the Green kernel of a boundary value problem for the differential operator Submitted: June 20, 2003     

Equilibrium problem for the eigenvalues of banded block Toeplitz matrices

We consider banded block Toeplitz matrices T_n with n block rows and columns. We show that under certain technical assumptions, the normalized eigenvalue counting measure of T_n for n → ∞ weakly converges to one component of the unique vector of measures that minimizes a certain energy functional. In this way we generalize a recent result of Duits and Kuijlaars for the scalar case. Along the way we also obtain an equilibrium problem associated to an arbitrary algebraic curve, not necessarily related to a block Toeplitz matrix. For banded block Toeplitz matrices, there are several new phenomena that do not occur in the scalar case: (i) The total masses of the equilibrium measures do not necessarily form a simple arithmetic series but in general are obtained through a combinatorial rule; (ii) The limiting eigenvalue distribution may contain point masses, and there may be attracting point sources in the equilibrium problem; (iii) More seriously, there are examples where the connection between the limiting eigenvalue distribution of T_n and the solution to the equilibrium problem breaks down. We provide sufficient conditions guaranteeing that no such breakdown occurs; in particular we show this if T_n is a Hessenberg matrix.     

Band plus algebra preconditioners for two-level Toeplitz systems

In this paper we are interested in the fast and efficient solution of nm×nm symmetric positive definite ill-conditioned Block Toeplitz with Toeplitz Blocks (BTTB) systems of the form T _nm (f)x=b, where the generating function f is a priori known. The preconditioner that we propose and analyze is an extension of the one proposed in (D. Noutsos and P. Vassalos, Comput. Math. Appl., 56 (2008), pp. 1255–1270) and it arises as a product of a Block band Toeplitz matrix and matrices that may belong to any trigonometric matrix algebra. The underlying idea of the proposed scheme is to embody the well known advantages characterizing each component of the product when used alone. As a result we obtain spectral equivalence and a weak clustering of the eigenvalues of the preconditioned matrix around unity, ensuring the convergence of the Preconditioned Conjugate Gradient (PCG) method with a number of iterations independent of the partial dimensions. Finally, we compare our method with techniques already employed in the literature. A wide range of numerical experiments confirms the effectiveness of the proposed procedure and the adherence to the theoretical analysis.     

Circulant Preconditioners for Indefinite Toeplitz Systems

In recent papers circulant preconditioners were proposed for ill-conditioned Hermitian Toeplitz matrices generated by 2-periodic continuous functions with zeros of even order. It was show that the spectra of the preconditioned matrices are uniformly bounded except for a finite number of outliers and therefore the conjugate gradient method, when applied to solving these circulant preconditioned systems, converges very quickly. In this paper, we consider indefinite Toeplitz matrices generated by 2-periodic continuous functions with zeros of odd order. In particular, we show that the singular values of the preconditioned matrices are essentially bounded. Numerical results are presented to illustrate the fast convergence of CGNE, MINRES and QMR methods.This revised version was published online in October 2005 with corrections to the Cover Date.     

Spectral and Computational Analysis of Block Toeplitz Matrices Having Nonnegative Definite Matrix-Valued Generating Functions

It is well known that the generating function f L ¹([–, ], ) of a class of Hermitian Toeplitz matrices A _n(f) _n describes very precisely the spectrum of each matrix of the class. In this paper we consider n × n Hermitian block Toeplitz matrices with m × m blocks generated by a Hermitian matrix-valued generating function f L ¹([–, ], C ^m×m ). We extend to this case some classical results by Grenander and Szegö holding when m = 1 and we generalize the Toeplitz preconditioning technique introduced in the scalar case by R. H. Chan and F. Di Benedetto, G. Fiorentino and S. Serra. Finally, concerning the spectra of the preconditioned matrices, some asymptotic distribution properties are demonstrated and, in particular, a Szegö-style theorem is proved. A few numerical experiments performed at the end of the paper confirm the correctness of the theoretical analysis.     

Fast Structured Matrix Computations: Tensor Rank and Cohn–Umans Method

We discuss a generalization of the Cohn–Umans method, a potent technique developed for studying the bilinear complexity of matrix multiplication by embedding matrices into an appropriate group algebra. We investigate how the Cohn–Umans method may be used for bilinear operations other than matrix multiplication, with algebras other than group algebras, and we relate it to Strassen’s tensor rank approach, the traditional framework for investigating bilinear complexity. To demonstrate the utility of the generalized method, we apply it to find the fastest algorithms for forming structured matrix–vector product, the basic operation underlying iterative algorithms for structured matrices. The structures we study include Toeplitz, Hankel, circulant, symmetric, skew-symmetric, f-circulant, block Toeplitz–Toeplitz block, triangular Toeplitz matrices, Toeplitz-plus-Hankel, sparse/banded/triangular. Except for the case of skew-symmetric matrices, for which we have only upper bounds, the algorithms derived using the generalized Cohn–Umans method in all other instances are the fastest possible in the sense of having minimum bilinear complexity. We also apply this framework to a few other bilinear operations including matrix–matrix, commutator, simultaneous matrix products, and briefly discuss the relation between tensor nuclear norm and numerical stability.     

On the distribution singular values of Toeplitz matrices

We prove a second order formula concerning distribution of singular values of Toeplitz matrices in some cases when conditions of the H. Widom Theorem are not satisfied.