Convolution theorems associated with some integral operators and convolutions

In this article, various convolution theorems involving certain weight functions and convolution products are derived. The convolution theorems we obtain are more general, convenient, and efficient than the complicated convolution theorem of the Hartley transform. Further results involving new variants of generalizations of Fourier and Hartley transforms are also discussed.     

结构矩阵的三角表示及其应用

利用位移铁和交换Hessenberg矩阵代数给出结构矩阵的三角表示,并讨论在Toeplitz矩阵和Toeplitz Hankel矩阵方面的应用。     

ON BLOCK MATRICES ASSOCIATED WITH DISCRETE TRIGONOMETRIC TRANSFORMS AND THEIR USE IN THE THEORY OF WAVE PROPAGATION

Block matrices associated with discrete Trigonometric transforms （DTT＇s） arise in the mathematical modelling of several applications of wave propagation theory including discretizations of scatterers and radiators with the Method of Moments, the Boundary Element Method, and the Method of Auxiliary Sources. The DTT＇s are represented by the Fourier, Hartley, Cosine, and Sine matrices, which are unitary and offer simultaneous diagonalizations of specific matrix algebras. The main tool for the investigation of the aforementioned wave applications is the efficient inversion of such types of block matrices. To this direction, in this paper we develop an efficient algorithm for the inversion of matrices with U-diagonalizable blocks （U a fixed unitary matrix） by utilizing the U- diagonalization of each block and subsequently a similarity transformation procedure. We determine the developed method＇s computational complexity and point out its high efficiency compared to standard inversion techniques. An implementation of the algorithm in Matlab is given. Several numerical results are presented demonstrating the CPU-time efficiency and accuracy for ill-conditioned matrices of the method. The investigated matrices stem from real-world wave propagation applications.     

Kernel structure of Toeplitz-plus-Hankel matrices

The structure of the kernel of block Toeplitz-plus-Hankel matrices R=[a_j−k+b_j+k], where a_j and b_j are the given p×q blocks with entries from a given field, is investigated. It is shown that R corresponds to two systems of at most p+q vector polynomials from which a basis of the kernel of R and all other Toeplitz-plus-Hankel matrices with the same parameters a_j and b_j can be built. The main result is an analogue of a known kernel structure theorem for block Toeplitz and block Hankel matrices.     

On the skew-symmetric part of the Toeplitz component in the real normal (<Emphasis Type="Italic">T</Emphasis> + <Emphasis Type="Italic">H</Emphasis>)-problem

The real normal Toeplitz-plus-Hankel problem is to characterize the matrices that can be represented as sums of two real matrices of which one is Toeplitz and the other Hankel. For a matrix of this type, relations are found between the skew-symmetric part of the Toeplitz component and the matrix obtained by reversing the order of columns in the Hankel component.     

Difference operators,Green's matrix,sampling theory and applications in signal processing

This paper introduces sampling representations for discrete signals arising from self adjoint difference operators with mixed boundary conditions. The theory of linear operators on finite-dimensional inner product spaces is employed to study the second-order difference operators. We give necessary and sufficient conditions that make the operators self adjoint. The equivalence between the difference operator and a Hermitian Green's matrix is established. Sampling theorems are derived for discrete transforms associated with the difference operator. The results are exhibited via illustrative examples, involving sampling representations for the discrete Hartley transform. Families of discrete fractional Fourier-type transforms are introduced with an application to image encryption.     

Supercharacters and the discrete Fourier,cosine, and sine transforms

Using supercharacter theory, we identify the matrices that are diagonalized by the discrete cosine and discrete sine transforms, respectively. Our method affords a combinatorial interpretation for the matrix entries.     

Matrix representations of split Bezoutians

Inverses of symmetric (or skewsymmetric) Toeplitz matrices as well as of centrosymmetric (or centro-skewsymmetric) Toeplitz-plus-Hankel matrices can be represented as sums of two split Bezoutians which are highly structured matrices since all of their rows and columns are symmetric or skewsymmetric vectors. Thus it is desirable to find matrix representations for split Bezoutians B. This is the main aim of the present paper.Recursion formulas for the entries of B are presented, bases of very simple split Bezoutians or of sparse matrices are constructed, and B is represented as a corresponding linear combination. Moreover, matrix representations of Gohberg/Semencul type are established.     

Fast transforms for tridiagonal linear equations

In this paper we study the use of the Fourier, Sine and Cosine Transform for solving or preconditioning linear systems, which arise from the discretization of elliptic problems. Recently, R. Chan and T. Chan considered circulant matrices for solving such systems. Instead of using circulant matrices, which are based on the Fourier Transform, we apply the Fourier and the Sine Transform directly. It is shown that tridiagonal matrices arising from the discretization of an onedimensional elliptic PDE are connected with circulant matrices by congruence transformations with the Fourier or the Sine matrix. Therefore, we can solve such linear systems directly, using only Fast Fourier Transforms and the Sherman-Morrison-Woodbury formula. The Fast Fourier Transform is highly parallelizable, and thus such an algorithm is interesting on a parallel computer. Moreover, similar relations hold between block tridiagonal matrices and Block Toeplitz-plus-Hankel matrices of ordern ²×n ² in the 2D case. This can be used to define in some sense natural approximations to the given matrix which lead to preconditioners for solving such linear systems.     

Shift products and factorizations of wavelet matrices

A class of so-called shift products of wavelet matrices is introduced. These products are based on circulations of columns of orthogonal banded block circulant matrices arising in applications of discrete orthogonal wavelet transforms (or paraunitary multirate filter banks) or, equivalently, on augmentations of wavelet matrices by zero columns (shifts). A special case is no shift; a product which is closely related to the Pollen product is then obtained. Known decompositions using factors formed by two blocks are described and additional conditions such that uniqueness of the factorization is guaranteed are given. Next it is shown that when nonzero shifts are used, an arbitrary wavelet matrix can be factorized into a sequence of shift products of square orthogonal matrices. Such a factorization, as well as those mentioned earlier, can be used for the parameterization and construction of wavelet matrices, including the costruction from the first row. Moreover, it is also suitable for efficient implementations of discrete orthogonal wavelet transforms and paraunitary filter banks.and Cooperative Research Centre for Sensor Signal and Information ProcessingThis author is an Overseas Postgraduate Research Scholar supported by the Australian Government.     

Roundoff error analysis of fast DCT algorithms in fixed point arithmetic

Discrete cosine transforms (DCT) are essential tools in numerical analysis and digital signal processing. Processors in digital signal processing often use fixed point arithmetic. In this paper, we consider the numerical stability of fast DCT algorithms in fixed point arithmetic. The fast DCT algorithms are based on known factorizations of the corresponding cosine matrices into products of sparse, orthogonal matrices of simple structure. These algorithms are completely recursive, are easy to implement and use only permutations, scaling, butterfly operations, and plane rotations/rotation-reflections. In comparison with other fast DCT algorithms, these algorithms have low arithmetic costs. Using von Neumann–Goldstine’s model of fixed point arithmetic, we present a detailed roundoff error analysis for fast DCT algorithms in fixed point arithmetic. Numerical tests demonstrate the performance of our results.      

Fast Algorithms for Centro-Symmetric and Centro-Skewsymmetric Toeplitz-Plus-Hankel Matrices

Subject of the paper are centro-symmetric and centro-skewsymmetric Toeplitz-plus-Hankel matrices with the property that all central submatrices are nonsingular. Fast algorithms are presented that solve an n×n system of equations with O(n ²) operations in sequential and O(n) operations in parallel processing and compute the ZW-factorization with the same computational complexity. These algorithms are more efficient than existing algorithms because they fully exploit the symmetry properties of the matrices.     

A criterion for a two-sided integral transform to be unitary

A criterion for a two-sided Watson transform to be unitary in the space L₂(R) is considered. It enables us to construct new examples of integral transforms with symmetric inversion formulas (only the Fourier and the Hartley transforms are known). We give some new examples of the indicated transforms, in particular, the symmetric Hankel transform with the sum of two Bessel functions in the kernal and the Hardy transform with the sum of a Neumann function and a Struve function in the kernel, and the Narain transform with a sum of two G-functions in the kernelDoctor of Physicomathematical sciences.Candidate of Physicomathematical sciences.Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 44, No. 5, pp. 697–699, May, 1992.     

A discrete Hartley transform based on Simpson's rule

The Hartley transform is an integral transformation that maps a real valued function into a real valued frequency function via the Hartley kernel, thereby avoiding complex arithmetic as opposed to the Fourier transform. Approximation of the Hartley integral by the trapezoidal quadrature results in the discrete Hartley transform, which has proven a contender to the discrete Fourier transform because of its involutory nature. In this paper, a discrete transform is proposed as a real transform with a convolution property and is an alternative to the discrete Hartley transform. Copyright © 2015 John Wiley & Sons, Ltd.     

Fast Wavelet Transform for Toeplitz Matrices and Property Analysis

Fast wavelet transform algorithms for Toeplitz matrices are proposed in this paper. Distinctive from the well known discrete trigonometric transforms, such as the discrete cosine transform （DCT） and the discrete Fourier transform （DFT） for Toeplitz matrices, the new algorithms are achieved by compactly supported wavelet that preserve the character of a Toeplitz matrix after transform, which is quite useful in many applications involving a Toeplitz matrix. Results of numerical experiments show that the proposed method has good compression performance similar to using wavelet in the digital image coding. Since the proposed algorithms turn a dense Toeplitz matrix into a band-limited form, the arithmetic operations required by the new algorithms are O（N） that are reduced greatly compared with O（N log N） by the classical trigonometric transforms.     

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.     

基于Hartley变换的三维真振幅偏移算子研究

在实际应用中，以快速Fourier变换为基础的偏移方法，将本来是实数的地震道转化为复数参加运算，导致了计算机内存的增加。本文把只有纯实数运算的Hartley变换引入到基于Fourier变换的偏移算法，再利用三维真振幅偏移单程波方程，结合Fourier变换与Hartley变换的内在关系，经过数学推理，具体导出了裂步Hartley变换真振幅偏移算子。与一般裂步Fourier法相比，裂步Hartley变换真振幅偏移算法既提高了计算效率又对球面扩散问题进行了振幅补偿。     

Numerical stability of biorthogonal wavelet transforms

Biorthogonal wavelets are essential tools for numerous practical applications. It is very important that wavelet transforms work numerically stable in floating point arithmetic. This paper presents new results on the worst-case analysis of roundoff errors occurring in floating point computation of periodic biorthogonal wavelet transforms, i.e. multilevel wavelet decompositions and reconstructions. Both of these wavelet algorithms can be realized by matrix–vector products with sparse structured matrices. It is shown that under certain conditions the wavelet algorithms can be remarkably stable. Numerous tests demonstrate the performance of the results.      

Cayley transform and the Kronecker product of Hermitian matrices

We consider the conditions under which the Cayley transform of the Kronecker product of two Hermitian matrices can be again presented as a Kronecker product of two matrices and, if so, if it is a product of the Cayley transforms of the two Hermitian matrices. We also study the related question: given two matrices, which matrix under the Cayley transform yields the Kronecker product of their Cayley transforms.     

Cosine transforms over fields of characteristic 2

In this paper, we introduce cosine transforms over fields of characteristic 2. Our approach complements previous definitions of finite field trigonometric transforms, which only hold for fields whose characteristic is an odd prime. Besides introducing some new concepts related to trigonometry in finite fields, we discuss the eigenstructure and other important properties of the proposed transforms.