Faster algorithms for all-pairs small stretch distances in weighted graphs

Abstract. Let G = (V,E) be a weighted undirected graph, with non-negative edge weights. We consider the problem of efficiently computing approximate distances between all pairs of vertices in G. While many efficient algorithms are known for this problem in unweighted graphs, not many results are known for this problem in weighted graphs. Zwick [14] showed that for any fixed ε> 0, stretch 1 1 + ε distances between all pairs of vertices in a weighted directed graph on n vertices can be computed in Õ(n ω) time, where ω < 2.376 is the exponent of matrix multiplication and n is the number of vertices. It is known that finding distances of stretch less than 2 between all pairs of vertices in G is at least as hard as Boolean matrix multiplication of two n×n matrices. It is also known that all-pairs stretch 3 distances can be computed in Õ(n 2) time and all-pairs stretch 7/3 distances can be computed in Õ(n 7/3) time. Here we consider efficient algorithms for the problem of computing all-pairs stretch (2+ε) distances in G, for any 0 < ε < 1. We show that all pairs stretch (2 + ε) distances for any fixed ε> 0 in G can be computed in expected time O(n 9/4 logn). This algorithm uses a fast rectangular matrix multiplication subroutine. We also present a combinatorial algorithm (that is, it does not use fast matrix multiplication) with expected running time O(n 9/4) for computing all-pairs stretch 5/2 distances in G. 1

Bi-directional Switch Commutation for a Resonant Matrix Converter supplying a Contactless Energy Transmission System

This paper describes a bi-directional switch commutation strategy for a resonant matrix converter loaded with a contactless energy transmission system. Due to the different application compared to classical 3 phase to 3 phase matrix converters supplying induction machines a new investigation of possible commutation principles is necessary. The paper therefore compares the full bridge series-resonant converter with the 3 phase to 2 phase matrix converter. From the commutation of the full bridge series-resonant converter, conditions for the bi-directional switch commutation are derived. One of the main benefits of the derived strategy is the minimization of commutation steps, which is independent from the load current sign.

Optimal Exact-Regenerating Codes for Distributed Storage at the MSR and MBR Points via a Product-Matrix Construction

Regenerating codes are a class of distributed storage codes that allow for efficient repair of failed nodes, as compared to traditional erasure codes. An [n, k, d] regenerating code permits the data to be recovered by connecting to any k of the n nodes in the network, while requiring that a failed node be repaired by connecting to any d nodes. The amount of data downloaded for repair is typically much smaller than the size of the source data. Previous constructions of exact-regenerating codes have been confined to the case n = d + 1. In this paper, we present optimal, explicit constructions of (a) Minimum Bandwidth Regenerating (MBR) codes for all values of [n, k, d] and (b) Minimum Storage Regenerating (MSR) codes for all [n, k, d >= 2k - 2], using a new product-matrix framework. The product-matrix framework is also shown to significantly simplify system operation. To the best of our knowledge, these are the first constructions of exact-regenerating codes that allow the number n of nodes in the network, to be chosen independent of the other parameters. The paper also contains a simpler description, in the product-matrix framework, of a previously constructed MSR code with [n = d + 1, k, d >= 2k - 1].

Effect of rolling temperature and reduction in thickness on microstructure and mechanical properties of ZM21 magnesium alloy and its subsequent annealing treatment

In this present paper, the effects of non-isothermal rolling temperature and reduction in thickness followed by annealing on microstructure and mechanical properties of ZM21 magnesium alloy were investigated. The alloy rolled at four different temperatures 250 degrees C, 300 degrees C, 350 degrees C and 400 degrees C with reductions of 25%, 50% and 75%. Non-isothermal rolling resulted in grain refinement, introduction of shear bands and twins in the matrix alloy. Partial to full recrystallization was observed when the rolling temperature was above recrystallization temperature. Rolling and subsequent annealing resulted in strain-free equiaxed grains and complete disappearance of shear bands and twins. Maximum ultimate strength (345 MPa) with good ductility (14%) observed in the sample rolled at 250 degrees C with 75% reduction in thickness followed by short annealing. Recrystallization during warm/hot rolling was sluggish, but post-roll treatment gives distinct views about dynamic and static recrystallization. (C) 2011 Elsevier B.V. All rights reserved.

Symmetry of one-dimensional dynamical systems in terms of transfer matrix parameters

The concept of symmetry for passive, one-dimensional dynamical systems is well understood in terms of the impedance matrix, or alternatively, the mobility matrix. In the past two decades, however, it has been established that the transfer matrix method is ideally suited for the analysis and synthesis of such systems. In this paper an investigatiob is described of what symmetry means in terms of the transfer matrix parameters of an passive element or a set of elements. One-dimensional flexural systems with 4 × 4 transfer matrices as well as acoustical and mechanical systems characterized by 2 × 2 transfer matrices are considered. It is shown that the transfer matrix of a symmetrical system, defined with respect to symmetrically oriented state variables, is involutory, and that a physically symmetrical system may not necessarily be functionally or dynamically symmetrical.

Transfer matrix modeling of hyperbolic and parabolic ducts with incompressible mean flow

A general differential equation for the propagation of sound in a variable area duct or nozzle carrying incompressible mean flow (of low Mach number) is derived and solved for hyperbolic and parabolic shapes. Expressions for the state variables of acoustic pressure and acoustic mass velocity of the shapes are derived. Self‐consistent expressions for the four‐pole parameters are developed. The conical, exponential, catenoidal, sine, and cosine ducts are shown to be special cases of hyperbolic ducts. Finally, it is shown that if the mean flow in computing the transmission loss of the mufflers involving hyperbolic and parabolic shapes was not neglected, little practical benefit would be derived.

Formulas for algorithmic computation of impedance matrix using general circuit constants

A set of formulas is derived from general circuit constants which facilitates formation of the impedance matrix of a power system by the bus-impedance method. The errors associated with the lumpedparameter representation of a transmission line are thereby eliminated. The formulas are valid for short lines also, if the relevant general circuit constants are employed. The mutual impedance between the added line and the existing system is not considered, but the approach suggested can well be extended to it.

Matrix Processors Using p-adic Arithmetic for Exact Linear Computations

A unique code (called Hensel's code) is derived for a rational number by truncating its infinite p-adic expansion. The four basic arithmetic algorithms for these codes are described and their application to rational matrix computations is demonstrated by solving a system of linear equations exactly, using the Gaussian elimination procedure.

Relaxation: Application to the matrix reconstruction problem

This report describes some preliminary experiments on the use of the relaxation technique for the reconstruction of the elements of a matrix given their various directional sums (or projections).

Effect of dimerization on dynamics of spin-charge separation in Pariser-Parr-Pople model: A time-dependent density matrix renormalization group study

We investigate the effect of static electron-phonon coupling on real-time dynamics of spin and charge transport in pi-conjugated polyene chains. The polyene chain is modeled by the Pariser-Parr-Pople Hamiltonian with dimerized nearest-neighbor parameter t(0)(1 + delta) for short bonds and t(0)(1 - delta) for long bonds, and long-range electron-electron interactions. We follow the time evolution of the spin and charge using time-dependent density matrix renormalization group technique when a hole is injected at one end of the chain in its ground state. We find that spin and charge dynamics followed through spin and charge velocities depend both on chain length and extent of dimerization delta. Analysis of the results requires focusing on physical quantities such as average spin and charge polarizations, particularly in the large dimerization limit. In the dimerization range 0.0 <= delta <= 0.15, spin-charge dynamics is found to have a well-defined behavior, with spin-charge separation (measured as the ratio of charge velocity to spin velocity) as well as the total amount of charge and spin transported in a given time along the chain decreasing as dimerization increases. However, in the range 0.3 <= delta <= 0.5, it is observed that the dynamics of spin and charge transport becomes complicated. It is observed that, for large delta values, spin-charge separation is suppressed and the injected hole fails to travel the entire length of the chain.

3D Acoustic Analysis Of Spherical Chamber Having Single Inlet And Multiple Outlet: An Impedance Matrix Approach

The transmission loss (TL) performance of spherical chambers having single inlet and multiple outlet is obtained analytically through modal expansion of acoustic field inside the spherical cavity in terms of the spherical Bessel functions and Legendre polynomials. The uniform piston driven model based upon the impedance [Z] matrix is used to characterize the multi-port spherical chamber. It is shown analytically that the [Z] parameters are independent of the azimuthal angle (phi) due to the axisymmetric shape of the sphere; rather, they depend only upon the polar angle (theta) and radius of the chamber R(0). Thus, the effects of relative polar angular location of the ports and number of outlet ports are investigated. The analytical results are shown to be in good agreement with the 3D FEA results, thereby validating the procedure suggested in this work.

A density matrix renormalization group method study of optical properties of porphines and metalloporphines

The symmetrized density matrix renormalization group method is used to study linear and nonlinear optical properties of free base porphine and metalloporphine. Long-range interacting model, namely, Pariser-Parr-Pople model is employed to capture the quantum many-body effect in these systems. The nonlinear optical coefficients are computed within the correction vector method. The computed singlet and triplet low-lying excited state energies and their charge densities are in excellent agreement with experimental as well as many other theoretical results. The rearrangement of the charge density at carbon and nitrogen sites, on excitation, is discussed. From our bond order calculation, we conclude that porphine is well described by the 18-annulenic structure in the ground state and the molecule expands upon excitation. We have modeled the regular metalloporphine by taking an effective electric field due to the metal ion and computed the excitation spectrum. Metalloporphines have D(4h) symmetry and hence have more degenerate excited states. The ground state of metalloporphines shows 20-annulenic structure, as the charge on the metal ion increases. The linear polarizability seems to increase with the charge initially and then saturates. The same trend is observed in third order polarizability coefficients. (C) 2012 American Institute of Physics. [doi: 10.1063/1.3671946]