BTTB preconditioners for BTTB systems

In this paper, we consider solving the BTTB system \({\cal T}_{m,n}[f] {\bf{x}} = {\bf{b}}\) by the preconditioned conjugate gradient (PCG) method, where \({\cal T}_{m,n}[f]\) denotes the m × m block Toeplitz matrix with n × n Toeplitz blocks (BTTB) generated by a (2π, 2π)-periodic continuous function f(x, y). We propose using the BTTB matrix \({\cal T}_{m,n}[1/f]\) to precondition the BTTB system and prove that only O(m)?+?O(n) eigenvalues of the preconditioned matrix \({\cal T}_{m,n}[1/f] {\cal T}_{m,n}[f]\) are not around 1 under the condition that f(x, y)?>?0. We then approximate 1/f(x, y) by a bivariate trigonometric polynomial, which can be obtained in O(m n log(m n)) operations by using the fast Fourier transform technique. Numerical results show that our BTTB preconditioner is more efficient than block circulant preconditioners.     

An Optimal Algorithm for the <Emphasis Type="Italic">k</Emphasis>-Fixed-Endpoint Path Cover on Proper Interval Graphs

In this paper we consider the k-fixed-endpoint path cover problem on proper interval graphs, which is a generalization of the path cover problem. Given a graph G and a set T of k vertices, a k-fixed-endpoint path cover of G with respect to T is a set of vertex-disjoint simple paths that covers the vertices of G, such that the vertices of T are all endpoints of these paths. The goal is to compute a k-fixed-endpoint path cover of G with minimum cardinality. We propose an optimal algorithm for this problem with runtime O(n), where n is the number of intervals in G. This algorithm is based on the Stair Normal Interval Representation (SNIR) matrix that characterizes proper interval graphs. In this characterization, every maximal clique of the graph is represented by one matrix element; the proposed algorithm uses this structural property, in order to determine directly the paths in an optimal solution.     

Separately radial and radial Toeplitz operators on the projective space and representation theory

We consider separately radial (with corresponding group T ⁿ ) and radial (with corresponding group U(n)) symbols on the projective space P ⁿ (C), as well as the associated Toeplitz operators on the weighted Bergman spaces. It is known that the C*-algebras generated by each family of such Toeplitz operators are commutative (see R. Quiroga-Barranco and A. Sanchez-Nungaray (2011)). We present a new representation theoretic proof of such commutativity. Our method is easier and more enlightening as it shows that the commutativity of the C*-algebras is a consequence of the existence of multiplicity-free representations. Furthermore, our method shows how to extend the current formulas for the spectra of the corresponding Toeplitz operators to any closed group lying between T ⁿ and U(n).     

A tournament approach to pattern avoiding matrices

We consider the following Turán-type problem: given a fixed tournament H, what is the least integer t = t(n,H) so that adding t edges to any n-vertex tournament, results in a digraph containing a copy of H. Similarly, what is the least integer t = t(T _n ,H) so that adding t edges to the n-vertex transitive tournament, results in a digraph containing a copy of H. Besides proving several results on these problems, our main contributions are the following:

• Pach and Tardos conjectured that if M is an acyclic 0/1 matrix, then any n × n matrix with n(log n) ^O(1) entries equal to 1 contains the pattern M. We show that this conjecture is equivalent to the assertion that t(T _n ,H) = n(log n) ^O(1) if and only if H belongs to a certain (natural) family of tournaments.
• We propose an approach for determining if t(n,H) = n(log n) ^O(1). This approach combines expansion in sparse graphs, together with certain structural characterizations of H-free tournaments. Our result opens the door for using structural graph theoretic tools in order to settle the Pach–Tardos conjecture.

     

Classifying anti-commuting pairs of Toeplitz and Hankel matrices

Conditions for commuting a Toeplitz matrix and a Hankel matrix were obtained relatively recently (in 2015). The solution to the problem of describing all anti-commuting pairs (T, H), where T is a Toeplitz matrix and H is a Hankel matrix, is sketched below.     

Modification of Rissanen’s Method in Linear Memory

The problem of solving a linear system with a Hankel or block-Hankel matrix, as well as Rissanen’s algorithm and its generalization to the block case, are considered. Modifications of these algorithms that use less memory (O(n) against O(n²)).     

On Lebesgue Measure of Integral Self-Affine Sets

Let A be an expanding integer n×n matrix and D be a finite subset of ? ⁿ . The self-affine set T=T(A,D) is the unique compact set satisfying the equality \(A(T)=\bigcup_{d\in D}(T+d)\). We present an effective algorithm to compute the Lebesgue measure of the self-affine set T, the measure of the intersection T∩(T+u) for u∈? ⁿ , and the measure of the intersection of self-affine sets T(A,D ₁)∩T(A,D ₂) for different sets D ₁, D ₂?? ⁿ .     

Conjugacy classes in Möbius groups

Let \({\mathbb H^{n+1}}\) denote the n + 1-dimensional (real) hyperbolic space. Let \({\mathbb {S}^{n}}\) denote the conformal boundary of the hyperbolic space. The group of conformal diffeomorphisms of \({\mathbb {S}^{n}}\) is denoted by M(n). Let M _o (n) be its identity component which consists of all orientation-preserving elements in M(n). The conjugacy classification of isometries in M _o (n) depends on the conjugacy of T and T ^?1 in M _o (n). For an element T in M(n), T and T ^?1 are conjugate in M(n), but they may not be conjugate in M _o (n). In the literature, T is called real if T is conjugate in M _o (n) to T ^?1. In this paper we classify real elements in M _o (n). Let T be an element in M _o (n). Corresponding to T there is an associated element T _o in SO(n + 1). If the complex conjugate eigenvalues of T _o are given by \({\{e^{i\theta_j}, e^{-i\theta_j}\}, 0 < \theta_j \leq \pi, j=1,\ldots,k}\) , then {θ₁, . . . , θ _k } are called the rotation angles of T. If the rotation angles of T are distinct from each-other, then T is called a regular element. After classifying the real elements in M _o (n) we have parametrized the conjugacy classes of regular elements in M _o (n). In the parametrization, when T is not conjugate to T ^?1 , we have enlarged the group and have considered the conjugacy class of T in M(n). We prove that each such conjugacy class can be induced with a fibration structure.     

On likelihood ratio ordering of parallel systems with exponential components

Let T(λ₁,...,λ _n ) be the lifetime of a parallel system consisting of exponential components with hazard rates λ₁,...,λ _n , respectively. For systems with only two components, Dykstra et. al. (1997) showed that if (λ₁, λ₂) majorizes (γ₁, γ₂), then, T(λ₁, λ₂) is larger than T(γ₁, γ₂) in likelihood ratio order. In this paper, we extend this theorem to general parallel systems. We introduce a new partial order, the so-called d-larger order, and show that if (λ₁,...,λ _n ) is d-larger than (γ₁,...,γ _n ), then T(λ₁,...,λ _n ) is larger than T(γ₁,...,γ _n ) in likelihood ratio order.     

Linear information for approximation of the Itô integrals

We study optimal approximation of stochastic integrals in the Itô sense when linear information, consisting of certain integrals of trajectories of Brownian motion, is available. Upper bounds on the nth minimal error, where n is the fixed cardinality of information, are obtained by the Wagner–Platen algorithm and are O(n ^???3/2) or O(n ^???2), depending on considered class of integrands. We also show that Ω(n ^???2) is a lower bound which holds even for very smooth integrands.     

Numerical solution to generalized Lyapunov/Stein and rational Riccati equations in stochastic control

We consider the numerical solution of the generalized Lyapunov and Stein equations in \(\mathbb {R}^{n}\), arising respectively from stochastic optimal control in continuous- and discrete-time. Generalizing the Smith method, our algorithms converge quadratically and have an O(n³) computational complexity per iteration and an O(n²) memory requirement. For large-scale problems, when the relevant matrix operators are “sparse”, our algorithm for generalized Stein (or Lyapunov) equations may achieve the complexity and memory requirement of O(n) (or similar to that of the solution of the linear systems associated with the sparse matrix operators). These efficient algorithms can be applied to Newton’s method for the solution of the rational Riccati equations. This contrasts favourably with the naive Newton algorithms of O(n⁶) complexity or the slower modified Newton’s methods of O(n³) complexity. The convergence and error analysis will be considered and numerical examples provided.     

Linear preservers of row-dense matrices

Let M_m,n be the set of all m × n real matrices. A matrix A ∈ M_m,n is said to be row-dense if there are no zeros between two nonzero entries for every row of this matrix. We find the structure of linear functions T: M_m,n → M_m,n that preserve or strongly preserve row-dense matrices, i.e., T(A) is row-dense whenever A is row-dense or T(A) is row-dense if and only if A is row-dense, respectively. Similarly, a matrix A ∈ M_n,m is called a column-dense matrix if every column of A is a column-dense vector. At the end, the structure of linear preservers (strong linear preservers) of column-dense matrices is found.     

Lower bounds for polynomials of many variables

A polynomial P(ξ) = P(ξ₁,..., ξ _n ) is said to be almost hypoelliptic if all its derivatives D ^ν P(ξ) can be estimated from above by P(ξ) (see [16]). By a theorem of Seidenberg-Tarski it follows that for each polynomial P(ξ) satisfying the condition P(ξ) > 0 for all ξ ∈ R ⁿ , there exist numbers σ > 0 and T ∈ R¹ such that P(ξ) ≥ σ(1 + |ξ|) ^T for all ξ ∈ R ⁿ . The greatest of numbers T satisfying this condition, denoted by ST(P), is called Seidenberg-Tarski number of polynomial P. It is known that if, in addition, P ∈ I _n , that is, |P(ξ)| → ∞ as |ξ| → ∞, then T = T(P) > 0. In this paper, for a class of almost hypoelliptic polynomials of n (≥ 2) variables we find a sufficient condition for ST(P) ≥ 1. Moreover, in the case n = 2, we prove that ST(P) ≥ 1 for any almost hypoelliptic polynomial P ∈ I₂.     

On Excess-time Correlated Cumulative Processes

In this paper a class of correlated cumulative processes, B _s (t) = ∑^N(t)_i=1 H _s (X _i )X _i , is studied with excess level increments X _i ?s, where {N(t), t ?0} is the counting process generated by the renewal sequence T _n , T _n and X _n are correlated for given n, H _s (t) is the Heaviside function and s?0 is a given constant. Several useful results, for the distributions of B _s (t), and that of the number of excess (non-excess) increments on (0, t) and the corresponding means, are derived. First passage time problems are also discussed and various asymptotic properties of the processes are obtained. Transform results, by applying a flexible form for the joint distribution of correlated pairs (T _n , X _n ) are derived and inverted. The case of non-excess level increments, X _i < s, is also considered. Finally, applications to known stochastic shock and pro-rata warranty models are given.     

Equiconvergence of expansions in multiple Fourier series and in fourier integrals with “lacunary sequences of partial sums”

We investigate the equiconvergence on T^N = [?π, π)^N of expansions in multiple trigonometric Fourier series and in the Fourier integrals of functions f ∈ L_p(T^N) and g ∈ L_p(R^N), p > 1, N ≥ 3, g(x) = f(x) on T^N, in the case where the “partial sums” of these expansions, i.e., S_n(x; f) and J_α(x; g), respectively, have “numbers” n ∈ Z^N and α ∈ R^N (n_j = [α_j], j = 1,..., N, [t] is the integral part of t ∈ R¹) containing N ? 1 components which are elements of “lacunary sequences.”     

Paranormal Elements in Normed Algebra

For a normed algebra A and natural numbers k we introduce and investigate the ∥ · ∥ closed classes P _k (A). We show that P₁(A) is a subset of P _k (A) for all k. If T in P₁(A), then Tⁿ lies in P₁(A) for all natural n. If A is unital, U, V ∈ A are such that ∥U∥ = ∥V∥ = 1, VU = I and T lies in P _k (A), then UTV lies in P _k (A) for all natural k. Let A be unital, then 1) if an element T in P₁(A) is right invertible, then any right inverse element T^?1 lies in P₁(A); 2) for ßßIßß = 1 the class P₁(A) consists of normaloid elements; 3) if the spectrum of an element T, T ∈ P₁(A) lies on the unit circle, then ∥TX∥ = ∥X∥ for all X ∈ A. If A = B(H), then the class P₁(A) coincides with the set of all paranormal operators on a Hilbert space H.     

Fast Algorithm of Square Rooting in Some Finite Fields of Odd Characteristic

It was proved that the complexity of square root computation in the Galois field GF(3^s), s = 2^kr, is equal to O(M(2^k)M(r)k + M(r) log₂r) + 2^kkr^1+o(1), where M (n) is the complexity of multiplication of polynomials of degree n over fields of characteristics 3. The complexity of multiplication and division in the field GF(3^s) is equal to O(M(2^k)M(r)) and O(M(2^k)M(r)) + r^1+o(1), respectively. If the basis in the field GF(3^r) is determined by an irreducible binomial over GF(3) or is an optimal normal basis, then the summands 2^kkr^1+o(1) and r^1+o(1) can be omitted. For M(n) one may take n log₂nψ(n) where ψ(n) grows slower than any iteration of the logarithm. If k grow and r is fixed, than all the estimates presented here have the form O_r (M (s) log ₂s) = s (log ₂s)²ψ(s).     

On conditions for permutability of Toeplitz and Hankel matrices

The problem of describing pairs of commuting matrices (T, H), where T and H are a Toeplitz and a Hankel matrix, respectively, is examined. Several families of such pairs are indicated.