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.     

Lusternik‐Schnirelmann category and systolic category of low‐dimensional manifolds

We show that the geometry of a Riemannian manifold (M, ??) is sensitive to the apparently purely homotopy‐theoretic invariant of M known as the Lusternik‐Schnirelmann category, denoted cat_LS(M). Here we introduce a Riemannian analogue of cat_LS(M), called the systolic category of M. It is denoted cat_sys(M) and defined in terms of the existence of systolic inequalities satisfied by every metric ??, as initiated by C. Loewner and later developed by M. Gromov. We compare the two categories. In all our examples, the inequality cat_sysM ≤ cat_LSM is satisfied, which typically turns out to be an equality, e.g., in dimension 3. We show that a number of existing systolic inequalities can be reinterpreted as special cases of such equality and that both categories are sensitive to Massey products. The comparison with the value of cat_LS(M) leads us to prove or conjecture new systolic inequalities on M. © 2006 Wiley Periodicals, Inc.     

Defining Sets and Critical Sets in (0,1)‐Matrices

If D is a partially filled‐in (0, 1)‐matrix with a unique completion to a (0, 1)‐matrix M (with prescribed row and column sums), we say that D is a defining set for M. If the removal of any entry of D destroys this property (i.e. at least two completions become possible), we say that D is a critical set for M. In this note, we show that the complement of a critical set for a (0, 1)‐matrix M is a defining set for M. We also study the possible sizes (number of filled‐in cells) of defining sets for square matrices M with uniform row and column sums, which are also frequency squares. In particular, we show that when the matrix is of even order 2m and the row and column sums are all equal to m, the smallest possible size of a critical set is precisely m². We give the exact structure of critical sets with this property. © 2012 Wiley Periodicals, Inc. J. Combin. Designs 21: 253–266, 2013     

Non-induced isomorphisms of matrix rings

We give examples of distinct integersi, j, and ringsT for which the matrix ringsM _i (T) andM _j (T) are isomorphic as rings, but for which the free modules _T T ⁽ⁱ⁾ and _T T ⁽ⁱ⁾ are non-isomorphic asT-modules.     

Rings with Zassenhaus Families of Ideals

Let R be a ring with identity. We call a family ? of left ideals of R a Zassenhaus family if the only additive endomorphisms of R that leave all members of ? invariant are the left multiplications by elements of R. Moreover, if R is torsion-free and there is some left R-module M such that R ? M ? R?_?? and End _?(M) = R we call R a “Zassenhaus ring”. It is well known that all Zassenhaus rings have Zassenhaus families. We will give examples to show that the converse does not hold even for torsion-free rings of finite rank.     

Lanczos,Householder transformations,and implicit deflation for fast and reliable dominant singular subspace computation

Many applications, such as subspace‐based models in information retrieval and signal processing, require the computation of singular subspaces associated with the k dominant, or largest, singular values of an m×n data matrix A, where k?min(m,n). Frequently, A is sparse or structured, which usually means matrix–vector multiplications involving A and its transpose can be done with much less than ??(mn) flops, and A and its transpose can be stored with much less than ??(mn) storage locations. Many Lanczos‐based algorithms have been proposed through the years because the underlying Lanczos method only accesses A and its transpose through matrix–vector multiplications. We implement a new algorithm, called KSVD, in the Matlab environment for computing approximations to the singular subspaces associated with the k dominant singular values of a real or complex matrix A. KSVD is based upon the Lanczos tridiagonalization method, the WY representation for storing products of Householder transformations, implicit deflation, and the QR factorization. Our Matlab simulations suggest it is a fast and reliable strategy for handling troublesome singular‐value spectra. Copyright © 2001 John Wiley & Sons, Ltd.     

Properties of Hadamard product of inverse M‐matrices

This paper concerns with the properties of Hadamard product of inverse M‐matrices. Structures of tridiagonal inverse M‐matrices and Hessenberg inverse M‐matrices are analysed. It is proved that the product A ○ A^T satisfies Willoughby's necessary conditions for being an inverse M‐matrix when A is an irreducible inverse M‐matrix. It is also proved that when A is either a Hessenberg inverse M‐matrix or a tridiagonal inverse M‐matrix then A ○ A^T is an inverse M‐matrix. Based on these results, the conjecture that A ○ A^T is an inverse M‐matrix when A is an inverse M‐matrix is made. Unfortunately, the conjecture is not true. Copyright © 2004 John Wiley Sons, Ltd.     

Circulant weighing matrices of weight 22t

A weighing matrix of weight k is a square matrix M with entries 0, ± 1 such that MM ^T = kI _n . We study the case that M is a circulant and k = 2^2t for some positive integer t. New structural results are obtained. Based on these results, we make a complete computer search for all circulant weighing matrices of order 16.      

Toeplitz operators on the Fock space: Radial component effects

The paper is devoted to the study of specific properties of Toeplitz operators with (unbounded, in general) radial symbolsa=a(r). Boundedness and compactness conditions, as well as examples, are given. It turns out that there exist non-zero symbols which generate zero Toeplitz operators. We characterize such symbols, as well as the class of symbols for whichT _a =0 impliesa(r)=0 a.e. For each compact setM there exists a Toeplitz operatorT _a such that spT _a =ess-spT _a =M. We show that the set of symbols which generate bounded Toeplitz operators no longer forms an algebra under pointwise multiplication.Besides the algebra of Toeplitz operators we consider the algebra of Weyl pseudodifferential operators obtained from Toeplitz ones by means of the Bargmann transform. Rewriting our Toeplitz and Weyl pseudodifferential operators in terms of the Wick symbols we come to their spectral decompositions.This work was partially supported by CONACYT Project 27934-E, México.The first author acknowledges the RFFI Grant 98-01-01023, Russia.     

Primitive non-powerful sign pattern matrices with base 2

A sign pattern matrix M with zero trace is primitive non-powerful if for some positive integer k, M ^k ?=?J _#. The base l(M) of the primitive non-powerful matrix M is the smallest integer k. By considering the signed digraph S whose adjacent matrix is the primitive non-powerful matrix M, we will show that if l(M)?=?2, the minimum number of non-zero entries of M is 5n???8 or 5n???7 depending on whether n is even or odd.     

Sine transform based preconditioners for elliptic problems

We consider applying the preconditioned conjugate gradient (PCG) method to solving linear systems Ax = b where the matrix A comes from the discretization of second-order elliptic operators with Dirichlet boundary conditions. Let (L + Σ)Σ⁻¹(L^t + Σ) denote the block Cholesky factorization of A with lower block triangular matrix L and diagonal block matrix Σ. We propose a preconditioner M = (Lˆ + Σˆ)Σˆ⁻¹(Lˆ^t + Σˆ) with block diagonal matrix Σˆ and lower block triangular matrix Lˆ. The diagonal blocks of Σˆ and the subdiagonal blocks of Lˆ are respectively the optimal sine transform approximations to the diagonal blocks of Σ and the subdiagonal blocks of L. We show that for two-dimensional domains, the construction cost of M and the cost for each iteration of the PCG algorithm are of order O(n² log n). Furthermore, for rectangular regions, we show that the condition number of the preconditioned system M⁻¹A is of order O(1). In contrast, the system preconditioned by the MILU and MINV methods are of order O(n). We will also show that M can be obtained from A by taking the optimal sine transform approximations of each sub-block of A. Thus, the construction of M is similar to that of Level-1 circulant preconditioners. Our numerical results on two-dimensional square and L-shaped domains show that our method converges faster than the MILU and MINV methods. Extension to higher-dimensional domains will also be discussed. © 1997 John Wiley & Sons, Ltd.     

Variational Formula for the Time Constant of First‐Passage Percolation

We consider first‐passage percolation with positive, stationary‐ergodic weights on the square lattice ?^d. Let T(x) be the first‐passage time from the origin to a point x in ?^d. The convergence of the scaled first‐passage time T([nx])/n to the time constant as n → ∞ can be viewed as a problem of homogenization for a discrete Hamilton‐Jacobi‐Bellman (HJB) equation. We derive an exact variational formula for the time constant and construct an explicit iteration that produces a minimizer of the variational formula (under a symmetry assumption). We explicitly identify when the iteration produces correctors.© 2016 Wiley Periodicals, Inc.     

On the evaluation at (−ι,ι) of the Tutte polynomial of a binary matroid

Vertigan has shown that if M is a binary matroid, then |T _M (?ι,ι)|, the modulus of the Tutte polynomial of M as evaluated in (?ι,ι), can be expressed in terms of the bicycle dimension of M. In this paper, we describe how the argument of the complex number T _M (?ι,ι) depends on a certain $\mathbb{Z}/4\mathbb {Z}$ -valued quadratic form that is canonically associated with M. We show how to evaluate T _M (?ι,ι) in polynomial time, as well as the canonical tripartition of M and further related invariants.     

Finite groups with some given systems of Xm‐semipermutable subgroups

Let X be a nonempty subset of a group G. We call a subgroup A of G an X_m‐semipermutable subgroup of G if A has a minimal supplement T in G such that for every maximal subgroup M of any Hall subgroup T₁ of T there exists an element x ∈ X such that AM^x = M^xA. In this paper, we study the structure of finite groups with some given systems of X_m‐semipermutable subgroups (© 2010 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Unitary dilations and theC* algebra0 2

LetH be an infinite-dimensional separable Hilbert space, and letS=(S _ij)∈teB(H)⊗M ₂ be a unitary 2 × 2 matrix with operator entries. We study theC*-algebra generated by the operatorsS _ij, and show that the study of unitary dilations of isometriesT inH reduces to the special case whereS ₁₁ =T, andS ₂₁ = 0. We useC*-algebraic techniques to obtain detailed results about the set of all unitary dilations ofT. Work supported in part by NSF.     

An effective algorithm for the cohomology ring of symplectic reductions

Let G be a compact torus acting on a compact symplectic manifold M in a Hamiltonian fashion, and T a subtorus of G. We prove that the kernel of is generated by a small number of classes satisfying very explicit restriction properties. Our main tool is the equivariant Kirwan map, a natural map from the G-equivariant cohomology of M to the G/T-equivariant cohomology of the symplectic reduction of M by T . We show this map is surjective. This is an equivariant version of the well-known result that the (nonequivariant) Kirwan map is surjective. We also compute the kernel of the equivariant Kirwan map, generalizing the result due to Tolman and Weitsman [TW] in the case T = G and allowing us to apply their methods inductively. This result is new even in the case that dim T = 1. We close with a worked example: the cohomology ring of the product of two , quotiented by the diagonal 2-torus action. Submitted: September 2001, Revised: December 2001, Revised: February 2002.     

Combinatorial interpretations for TG(1, −1)

Let G be a connected and simple graph with vertex set {1, 2, …, n + 1} and T_G(x, y) the Tutte polynomial of G. In this paper, we give combinatorial interpretations for T_G(1, ?1). In particular, we give the definitions of even spanning tree and left spanning tree. We prove T_G(1, ?1) is the number of even‐left spanning trees of G. We associate a permutation with a spanning forest of G and give the definition of odd G‐permutations. We show T_G(1, ?1) is the number of odd G‐permutations. We give a bijection from the set of odd K_{n + 1}‐permutations to the set of alternating permutations on the set {1, 2, …, n}. Copyright © 2011 Wiley Periodicals, Inc. J Graph Theory 69: 341–348, 2012     

ON THE STRUCTURE OF THEATTRACTORS OF HYPERBOLICITERATED FUNCTION SYSTEM

1.IntroductionThefractalsgeneratedbytheattractorsofiteratedfunctionsystems(i.f.s.)havebeenresearchedbymanyauthorsfl--3'6'7'9].ByaniteratedfunctionsystemwemeanacompactmetricspaceXtogetherwithacollectionofcontinuousmapsTI,T2,'tTNonit,denotedby(X,TI,',TN).IfalltheTi'sarecontractionswecall(X;TI,',TN)ahyperboliciteratedfunctionsystem(h.i.f.s.).NForanh.i.f.s.thereexistsacompactsubsetAofX,suchthatA=.UTi(A).Aiscalledtheattractoroftheh.i.f.s.DenoteZ=(1,2,',N)N,anddefineametricdonZby…     

Preconditioners for block Toeplitz systems based on circulant preconditioners

We study the numerical solution of a block system T _m,n x=b by preconditioned conjugate gradient methods where T _m,n is an m×m block Toeplitz matrix with n×n Toeplitz blocks. These systems occur in a variety of applications, such as two-dimensional image processing and the discretization of two-dimensional partial differential equations. In this paper, we propose new preconditioners for block systems based on circulant preconditioners. From level-1 circulant preconditioner we construct our first preconditioner q ₁(T _m,n ) which is the sum of a block Toeplitz matrix with Toeplitz blocks and a sparse matrix with Toeplitz blocks. By setting selected entries of the inverse of level-2 circulant preconditioner to zero, we get our preconditioner q ₂(T _m,n ) which is a (band) block Toeplitz matrix with (band) Toeplitz blocks. Numerical results show that our preconditioners are more efficient than circulant preconditioners.     

Spectral flexibility of symplectic manifolds <Emphasis Type="Italic">T</Emphasis><Superscript>2</Superscript> × <Emphasis Type="Italic">M</Emphasis>

We consider Riemannian metrics compatible with the natural symplectic structure on T ² × M, where T ² is a symplectic 2-torus and M is a closed symplectic manifold. To each such metric we attach the corresponding Laplacian and consider its first positive eigenvalue λ₁. We show that λ₁ can be made arbitrarily large by deforming the metric structure, keeping the symplectic structure fixed. The conjecture is that the same is true for any symplectic manifold of dimension ≥ 4. We reduce the general conjecture to a purely symplectic question.