On regularity of block triangular fuzzy matrices

Necessary and sufficient conditions are given for the regularity of block triangular fuzzy matrices. This leads to characterization of idempotency of a class of triangular Toeplitz matrices. As an application, the existence of group inverse of a block triangular fuzzy matrix is discussed. Equivalent conditions for a regular block triangular fuzzy matrix to be expressed as a sum of regular block fuzzy matrices is derived. Further, fuzzy relational equations consistency is studied.     

A note on the spectral distribution of toeplitz matrices

An elementary and direct proof of the Szegö formula is given, for both eigen and singular values. This proof, which is based on tools from linear algebra and does not rely on the theory of Fourier series, simultaneously embraces multilevel Toeplitz matrices, block Toeplitz matrices and combinations of them. The assumptions on the generating

function f are as weak as possible; indeedf is a matrix-valued function of p variables, and it is only supposed to be integrable. In the case of singular values f(x), and hence the block p-level Toeplitz matrices it generates, are not even supposed to be square matrices. Moreover, in the asymptotic formulas for eigen and singular values the test functions involved are not required to have compact support.     

On algebras of Toeplitz fuzzy matrices

In this paper, necessary and sufficient conditions are given for a product of Toeplitz fuzzy matrices to be Toeplitz. As an application, a criterion for normality of Toeplitz fuzzy matrices is derived and conditions are deduced for symmetric idempotency of Toeplitz fuzzy matrices. We discuss similar results for Hankel fuzzy matrices. Keywords: Fuzzy matrix, Toeplitz and Hankel matrices.     

On inversion of hermitian block toeplitz matrices

A formula for the inverse of a hermitian block Toeplitz matrix via solutions of two block equations(instead of four in the general case) is given.     

Infinite analogues of block toeplitz matrices and related orthogonal functions

This paper concerns a class of infinite block matrices that are analogous to finite block Toeplitz matrices. Also studied are corresponding matrix-valued functions that are orthogonal for a matrixvalued inner product. An appendix presents basic results on orthogonalization in a Hilbert module.     

Block toeplitz operators with rational symbol analytic at infinity

This paper concerns the problem of explicit inversion of a block Toeplitz operator with rational and analytic at infinity symbol. The necessary and sufficient conditions for the invertibility and explicit formulas for the inverse are given in terms of the realization of the symbol.     

Asymptotically fast solution of toeplitz and related systems of linear equations

We present an inversion algorithm for the solution of a generic N X N Toeplitz system of linear equations with computational complexity O(Nlog²N) and storage requirements O(N). The algorithm relies upon the known structure of Toeplitz matrices and their inverses and achieves speed through a doubling method. All the results are derived and stated in terms of the recent concept of displacement rank, and this is used to extend the scope of the algorithm to include a wider class of matrices than just Toeplitz and also to include block Toeplitz matrices.     

On the Toeplitz embedding of an arbitrary matrix

It has been shown by Delosme and Morf that an arbitrary block matrix can be embedded into a block Toeplitz matrix; the dimension of this embedding depends on the complexity of the matrix structure compared to the block Toeplitz structure. Due to the special form of the embedding matrix, the algebra of matrix polynomials relative to block Toeplitz matrices can be interpreted directly in terms of the original matrix and therefore can be extended to arbitrary matrices. In fact, these polynomials turn out to provide an appropriate framework for the recently proposed generalized Levinson algorithm solving the general matrix inversion problem.     

Some extensions of Hankel and Toeplitz matrices

New necessary and sufficient conditions are given for a nonsingular matrix to have Hankel or Toeplitz form. Two generalizations, termed conjugate-Toeplitz and Leslie-Toeplitz matrices, are introduced A number of properties of Toeplitz matrices are shown to carry over to these extensions     

Matrices with block Toeplitz inverses

Conditions for a nonsingular matrix to have a block Toeplitz inverse are obtained. A simpler criterion for a block Toeplitz matrix to have a block Toeplitz inverse is also given. The results generalize those of Huang and Cline for Toeplitz matrices with scalar entries, for which alternative statements and proofs are also indicated.     

On the extreme eigenvalues of hermitian (block) toeplitz matrices

We are concerned with the behavior of the minimum (maximum) eigenvalue λ₀⁽ⁿ⁾ (λ_n⁽ⁿ⁾) of an (n + 1) × (n + 1) Hermitian Toeplitz matrix T_n(ƒ) where ƒ is an integrable real-valued function. Kac, Murdoch, and Szegö, Widom, Parter, and R. H. Chan obtained that λ₀⁽ⁿ⁾ — min ƒ = O(1/n^2k) in the case where ƒ C^2k, at least locally, and ƒ — inf ƒ has a zero of order 2k. We obtain the same result under the second hypothesis alone. Moreover we develop a new tool in order to estimate the extreme eigenvalues of the mentioned matrices, proving that the rate of convergence of λ₀⁽ⁿ⁾ to inf ƒ depends only on the order ρ (not necessarily even or integer or finite) of the zero of ƒ — inf ƒ. With the help of this tool, we derive an absolute lower bound for the minimal eigenvalues of Toeplitz matrices generated by nonnegative L¹ functions and also an upper bound for the associated Euclidean condition numbers. Finally, these results are extended to the case of Hermitian block Toeplitz matrices with Toeplitz blocks generated by a bivariate integrable function ƒ.     

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.     

块对偶Toeplitz算子的乘积

本文刻画了向量值Bergman空间上块对偶Toeplitz算子有界性和紧性,给出了块对偶Toeplitz算子的乘积是块对偶Toeplitz算子的充要条件.     

Conservative solution of the Fokker–Planck equation for stochastic chemical reactions

In this paper we discuss multigrid methods for ill-conditioned symmetric positive definite block Toeplitz matrices. Our block Toeplitz systems are general in the sense that the individual blocks are not necessarily Toeplitz, but we restrict our attention to blocks of small size. We investigate how transfer operators for prolongation and restriction have to be chosen such that our multigrid algorithms converge quickly. We point out why these transfer operators can be understood as block matrices as well and how they relate to the zeroes of the generating matrix function. We explain how our new algorithms can also be combined efficiently with the use of a natural coarse grid operator. We clearly identify a class of ill-conditioned block Toeplitz matrices for which our algorithmic ideas are suitable. In the final section we present an outlook to well-conditioned block Toeplitz systems and to problems of vector Laplace type. In the latter case the small size blocks can be interpreted as degrees of freedom associated with a node. A large number of numerical experiments throughout the article confirms convincingly that our multigrid solvers lead to optimal order convergence. AMS subject classification (2000) 65N55, 65F10     

On inversion of block Toeplitz matrices

In [1] we proved that each inverse of a Toeplitz matrix can be constructed via three of its columns, and thus, a parametrization of the set of inverses of Toeplitz matrices was obtained. A generalization of these results to block Toeplitz matrices is the main aim of this paper.     

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.     

Spectra of multilevel toeplitz matrices: Advanced theory via simple matrix relationships

We consider the eigenvalue and singular-value distributions for m-level Toeplitz matrices generated by a complex-valued periodic function ƒ of m real variables. We show that familiar formulations for ƒ L_∞ (due to Szegő and others) can be preserved so long as f L₁, and what is more, with G. Weyl's definitions just a bit changed. In contrast to other approaches, the one we follow is based on simple matrix relationships.     

Inversion of Toeplitz Matrices which are not Strongly Non-singular

A type of patterned matrix called r-Toeplitz is introduced.This is more general than a block Toeplitz matrix, which resultswhen the order n of the matrix is a multiple of r.A well-knownalgorithm for inverting Toeplitz matrices is extended to dealwith r-Toeplitz matrices, involving O(rn²) operations.This enablesan algorithm to be produced for inverting Toeplitz matriceswhich are not strongly non-singular, when the standard techniquesbreak down.     

A note on inversion of Toeplitz matrices

It is shown that the invertibility of a Toeplitz matrix can be determined through the solvability of two standard equations. The inverse matrix can be denoted as a sum of products of circulant matrices and upper triangular Toeplitz matrices. The stability of the inversion formula for a Toeplitz matrix is also considered.     

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.