Approximate minimum-cost multicommodity flows in\tilde O(ɛ −2 KNM) timetime

We show that an ε-approximate solution of the cost-constrainedK-commodity flow problem on anN-nodeM-arc network,G can be computed by sequentially solving O(K(? ^?2+logGK) logGM log (G? ^?1 GK)) single-commodity minimum-cost flow problems on the same network. In particular, an approximate minimum-cost multicommodity flow can be computed in $\tilde O$ (G? ^?2 GKNM) running time, where the notation Õ(·) means “up to logarithmic factors”. This result improves the time bound mentioned by Grigoriadis and Khachiyan [4] by a factor ofM/N and that developed more recently by Karger and Plotkin [8] by a factor of? ^?1. We also provide a simple $\tilde O$ (NM)-time algorithm for single-commodity budget-constrained minimum-cost flows which is $\tilde O$ (? ^?3) times faster than the algorithm developed in the latter paper.     

Asymptotic behavior of eigenvalues and random updating schemes

For a stochastic matrix (Q _ij ^T ) _i,j=1 ^M withQ _ij ^T exp(–U(ij)/T) at the off-diagonal positions, we develop an algorithm to evaluate the asymptotic convergence rate of all eigenvalues ofQ _ij ^T asT 0 using Ventcel's optimal graphs. As an application we can compare the convergence rates of some random updating schemes used in image processing.This research was partially supported by the National Science Council, Taiwan and Air Force Office of Scientific Research Contract No. F49620 S5C 0144, and was completed while Tzuu-Shuh Chiang was visiting the Center for Stochastic Processes, Department of Statistics, University of North Carolina, Chapel Hill, NC 27599-3260, USA.     

Constrained minimax approximation and optimal preconditioned for Toeplitz matrices

A good preconditioner is extremely important in order for the conjugate gradients method to converge quickly. In the case of Toeplitz matrices, a number of recent studies were made to relate approximation of functions to good preconditioners. In this paper, we present a new result relating the quality of the Toeplitz preconditionerC for the Toeplitz matrixT to the Chebyshev norm (f– g)/f, wheref and g are the generating functions forT andC, respectively. In particular, the construction of band-Toeplitz preconditioners becomes a linear minimax approximation problem. The case whenf has zeros (but is nonnegative) is especially interesting and the corresponding approximation problem becomes constrained. We show how the Remez algorithm can be modified to handle the constraints. Numerical experiments confirming the theoretical results are presented.     

New Monte Carlo method for the self-avoiding walk

We introduce a new Monte Carlo algorithm for the self-avoiding walk (SAW), and show that it is particularly efficient in the critical region (long chains). We also introduce new and more efficient statistical techniques. We employ these methods to extract numerical estimates for the critical parameters of the SAW on the square lattice. We find=2.63820 ± 0.00004 ± 0.00030=1.352 ± 0.006 ± 0.025v=0.7590 ± 0.0062 ± 0.0042 where the first error bar represents systematic error due to corrections to scaling (subjective 95% confidence limits) and the second bar represents statistical error (classical 95% confidence limits). These results are based on SAWs of average length 166, using 340 hours CPU time on a CDC Cyber 170–730. We compare our results to previous work and indicate some directions for future research.     

Nonstationary Markov chains and convergence of the annealing algorithm

We study the asymptotic behavior as timet + of certain nonstationary Markov chains, and prove the convergence of the annealing algorithm in Monte Carlo simulations. We find that in the limitt + , a nonstationary Markov chain may exhibit phase transitions. Nonstationary Markov chains in general, and the annealing algorithm in particular, lead to biased estimators for the expectation values of the process. We compute the leading terms in the bias and the variance of the sample-means estimator. We find that the annealing algorithm converges if the temperatureT(t) goes to zero no faster thanC/log(t/t ₀) ast+, with a computable constantC andt ₀ the initial time. The bias and the variance of the sample-means estimator in the annealing algorithm go to zero likeO(t^–1+) for some 0<1, with =0 only in very special circumstances. Our results concerning the convergence of the annealing algorithm, and the rate of convergence to zero of the bias and the variance of the sample-means estimator, provide a rigorous procedure for choosing the optimal annealing schedule. This optimal choice reflects the competition between two physical effects: (a) The adiabatic effect, whereby if the temperature is loweredtoo abruptly the system may end up not in a ground state but in a nearby metastable state, and (b) the super-cooling effect, whereby if the temperature is loweredtoo slowly the system will indeed approach the ground state(s) but may do so extremely slowly.     

Aligning Text and Phonemes for Speech Technology Applications Using an EM-Like Algorithm

A common requirement in speech technology is to align two different symbolic representations of the same linguistic ‘message’. For instance, we often need to align letters of words listed in a dictionary with the corresponding phonemes specifying their pronunciation. As dictionaries become ever bigger, manual alignment becomes less and less tenable yet automatic alignment is a hard problem for a language like English. In this paper, we describe the use of a form of the expectation-maximization (EM) algorithm to learn alignments of English text and phonemes, starting from a variety of initializations. We use the British English Example Pronunciation (BEEP) dictionary of almost 200,000 words in this work. The quality of alignment is difficult to determine quantitatively since no ‘gold standard’ correct alignment exists. We evaluate the success of our algorithm indirectly from the performance of a pronunciation by analogy system using the aligned dictionary data as a knowledge base for inferring pronunciations. We find excellent performance—the best so far reported in the literature. There is very little dependence on the start point for alignment, indicating that the EM search space is strongly convex. Since the aligned BEEP dictionary is a potentially valuable resource, it is made freely available for research use.     

Numerical comparison of several variable-metric algorithms

The paper compares the numerical performances of the LDL decomposition of the BFGS variable-metric algorithm, the Dennis-Mei dogleg algorithm on the BFGS update, and Davidon's projections with the BFGS update with the straight BFGS update on a number of standard test problems. Numerical results indicate that the standard BFGS algorithm is superior to all of the more complex strategies.This research was supported by the National Science Foundation under Research Grant No. MCS77-07327.     

Quantitative determination of Malathion in pesticide by modified attenuated total reflectance-Fourier transform infrared spectrometry applying genetic algorithm wavelength selection method

A simple and environment friendly method was developed for determination of Malathion content of analytical and commercial insecticide samples with no special preparation. Attenuated total reflectance-Fourier transform infrared (ATR-FTIR) spectra were characterized and 1000-2000 cm⁻¹ region was selected for quantitative analysis utilizing partial least square (PLS) and two wavelength selection methods: (a) principal component regression (PCR) and (b) genetic algorithm (GA). Relative error of prediction (REP) was calculated in PLS, PCR-PLS and GA-PLS methods and was 3.536, 1.656 and 0.188, respectively. Proposed method is successfully applicable for quantification of Malathion in commercial grade samples and reliable results in comparison with known methods, confirms this idea.     

The Enhancement of Efficiency of High-order Harmonic in Intense Laser Field Based on Asymptotic Boundary Conditions and Symplectic Algorithm

Asymptotic boundary condition (ABC) of laser-atom interaction presented recently is applied to transform the initial value problem of the time-dependent Schrödinger equation (TDSE) in infinite space into the initial and boundary value problem in the finite space, and then the TDSE is discretized into linear canonical equations by substituting the symmetry difference quotient for the 2-order partial derivative. The canonical equation is solved by symplectic algorithm. The ground state and the equal weight coherent superposition of the ground state and the first excited state have been taken as the initial conditions, respectively, while we calculate the population of bound states, the evolution of average distance and the high-order harmonic generation (HHG). The conversion efficiency of HHG can be enhanced by initial coherent superposition state and moderate laser intensities