Hardness of approximation results for the problem of finding the stopping distance in Tanner graphs

Tanner Graph representation of linear block codes is widely used by iterative decoding algorithms for recovering data transmitted across a noisy communication channel from errors and erasures introduced by the channel. The stopping distance of a Tanner graph T for a binary linear block code C determines the number of erasures correctable using iterative decoding on the Tanner graph T when data is transmitted across a binary erasure channel using the code C. We show that the problem of finding the stopping distance of a Tanner graph is hard to approximate within any positive constant approximation ratio in polynomial time unless P = NP. It is also shown as a consequence that there can be no approximation algorithm for the problem achieving an approximation ratio of 2(log n)(1-epsilon) for any epsilon > 0 unless NP subset of DTIME(n(poly(log n))).

Dynamical cluster approximation: Nonlocal dynamics of correlated electron systems

We recently introduced the dynamical cluster approximation (DCA), a technique that includes short-ranged dynamical correlations in addition to the local dynamics of the dynamical mean-field approximation while preserving causality. The technique is based on an iterative self-consistency scheme on a finite-size periodic cluster. The dynamical mean-field approximation (exact result) is obtained by taking the cluster to a single site (the thermodynamic limit). Here, we provide details of our method, explicitly show that it is causal, systematic, Phi derivable, and that it becomes conserving as the cluster size increases. We demonstrate the DCA by applying it to a quantum Monte Carlo and exact enumeration study of the two-dimensional Falicov-Kimball model. The resulting spectral functions preserve causality, and the spectra and the charge-density-wave transition temperature converge quickly and systematically to the thermodynamic limit as the cluster size increases.

Approximation of Internal Refractive Index Variation Improves Image Guided Diffuse Optical Tomography of Breast

Effective usage of image guidance by incorporating the refractive index (RI) variation in computational modeling of light propagation in tissue is investigated to assess its impact on optical-property estimation. With the aid of realistic patient breast three-dimensional models, the variation in RI for different regions of tissue under investigation is shown to influence the estimation of optical properties in image-guided diffuse optical tomography (IG-DOT) using numerical simulations. It is also shown that by assuming identical RI for all regions of tissue would lead to erroneous estimation of optical properties. The a priori knowledge of the RI for the segmented regions of tissue in IG-DOT, which is difficult to obtain for the in vivo cases, leads to more accurate estimates of optical properties. Even inclusion of approximated RI values, obtained from the literature, for the regions of tissue resulted in better estimates of optical properties, with values comparable to that of having the correct knowledge of RI for different regions of tissue.

Unified Galerkin- and DAE-Based Approximation of Fractional Order Systems

We consider numerical solutions of nonlinear multiterm fractional integrodifferential equations, where the order of the highest derivative is fractional and positive but is otherwise arbitrary. Here, we extend and unify our previous work, where a Galerkin method was developed for efficiently approximating fractional order operators and where elements of the present differential algebraic equation (DAE) formulation were introduced. The DAE system developed here for arbitrary orders of the fractional derivative includes an added block of equations for each fractional order operator, as well as forcing terms arising from nonzero initial conditions. We motivate and explain the structure of the DAE in detail. We explain how nonzero initial conditions should be incorporated within the approximation. We point out that our approach approximates the system and not a specific solution. Consequently, some questions not easily accessible to solvers of initial value problems, such as stability analyses, can be tackled using our approach. Numerical examples show excellent accuracy. DOI: 10.1115/1.4002516]

Activation barriers for d.c. conductivity in ionic glasses: Classical calculations using the small-cluster approximation

A small-cluster approximation has been used to calculate the activation barriers for the d.c. conductivity in ionic glasses. The main emphasis of this approach is on the importance of the hitherto ignored polarization energy contribution to the total activation energy. For the first time it has been demonstrated that the d.c. conductivity activation energy can be calculated by considering ionic migration to a neighbouring vacancy in a smali cluster of ions consisting of face-sharing anion polyhedra. The activation energies from the model calculations have been compared with the experimental values in the case of highly modified lithium thioborate glasses.

Phase diagram of the two-dimensional disordered Hubbard model in the Hartree-Fock approximation

Ground-state properties of the two-dimensional Hubbard model with point-defect disorder are investigated numerically in the Hartree-Fock approximation. The phase diagram in the p(point defect concentration)-delta(deviation from half filling) plane exhibits antiferromagnetic, spin-density-wave, paramagnetic, and spin-glass-like phases. The disorder stabilizes the antiferromagnetic phase relative to the spin-density-wave phase. The presence of U strongly enhances the localization in the antiferromagnetic phase. The spin-density-wave and spin-glass-like phases are weakly localized.

New Approximation Algorithms for Minimum Cycle Bases of Graphs

We consider the problem of computing an approximate minimum cycle basis of an undirected non-negative edge-weighted graph G with m edges and n vertices; the extension to directed graphs is also discussed. In this problem, a {0,1} incidence vector is associated with each cycle and the vector space over F-2 generated by these vectors is the cycle space of G. A set of cycles is called a cycle basis of G if it forms a basis for its cycle space. A cycle basis where the sum of the weights of the cycles is minimum is called a minimum cycle basis of G. Cycle bases of low weight are useful in a number of contexts, e.g. the analysis of electrical networks, structural engineering, chemistry, and surface reconstruction. Although in most such applications any cycle basis can be used, a low weight cycle basis often translates to better performance and/or numerical stability. Despite the fact that the problem can be solved exactly in polynomial time, we design approximation algorithms since the performance of the exact algorithms may be too expensive for some practical applications. We present two new algorithms to compute an approximate minimum cycle basis. For any integer k >= 1, we give (2k - 1)-approximation algorithms with expected running time O(kmn(1+2/k) + mn((1+1/k)(omega-1))) and deterministic running time O(n(3+2/k) ), respectively. Here omega is the best exponent of matrix multiplication. It is presently known that omega < 2.376. Both algorithms are o(m(omega)) for dense graphs. This is the first time that any algorithm which computes sparse cycle bases with a guarantee drops below the Theta(m(omega) ) bound. We also present a 2-approximation algorithm with expected running time O(M-omega root n log n), a linear time 2-approximation algorithm for planar graphs and an O(n(3)) time 2.42-approximation algorithm for the complete Euclidean graph in the plane.

Decoupled three-dimensional finite element computation of thermoelastic damping using Zener's approximation

We consider three dimensional finite element computations of thermoelastic damping ratios of arbitrary bodies using Zener's approach. In our small-damping formulation, unlike existing fully coupled formulations, the calculation is split into three smaller parts. Of these, the first sub-calculation involves routine undamped modal analysis using ANSYS. The second sub-calculation takes the mode shape, and solves on the same mesh a periodic heat conduction problem. Finally, the damping coefficient is a volume integral, evaluated elementwise. In the only other decoupled three dimensional computation of thermoelastic damping reported in the literature, the heat conduction problem is solved much less efficiently, using a modal expansion. We provide numerical examples using some beam-like geometries, for which Zener's and similar formulas are valid. Among these we examine tapered beams, including the limiting case of a sharp tip. The latter's higher-mode damping ratios dramatically exceed those of a comparable uniform beam.

Stochastic Approximation Algorithms for Constrained Optimization via Simulation

We develop four algorithms for simulation-based optimization under multiple inequality constraints. Both the cost and the constraint functions are considered to be long-run averages of certain state-dependent single-stage functions. We pose the problem in the simulation optimization framework by using the Lagrange multiplier method. Two of our algorithms estimate only the gradient of the Lagrangian, while the other two estimate both the gradient and the Hessian of it. In the process, we also develop various new estimators for the gradient and Hessian. All our algorithms use two simulations each. Two of these algorithms are based on the smoothed functional (SF) technique, while the other two are based on the simultaneous perturbation stochastic approximation (SPSA) method. We prove the convergence of our algorithms and show numerical experiments on a setting involving an open Jackson network. The Newton-based SF algorithm is seen to show the best overall performance.

An actor-critic algorithm with function approximation for discounted cost constrained Markov decision processes

We develop in this article the first actor-critic reinforcement learning algorithm with function approximation for a problem of control under multiple inequality constraints. We consider the infinite horizon discounted cost framework in which both the objective and the constraint functions are suitable expected policy-dependent discounted sums of certain sample path functions. We apply the Lagrange multiplier method to handle the inequality constraints. Our algorithm makes use of multi-timescale stochastic approximation and incorporates a temporal difference (TD) critic and an actor that makes a gradient search in the space of policy parameters using efficient simultaneous perturbation stochastic approximation (SPSA) gradient estimates. We prove the asymptotic almost sure convergence of our algorithm to a locally optimal policy. (C) 2010 Elsevier B.V. All rights reserved.

A two timescale stochastic approximation scheme for simulation-based parametric optimization

A two timescale stochastic approximation scheme which uses coupled iterations is used for simulation-based parametric optimization as an alternative to traditional "infinitesimal perturbation analysis" schemes, It avoids the aggregation of data present in many other schemes. Its convergence is analyzed, and a queueing example is presented.