SPSA algorithms with measurement reuse

Four algorithms, all variants of Simultaneous Perturbation Stochastic Approximation (SPSA), are proposed. The original one-measurement SPSA uses an estimate of the gradient of objective function L containing an additional bias term not seen in two-measurement SPSA. As a result, the asymptotic covariance matrix of the iterate convergence process has a bias term. We propose a one-measurement algorithm that eliminates this bias, and has asymptotic convergence properties making for easier comparison with the two-measurement SPSA. The algorithm, under certain conditions, outperforms both forms of SPSA with the only overhead being the storage of a single measurement. We also propose a similar algorithm that uses perturbations obtained from normalized Hadamard matrices. The convergence w.p. 1 of both algorithms is established. We extend measurement reuse to design two second-order SPSA algorithms and sketch the convergence analysis. Finally, we present simulation results on an illustrative minimization problem.

Intermolecular interactions in pi -conjugated systems: Application to polyenes

A computational scheme has been developed for strongly interacting systems wherein the intermolecular interaction is introduced as a charge-induced-dipole term. Within this approximation, the model Hamiltonian is exactly solved using a valence-bond basis. The validity of the scheme has been checked by use of exact calculations on small model systems. The method has been applied to finite polyenes to study the shifts in the ground-state energies and dipole-allowed excited-state energies in the presence of neighbors. Our calculations show a red shift in the optical gap of the infinite polyene by 0.124 eV, which is rather small compared to the experimental red shift. This is traced to the larger inaccuracy in the calculated shift in the excited state. The calculated shift in the ground-state energies are more accurate and hence the method is better suited for studying the effect of intermolecular interactions on the properties of the ground state.

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.

New computational approaches for wrinkled and slack membranes

The static response of thin, wrinkled membranes is studied using both a tension field approximation based on plane stress conditions and a 3D nonlinear elasticityformulation, discretized through 8-noded Cosserat point elements. While the tension field approach only obtains the wrinkled/slack regions and at best a measure of the extent of wrinkliness, the 3D elasticity solution provides, in principle, the deformed shape of a wrinkled/slack membrane. However, since membranes barely resist compression, the discretized and linearized system equations via both the approaches are ill-conditioned and solutions could thus be sensitive to discretizations errors as well as other sources of noises/imperfections. We propose a regularized, pseudo-dynamical recursion scheme that provides a sequence of updates, which are almost insensitive to theregularizing term as well as the time step size used for integrating the pseudo-dynamical form. This is borne out through several numerical examples wherein the relative performance of the proposed recursion scheme vis-a-vis a regularized Newton strategy is compared. The pseudo-time marching strategy, when implemented using 3D Cosserat point elements, also provides a computationally cheaper, numerically accurate and simpler alternative to that using geometrically exact shell theories for computing large deformations of membranes in the presence of wrinkles. (C) 2010 Elsevier Ltd. All rights reserved.

Parametrized tests of post-Newtonian theory using Advanced LIGO and Einstein Telescope

General relativity has very specific predictions for the gravitational waveforms from inspiralling compact binaries obtained using the post-Newtonian (PN) approximation. We investigate the extent to which the measurement of the PN coefficients, possible with the second generation gravitational-wave detectors such as the Advanced Laser Interferometer Gravitational-Wave Observatory (LIGO) and the third generation gravitational-wave detectors such as the Einstein Telescope (ET), could be used to test post-Newtonian theory and to put bounds on a subclass of parametrized-post-Einstein theories which differ from general relativity in a parametrized sense. We demonstrate this possibility by employing the best inspiralling waveform model for nonspinning compact binaries which is 3.5PN accurate in phase and 3PN in amplitude. Within the class of theories considered, Advanced LIGO can test the theory at 1.5PN and thus the leading tail term. Future observations of stellar mass black hole binaries by ET can test the consistency between the various PN coefficients in the gravitational-wave phasing over the mass range of 11-44M(circle dot). The choice of the lower frequency cutoff is important for testing post-Newtonian theory using the ET. The bias in the test arising from the assumption of nonspinning binaries is indicated.

Embracing Integrability in Stellar and Planetary Dynamics

Hamiltonian systems in stellar and planetary dynamics are typically near integrable. For example, Solar System planets are almost in two-body orbits, and in simulations of the Galaxy, the orbits of stars seem regular. For such systems, sophisticated numerical methods can be developed through integrable approximations. Following this theme, we discuss three distinct problems. We start by considering numerical integration techniques for planetary systems. Perturbation methods (that utilize the integrability of the two-body motion) are preferred over conventional "blind" integration schemes. We introduce perturbation methods formulated with Cartesian variables. In our numerical comparisons, these are superior to their conventional counterparts, but, by definition, lack the energy-preserving properties of symplectic integrators. However, they are exceptionally well suited for relatively short-term integrations in which moderately high positional accuracy is required. The next exercise falls into the category of stability questions in solar systems. Traditionally, the interest has been on the orbital stability of planets, which have been quantified, e.g., by Liapunov exponents. We offer a complementary aspect by considering the protective effect that massive gas giants, like Jupiter, can offer to Earth-like planets inside the habitable zone of a planetary system. Our method produces a single quantity, called the escape rate, which characterizes the system of giant planets. We obtain some interesting results by computing escape rates for the Solar System. Galaxy modelling is our third and final topic. Because of the sheer number of stars (about 10^11 in Milky Way) galaxies are often modelled as smooth potentials hosting distributions of stars. Unfortunately, only a handful of suitable potentials are integrable (harmonic oscillator, isochrone and Stäckel potential). This severely limits the possibilities of finding an integrable approximation for an observed galaxy. A solution to this problem is torus construction; a method for numerically creating a foliation of invariant phase-space tori corresponding to a given target Hamiltonian. Canonically, the invariant tori are constructed by deforming the tori of some existing integrable toy Hamiltonian. Our contribution is to demonstrate how this can be accomplished by using a Stäckel toy Hamiltonian in ellipsoidal coordinates.

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.

Mid-urethral slings for treatment of stress urinary incontinence : long- and mid-term follow-up

Urinary incontinence is a common problem, affecting one third of the women at least at some time during their lives. The prevalence of urinary incontinence increases with advancing age, and the everyday impact of incontinence on women and on health services is enormous. Urinary incontinence is usually divided into three different subtypes, of which stress urinary incontinence (SUI) is the most common. Surgical treatment is often needed to cure SUI, and modern mid-urethral sling procedures give the possibility to cure this condition with a low risk of adverse events, a problem often associated with the so-called traditional incontinence operations. Life expectancy among women in Western countries has grown beyond 80 years of age. Long-term efficacy of treatment options for urinary incontinence therefore becomes an important issue in a world with limited eco-nomic resources. The purpose of the present study was to prospectively evaluate the long-term efficacy and safety of the first minimally invasive mid-urethral tape procedure, the Tension-free Vaginal Tape (TVT) procedure. The long-term (5-year) follow-up results of the TVT procedure as a repeat operation af-ter an unsuccessful mid-urethral tape operation were studied and the reasons for failure of the first operation were analyzed. Another purpose was to compare the original TVT procedure with a newer modification, the Tension-free Vaginal Tape Obturator (TVT-O) procedure within a multi-centre, randomized context in order to find out possible differences between these procedures re-garding efficacy and complications and the effects on symptoms of urgency. The first study of the present thesis is a prospective, Nordic, three-centre follow-up study of 90 women suffering from SUI, who were treated by means of the TVT procedure. The mean follow-up time was more than eleven years, and the study is the first to be published in connection with more than ten years of follow-up. The second study is a retrospective analysis of 26 women who were treated with a repeat TVT procedure after an unsuccessful primary mid-urethral tape procedure. The third and fourth studies concern 273 women in seven centres in Finland who were ran-domly assigned to the TVT and TVT-O procedures, the 3-year follow-up results of which are pre-sented in this thesis. After eleven years of follow-up, 90% of the women had a negative cough stress test result and a negative 24-h pad test result. The subjective cure rate measured as the women s global impression of cure was 77%, the rate of improvement 20%, and only 3% thought that the treatment had failed. No late-onset adverse effects were found. The repeat TVT procedure was successful in 75% of the cases when women who were cured and women who were significantly improved were included. The reasons for failure of the first operation could be separated into four different groups: tape material-related, operation technique-related, concomitant illness-related and a group with no identifiable reason. There were no intra-operative complications during the repeat operation. In the randomized trial comparing the TVT with the TVT-O procedure a cough stress test results were negative in 94.6% and 89.5% of the women in the two groups, respectively, after a 3-year follow-up period. There were no statistical differences in the cure rate or the rate of complications be-tween the two procedures. Symptoms of urgency were analyzed more closely and the main finding was that the prevalence of urgency symptoms decreased significantly after both mid-urethral sling procedures. The TVT operation was found to be an effective and safe procedure even after eleven years of follow-up. Long-term follow-up after a repeat TVT procedure revealed that the TVT procedure can well be considered after an unsuccessful mid-urethra tape procedure, because 75% of the patients showed significantly improvement of their incontinence. The TVT and TVT-O procedures showed no statistically significant differences in efficacy and rate of complications after three years of follow-up. In most cases these procedures alleviate preoperative symptoms of urgency and the risk of developing de novo urgency is low.

Fast distributed approximation algorithms for vertex cover and set cover in anonymous networks

We present a distributed algorithm that finds a maximal edge packing in O(Δ + log* W) synchronous communication rounds in a weighted graph, independent of the number of nodes in the network; here Δ is the maximum degree of the graph and W is the maximum weight. As a direct application, we have a distributed 2-approximation algorithm for minimum-weight vertex cover, with the same running time. We also show how to find an f-approximation of minimum-weight set cover in O(f2k2 + fk log* W) rounds; here k is the maximum size of a subset in the set cover instance, f is the maximum frequency of an element, and W is the maximum weight of a subset. The algorithms are deterministic, and they can be applied in anonymous networks.

A local 2-approximation algorithm for the vertex cover problem

We present a distributed 2-approximation algorithm for the minimum vertex cover problem. The algorithm is deterministic, and it runs in (Δ + 1)2 synchronous communication rounds, where Δ is the maximum degree of the graph. For Δ = 3, we give a 2-approximation algorithm also for the weighted version of the problem.

A simple local 3-approximation algorithm for vertex cover

We present a local algorithm (constant-time distributed algorithm) for finding a 3-approximate vertex cover in bounded-degree graphs. The algorithm is deterministic, and no auxiliary information besides port numbering is required. (c) 2009 Elsevier B.V. All rights reserved.