The tensor t‐function: A definition for functions of third‐order tensors

A definition for functions of multidimensional arrays is presented. The definition is valid for third‐order tensors in the tensor t‐product formalism, which regards third‐order tensors as block circulant matrices. The tensor function definition is shown to have similar properties as standard matrix function definitions in fundamental scenarios. To demonstrate the definition's potential in applications, the notion of network communicability is generalized to third‐order tensors and computed for a small‐scale example via block Krylov subspace methods for matrix functions. A complexity analysis for these methods in the context of tensors is also provided.     

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.     

Smoothing Windows for the Synthesis of Gaussian Stationary Random Fields Using Circulant Matrix Embedding

When generating Gaussian stationary random fields, a standard method based on circulant matrix embedding usually fails because some of the associated eigenvalues are negative. The eigenvalues can be shown to be nonnegative in the limit of increasing sample size. Computationally feasible large sample sizes, however, rarely lead to nonnegative eigenvalues. Another solution is to extend suitably the covariance function of interest so that the eigenvalues of the embedded circulant matrix become nonnegative in theory. Though such extensions have been found for a number of examples of stationary fields, the method depends on nontrivial constructions in specific cases.

In this work, the embedded circulant matrix is smoothed at the boundary by using a cutoff window or overlapping windows over a transition region. The windows are not specific to particular examples of stationary fields. The resulting method modifies the standard circulant embedding, and is easy to use. It is shown that this straightforward approach works for many examples of interest, with the overlapping windows performing consistently better. The method even outperforms in the cases where extending the covariance leads to nonnegative eigenvalues in theory, in the sense that the transition region is considerably smaller. The Matlab code implementing the method is included in the online supplementary materials and also publicly available at www.hermir.org.     

Weight Enumerators of Double Circulant Codes and New Extremal Self-Dual Codes

In this paper it is shown that the weight enumerator of a bordered double circulant self-dual code can be obtained from those of a pure double circulant self-dual code and its shadow through a relationship between bordered and pure double circulant codes. As applications, a restriction on the weight enumerators of some extremal double circulant codes is determined and a uniqueness proof of extremal double circulant self-dual codes of length 46 is given. New extremal singly-even [44,22,8] double circulant codes are constructed. These codes have weight enumerators for which extremal codes were not previously known to exist.     

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.     

The forms of the relation between the stress and strain tensors in a non-linearly elastic material

New relations for the stress and strain tensors, which comprise energy pairs, are obtained for a non-linearly elastic material using a similar method to that employed by Novozhilov, based on a trigonometric representation of the tensors. Shear strain and stress tensors, not used previously, are introduced in a natural way. It is established that the unit tensor, the deviator and the shear tensor form an orthogonal tensor basis. The stress tensor can be expanded in a strain-tensor basis and vice versa. By using this expansion, the non-linear law of elasticity can be written in a compact and physically clear form. It is shown that in the frame of the principal axes the stresses are expressed in terms of the strains and vice versa using linear relations, while the non-linearity is contained in the coefficients, which are functions of mixed invariants of the tensors, introduced by Novozhilov, the generalized moduli of bulk compression and shear and the phase of similitude of the deviators. Relations for different energy pairs of tensors are considered, including for tensors of the true stresses and strains, where the generalized moduli of elasticity have a physical meaning for large strains.     

The best circulant preconditioners for Hermitian Toeplitz systems II: The multiple-zero case

Summary. In [10,14], circulant-type preconditioners have been proposed for ill-conditioned Hermitian Toeplitz systems that are generated by nonnegative continuous functions with a zero of even order. The proposed circulant preconditioners can be constructed without requiring explicit knowledge of the generating functions. It was shown that the spectra of the preconditioned matrices are uniformly bounded except for a fixed number of outliers and that all eigenvalues are uniformly bounded away from zero. Therefore the conjugate gradient method converges linearly when applied to solving the circulant preconditioned systems. In [10,14], it was claimed that this result can be the case where the generating functions have multiple zeros. The main aim of this paper is to give a complete convergence proof of the method in [10,14] for this class of generating functions. Received October 19, 1999 / Revised version received May 2, 2001 / Published online October 17, 2001     

Parallel algorithms for solving tridiagonal and near-circulant systems

Many problems in mathematics and applied science lead to the solution of linear systems having circulant coefficient matrices. This paper presents a new stable method for the exact solution of non-symmetric tridiagonal circulant linear systems of equations. The method presented in this paper is quite competitive with Gaussian elimination both in terms of arithmetic operations and storage requirements. It is also competitive with the modified double sweep method. This method can be applied to solve the near-circulant tridiagonal system. In addition, the method is modified to allow for parallel processing.     

循环矩阵及其在结构计算中的应用

本文推广了循环矩阵的概念,讨论了它的一般性质,并提出了一种解系数矩阵为循环矩阵或准循环矩阵的线性代数方程组(这种方程组在一大类常见的结构物的计算中出现)的方法,这种解法比通常解法计算量小而且节省存储,同时还允许应用快速富氏变换以增怏其计算速度。     

Circulant Double Coverings of a Circulant Graph of Valency Four

Several isomorphism classes of graph coverings of a graph G have been enumerated by many authors (see [3], [8]–[15]). A covering of G is called circulant if its covering graph is circulant. Recently, the authors [4] enumerated the isomorphism classes of circulant double coverings of a certain kind, called typical, and showed that no double covering of a circulant graph of valency 3 is circulant. In this paper, the isomorphism classes of connected circulant double coverings of a circulant graph of valency 4 are enumerated. As a consequence, it is shown that no double covering of a non-circulant graph G of valency 4 can be circulant if G is vertex-transitive or G has a prime power of vertices. The first author is supported by NSF of China (No. 60473019) and by NKBRPC (2004CB318000), and the second author is supported by Com²MaC-KOSEF (R11-1999-054) in Korea.     

On characterizing the set of possible effective tensors of composites: The variational method and the translation method

A general algebraic framework is developed for characterizing the set of possible effective tensors of composites. A transformation to the polarization-problem simplifies the derivation of the Hashin-Shtrikman variational principles and simplifies the calculation of the effective tensors of laminate materials. A general connection is established between two methods for bounding effective tensors of composites. The first method is based on the variational principles of Hashin and Shtrikman. The second method, due to Tartar, Murat, Lurie, and Cherkaev, uses translation operators or, equivalently, quadratic quasiconvex functions. A correspondence is established between these translation operators and bounding operators on the relevant non-local projection operator, T₁. An important class of bounds, namely trace bounds on the effective tensors of two-component media, are given a geometrical interpretation: after a suitable fractional linear transformation of the tensor space each bound corresponds to a tangent plane to the set of possible tensors. A wide class of translation operators that generate these bounds is found. The extremal translation operators in this class incorporate projections onto spaces of antisymmetric tensors. These extremal translations generate attainable trace bounds even when the tensors of the two-components are not well ordered. In particular, they generate the bounds of Walpole on the effective bulk modulus. The variational principles of Gibiansky and Cherkaev for bounding complex effective tensors are reviewed and used to derive some rigorous bounds that generalize the bounds conjectured by Golden and Papanicolaou. An isomorphism is shown to underlie their variational principles. This isomorphism is used to obtain Dirichlet-type variational principles and bounds for the effective tensors of general non-selfadjoint problems. It is anticipated that these variational principles, which stem from the work of Gibiansky and Cherkaev, will have applications in many fields of science.     

Inequalities for determinants and permanents

Let p be a prime > 3. It is shown that no integral circulant of order p^k exists with determinant p^k+1 . It is also shown that m is the determinant of an integral 9×9 circulant if and only if (m, 3)=l, or m = 0 mod 27. The proof makes use of a criterion which must be satisfied by the difference of two units in the cyclotomic field of level p^k .     

具有对称循环结构线性大系统的分散镇定特征

研究一类具有对称循环结构的连续和离散线性大系统的分散镇定特征,充分利用对称循环的特点,建立了判断这类系统可分散镇定的充分条件．在连续情形下,通过引进耦合结构模这一概念,揭示了这类系统分散镇定的重要特征,这就是当整个系统的耦合结构模给定之后,系统的分散镇定特性可以完全由各孤立子系统的结构所决定．这表明在这类系统的实际设计中,不管系统内中各子系统之间的耦合结构多么复杂,只要按一定的条件适当设计或修正各孤立子系统的结构参数,就能使所设计的大系统具有分散镇定特征,并提供了相应的分散镇定算法．对离散情形也进行了讨论,结果表明,连续系统与离散系统的分散镇定特征有着很大的差异．     

PRODUCTS OF CIRCULANT GRAPHS

ABSTRACT

Graph products of circulants are studied. It is shown that if G and H are circulants and gcd(v(G), v(H)) = 1, then every B-product of G and H is again a circulant. We prove that if m ≠ 2, then the generalised prism K₂ ^mxC_n is a circulant iff n is odd. A similar result is deduced for the conjunction. We also prove that C_p x C_q is a circulant iff p and q are relatively prime. We close by showing that the composition of two circulants is again a circulant and explicitly describe the resultant circulant's jump sequence in terms of the constituent circulants' jump sequences.     

Factorization strategies for third-order tensors

Operations with tensors, or multiway arrays, have become increasingly prevalent in recent years. Traditionally, tensors are represented or decomposed as a sum of rank-1 outer products using either the CANDECOMP/PARAFAC (CP) or the Tucker models, or some variation thereof. Such decompositions are motivated by specific applications where the goal is to find an approximate such representation for a given multiway array. The specifics of the approximate representation (such as how many terms to use in the sum, orthogonality constraints, etc.) depend on the application.In this paper, we explore an alternate representation of tensors which shows promise with respect to the tensor approximation problem. Reminiscent of matrix factorizations, we present a new factorization of a tensor as a product of tensors. To derive the new factorization, we define a closed multiplication operation between tensors. A major motivation for considering this new type of tensor multiplication is to devise new types of factorizations for tensors which can then be used in applications.Specifically, this new multiplication allows us to introduce concepts such as tensor transpose, inverse, and identity, which lead to the notion of an orthogonal tensor. The multiplication also gives rise to a linear operator, and the null space of the resulting operator is identified. We extend the concept of outer products of vectors to outer products of matrices. All derivations are presented for third-order tensors. However, they can be easily extended to the order-p(p>3) case. We conclude with an application in image deblurring.     

Double circulant matrices

Double circulant matrices are introduced and studied. By a matrix-theoretic method, the rank r of a double circulant matrix is computed, and it is shown that any consecutive r rows of the double circulant matrix are linearly independent. As a generalization, multiple circulant matrices are also introduced. Two questions on square double circulant matrices are posed.     

Limiting spectral distributions of some band matrices

We use the method of moments to establish the limiting spectral distribution (LSD) of appropriately scaled large dimensional random symmetric circulant, reverse circulant, Toeplitz and Hankel matrices which have suitable band structures. The input sequence used to construct these matrices is assumed to be either i.i.d. with mean zero and variance one or independent and appropriate finite fourth moment. The class of LSD includes the normal and the symmetrized square root of chi-square with two degrees of freedom. In several other cases, explicit forms of the limit do not seem to be obtainable but the limits can be shown to be symmetric and their second and the fourth moments can be calculated with some effort. Simulations suggest some further properties of the limits.     

Lower Branch Modes of the Compressible Boundary Layer Flow Due to a Rotating-Disk

In this article, a theoretical study is pursued to investigate the structure of the lower branch neutral stability modes of three-dimensional small disturbances imposed on the compressible boundary layer flow due to a rotating-disk. Special attention is focused on to the short-wavelength stationary/nonstationary compressible crossflow vortex modes at sufficiently high Reynolds numbers with reasonably small scaled frequencies. Following closely the asymptotic framework introduced in [ 1 ] for the incompressible stationary modes, it is demonstrated here that the compressible modes having sufficiently long time scale can also be described by an asymptotic expansion procedure based on the triple-deck approach. Making use of this rational asymptotic technique, which rigorously takes into account the nonparallel effects, the asymptotic structure of the nonstationary modes is shown to be adjusted by a balance between viscous and Coriolis forces, and resulted from the fact of vanishing shear stress at the disk surface, as in the incompressible Von Karman's flow. As a consequence of matching successive regions in the asymptotic procedure, it is found that the wavenumber and the orientation of the compressible lower branch modes are governed by an eigenrelation, which is akin to the one obtained previously in [ 1 ] for the incompressible stationary mode and in [ 2 ] for the compressible stationary modes. The nonparallel influences are toward destabilizing all the modes, though the wall insulation and heating are relatively stabilizing for the modes in the vicinity of the stationary mode, unlike the wall cooling. The asymptotic compressible data obtained at high Reynolds number limit compares fairly well with the numerical results generated directly solving the linearized compressible system with usual parallel flow approximation.     

Multisymplectic Relative Equilibria, Multiphase Wavetrains, and Coupled NLS Equations

The article begins with a geometric formulation of two-phase wavetrain solutions of coupled nonlinear Schrödinger equations. It is shown that these solutions come in natural four-parameter families, associated with symmetry, and a geometric instability condition can be deduced from the parameter structure that generalizes Roskes' instability criterion. It is then shown that this geometric structure is universal in the sense that it does not depend on the particular equation, only on the structure of the equations. The theory also extends to the case without symmetry, where small divisors may be present, but gives a new formal geometric framework for multiphase wavetrains.