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.     

Modified Kantorovich theorem and asymptotic approximations of solutions to singularly perturbed systems of ordinary differential equations

The functional equation f(x,ε) = 0 containing a small parameter ε and admitting regular and singular degeneracy as ε → 0 is considered. By the methods of small parameter, a function x _n ⁰(ε) satisfying this equation within a residual error of O(ε ⁿ⁺¹) is found. A modified Newton’s sequence starting from the element x _n ⁰(ε) is constructed. The existence of the limit of Newton’s sequence is based on the NK theorem proven in this work (a new variant of the proof of the Kantorovich theorem substantiating the convergence of Newton’s iterative sequence). The deviation of the limit of Newton’s sequence from the initial approximation x _n ⁰(ε) has the order of O(ε ⁿ⁺¹), which proves the asymptotic character of the approximation x _n ⁰(ε). The method proposed is implemented in constructing an asymptotic approximation of a system of ordinary differential equations on a finite or infinite time interval with a small parameter multiplying the derivatives, but it can be applied to a wider class of functional equations with a small parameters.     

A Polynomial Time Algorithm for the Resource Allocation Problem with a Convex Objective Function

Consider the resource allocation problem:minimize ∑ⁿ_i=1 f_i(x_i) subject to ∑ⁿ_i=1 x_i = N and x_i's being nonnegative integers, where each f_i is a convex function. The well-known algorithm based on the incremental method requires O(N log n + n) time to solve this problem. We propose here a new algorithm based on the Lagrange multiplier method, requiring O[n²(log N)²] time. The latter is faster if N is much larger than n. Such a situation occurs, for example, when the optimal sample size problem related to monitoring the urban air pollution is treated.     

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).     

Generic hypersurface singularities

The problem considered here can be viewed as the analogue in higher dimensions of the one variable polynomial interpolation of Lagrange and Newton. Let x₁,...,x_r be closed points in general position in projective spacePn, then the linear subspaceV ofH⁰ (?ⁿ,O(d)) (the space of homogeneous polynomials of degreed on ?ⁿ) formed by those polynomials which are singular at eachx_i, is given by r(n + 1) linear equations in the coefficients, expressing the fact that the polynomial vanishes with its first derivatives at x₁,...,x_r. As such, the “expected” value for the dimension ofV is max(0,h⁰(O(d))?r(n+1)). We prove thatV has the “expected” dimension for d≥5 (theorem A). This theorem was first proven in [A] using a very complicated induction with many initial cases. Here we give a greatly simplified proof using techniques developed by the authors while treating the corresponding problem in lower degrees.     

On an Extremal Problem for Poset Dimension

Let f(n) be the largest integer such that every poset on n elements has a 2-dimensional subposet on f(n) elements. What is the asymptotics of f(n)? It is easy to see that f(n) = n ^1/2. We improve the best known upper bound and show f(n) = O (n ^2/3). For higher dimensions, we show \(f_{d}(n)=\O \left (n^{\frac {d}{d + 1}}\right )\), where f _d (n) is the largest integer such that every poset on n elements has a d-dimensional subposet on f _d (n) elements.     

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.

     

Accelerated PMHSS iteration methods for complex symmetric linear systems

In this paper, we introduce and analyze an accelerated preconditioning modification of the Hermitian and skew-Hermitian splitting (APMHSS) iteration method for solving a broad class of complex symmetric linear systems. This accelerated PMHSS algorithm involves two iteration parameters α,β and two preconditioned matrices whose special choices can recover the known PMHSS (preconditioned modification of the Hermitian and skew-Hermitian splitting) iteration method which includes the MHSS method, as well as yield new ones. The convergence theory of this class of APMHSS iteration methods is established under suitable conditions. Each iteration of this method requires the solution of two linear systems with real symmetric positive definite coefficient matrices. Theoretical analyses show that the upper bound σ₁(α,β) of the asymptotic convergence rate of the APMHSS method is smaller than that of the PMHSS iteration method. This implies that the APMHSS method may converge faster than the PMHSS method. Numerical experiments on a few model problems are presented to illustrate the theoretical results and examine the numerical effectiveness of the new method.     

Global existence of real roots and random Newton flow algorithm for nonlinear system of equations

To solve nonlinear system of equation, F(x) = 0, a continuous Newton flow x _t (t) = V (x) = ?(DF(x))^?1 F(x), x(0) = x ⁰ and its mathematical properties, such as the central field, global existence and uniqueness of real roots and the structure of the singular surface, are studied. We concisely introduce random Newton flow algorithm (NFA) for finding all roots, based on discrete Newton flow x ^j+1 = x ^j + hV (x ^j ) with random initial value x ⁰ and h ∈ (0, 1], and three computable quantities, g _j , d _j and K _j . The numerical experiments with dimension n = 300 are provided.     

Compressed Sensing and Matrix Completion with Constant Proportion of Corruptions

In this paper, we improve existing results in the field of compressed sensing and matrix completion when sampled data may be grossly corrupted. We introduce three new theorems. (1) In compressed sensing, we show that if the m×n sensing matrix has independent Gaussian entries, then one can recover a sparse signal x exactly by tractable ? ₁ minimization even if a positive fraction of the measurements are arbitrarily corrupted, provided the number of nonzero entries in x is O(m/(log(n/m)+1)). (2) In the very general sensing model introduced in Candès and Plan (IEEE Trans. Inf. Theory 57(11):7235–7254, 2011) and assuming a positive fraction of corrupted measurements, exact recovery still holds if the signal now has O(m/(log² n)) nonzero entries. (3) Finally, we prove that one can recover an n×n low-rank matrix from m corrupted sampled entries by tractable optimization provided the rank is on the order of O(m/(nlog² n)); again, this holds when there is a positive fraction of corrupted samples.     

A continuation method for solving symmetric Toeplitz systems

A fast algorithm is proposed for solving symmetric Toeplitz systems. This algorithm continuously transforms the identity matrix into the inverse of a given Toeplitz matrix T. The memory requirements for the algorithm are O(n), and its complexity is O(log κ(T)nlogn), where (T) is the condition number of T. Numerical results are presented that confirm the efficiency of the proposed algorithm.     

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.     

The communication complexity of addition

Suppose each of k≤n ^o(1) players holds an n-bit number x _i in its hand. The players wish to determine if ∑ _i≤k x _i =s. We give a public-coin protocol with error 1% and communication O(k logk). The communication bound is independent of n, and for k≥3 improves on the O(k logn) bound by Nisan (Bolyai Soc. Math. Studies; 1993).     

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.     

A note on scheduling jobs with equal processing times and inclusive processing set restrictions

We consider the problem of scheduling n jobs on m parallel machines with inclusive processing set restrictions. Each job has a given release date, and all jobs have equal processing times. The objective is to minimize the makespan of the schedule. Li and Li (2015) have developed an O(n²+mn log?n) time algorithm for this problem. In this note, we present a modified algorithm with an improved time complexity of O(min{m, log?n} ? n log?n).     

Fast heuristics for protection networks for dynamic routing

Traffic volatility and network reliability are important issues in the provision of high speed network services. We consider the construction of a second network, the protection network which can carry overload traffic due to the failure or congestion of any two links in the original network. The level of protection against such contingencies can be specified by a traffic requirement matrix. We construct a fully connected protection network, for an n node network, using an O(n²) heuristic based on the largest two traffic requirements for each node. This procedure is then modified to generate a more effective O(n⁴) heuristic, both methods facilitate fast processing for two-hop dynamic routing. We compare the performance of the heuristics with the O(n¹⁵) optimal solution.     

A new infeasible-interior-point algorithm for linear programming over symmetric cones

In this paper we present an infeasible-interior-point algorithm, based on a new wide neighbourhood N(τ₁, τ₂, η), for linear programming over symmetric cones. We treat the classical Newton direction as the sum of two other directions. We prove that if these two directions are equipped with different and appropriate step sizes, then the new algorithm has a polynomial convergence for the commutative class of search directions. In particular, the complexity bound is O(r^1.5logε^?1) for the Nesterov-Todd (NT) direction, and O(r²logε^?1) for the xs and sx directions, where r is the rank of the associated Euclidean Jordan algebra and ε > 0 is the required precision. If starting with a feasible point (x⁰, y⁰, s⁰) in N(τ₁, τ₂, η), the complexity bound is \(O\left( {\sqrt r \log {\varepsilon ^{ - 1}}} \right)\) for the NT direction, and O(rlogε^?1) for the xs and sx directions. When the NT search direction is used, we get the best complexity bound of wide neighborhood interior-point algorithm for linear programming over symmetric cones.     

Optimal Embeddings of Bessel-Potential-Type Spaces into Generalized Hölder Spaces Involving <Emphasis Type="Italic">k</Emphasis>-Modulus of Smoothness

We establish necessary and sufficient conditions for embeddings of Bessel potential spaces H ^σ X(IR ⁿ ) with order of smoothness σ?∈?(0, n), modelled upon rearrangement invariant Banach function spaces X(IR ⁿ ), into generalized Hölder spaces (involving k-modulus of smoothness). We apply our results to the case when X(IR ⁿ ) is the Lorentz-Karamata space \(L_{p,q;b}({{\rm I\kern-.17em R}}^n)\). In particular, we are able to characterize optimal embeddings of Bessel potential spaces \(H^{\sigma}L_{p,q;b}({{\rm I\kern-.17em R}}^n)\) into generalized Hölder spaces. Applications cover both superlimiting and limiting cases. We also show that our results yield new and sharp embeddings of Sobolev-Orlicz spaces W ^k?+?1 L ^n/k(logL) ^α (IR ⁿ ) and W ^k L ^n/k(logL) ^α (IR ⁿ ) into generalized Hölder spaces.     

New approximations to the principal real-valued branch of the Lambert <Emphasis Type="Italic">W</Emphasis>-function

The Lambert W-function is the solution to the transcendental equation W(x)e ^W(x) = x. It has two real branches, one of which, for x ∈ [?1/e, ∞], is usually denoted as the principal branch. On this branch, the function grows from ? 1 to infinity, logarithmically at large x. The present work is devoted to the construction of accurate approximations for the principal branch of the W-function. In particular, a simple, global analytic approximation is derived that covers the whole branch with a maximum relative error smaller than 5 × 10^?3. Starting from it, machine precision accuracy is reached everywhere with only three steps of a quadratically convergent iterative scheme, here examined for the first time, which is more efficient than standard Newton’s iteration at large x. Analytic bounds for W are also constructed, for x > e, which are much tighter than those currently available. It is noted that the exponential of the upper bounding function yields an upper bound for the prime counting function π(n) that is better than the well-known Chebyshev’s estimates at large n. Finally, the construction of accurate approximations to W based on Chebyshev spectral theory is discussed; the difficulties involved are highlighted, and methods to overcome them are presented.     

Homogenization of the Dirichlet problem for elliptic and parabolic systems with periodic coefficients

Let O ? R ^d be a bounded domain of class C ^1,1. Let 0 < ε - 1. In L ₂(O;C ⁿ ) we consider a positive definite strongly elliptic second-order operator B _D,ε with Dirichlet boundary condition. Its coefficients are periodic and depend on x/ε. The principal part of the operator is given in factorized form, and the operator has lower order terms. We study the behavior of the generalized resolvent (B _D,ε ? ζQ ₀(·/ε))^?1 as ε → 0. Here the matrix-valued function Q ₀ is periodic, bounded, and positive definite; ζ is a complex-valued parameter. We find approximations of the generalized resolvent in the L ₂(O;C ⁿ )-operator norm and in the norm of operators acting from L ₂(O;C ⁿ ) to the Sobolev space H ¹(O;C ⁿ ) with two-parameter error estimates (depending on ε and ζ). Approximations of the generalized resolvent are applied to the homogenization of the solution of the first initial-boundary value problem for the parabolic equation Q ₀(x/ε)? _t v _ε (x, t) = ?(B _D,ε v _ε )(x, t).