Economical cascadic multigrid method (ECMG)

In this paper,an economical cascadic multigrid method is proposed.Compared with the usual cascadic multigrid method developed by Bornemann and Deuflhard,the new one requires less iterations on each level,especially on the coarser grids.Many operations can be saved in the new cascadic multigrid algorithms.The main ingredient is the control of the iteration numbers on the each level to preserve the accuracy without over iterations.The theoretical justification is based on the observations that the error reduction rate of an iteration scheme in terms of the smoothing property is no longer accurate while the iteration number is big enough.A new formulae of the error reduction rate is employed in our new algorithm.Numerical experiments are reported to support our theory.     

菲波纳奇数列在常微分方程外推方法中的应用

§1.引言 Deuflhard在关于常微分方程外推方法的综合报告[1]中认为“在早期的论文中,外推表依可用于无限排列(按两个下标)的想法加以分析:在数列?的Toeplitz条件     

A metaheuristic methodology based on the limitation of the memory of interval branch and bound algorithms

Branch and Bound Algorithms based on Interval Arithmetic permit to solve exactly continuous (as well as mixed) non-linear and non-convex global optimization problems. However, their intrinsic exponential time-complexities do not make it possible to solve some quite large problems. The idea proposed in this paper is to limit the memory available during the computations of such a global optimization code in order to find some efficient feasible solutions. By this way, we introduce a metaheuristic frame to develop some new heuristic global optimization algorithms based on an exact code. We show in this paper, with a small assumption about the sorting by breadth first of elements in the data structure, that the time-complexity of such metaheuristic algorithms becomes polynomial instead of exponential for the exact code. In order to validate our metaheuristic approach, some numerical experiments about constrained global optimization problems coming from the COCONUT library were solved using a heuristic which certifies an enclosure of the global minimum value. The objective is not to solve completely the problem or find a better solution, but it is to know what is the highest precision which can be guaranteed reliably with the available memory.     

Automatic solution of regular and singular vector Sturm-Liouville problems

This paper describes the algorithms and theory behind a new code for vector Sturm-Liouville problems. A new spectral function is defined for vector Sturm-Liouville problems; this is an integer valued function of the eigenparameter which has discontinuities precisely at the eigenvalues. We describe numerical algorithms which may be used to compute the new spectral function, and its use as amiss-distance function in a new code which solves automatically a large class of regular and singular vector Sturm-Liouville problems. Vector Sturm-Liouville problems arise naturally in quantum mechanical applications. Usually they are singular. The advantages of the author's code lie in its ability to solve singular problems automatically, and in the fact that the user may specify the required eigenvalue by its index.     

On the solution of highly structured nonlinear equations

We introduce a quasi-Newton update for nonlinear equations which have a Jacobian with sparse triangular factors and consider its application, through an algorithm of Deuflhard, to the solution of boundary value problems by multiple shooting.     

On Newton-like methods of ��bounded deterioration�� using recurrent functions

We provide a semilocal convergence analysis for Newton-like methods of ??bounded deterioration?? in a Banach space setting. We establish tighter error bounds on the distances involved, and a more precise information on the location of the solution, under the same or weaker hypotheses than before (Argyros, Acta Math. Sin. (Engl. Ser.), 23:2087?C2096, 2007; Deuflhard, Newton methods for nonlinear problems. Affine invariance and adaptive algorithms, Springer Series in Computational Mathematics, vol. 35. Springer, Berlin, 2004; Ezquerro and Hern??ndez, IMA J. Numer. Anal., 22:187?C205, 2002) using recurrent functions. Numerical examples are also provided involving polynomial, integral, and differential equations.     

$${\tt surveillance}$$: An R package for the monitoring of infectious diseases

Public health surveillance of emerging infectious diseases is an essential instrument in the attempt to control and prevent their spread. This paper presents the R package “surveillance”, which contains functionality to visualise routinely collected surveillance data and provides algorithms for the statistical detection of aberrations in such univariate or multivariate time series. For evaluation purposes, the package includes real-world example data and the possibility to generate surveillance data by simulation. To compare algorithms, benchmark numbers like sensitivity, specificity, and detection delay can be computed for a set of time series. Package motivation, use and potential are illustrated through a mixture of surveillance theory, case study and R code snippets.     

A simple SLP algorithm for solving a class of nonlinear programs

Successive linear programming (SLP) algorithms solve nonlinear optimization problems via a sequence of linear programs. We present an approach for a special class of nonlinear programming problems, which arise in multiperiod coal blending. The class of nonlinear programming problems and the solution approach considered in this paper are quite different from previous work. The algorithm is very simple, easy to apply and can be applied to as large a problem as the linear programming code can handle. The quality of solution, produced by the proposed algorithm, is discussed and the results of some test problems, in the real world environment, are provided.     

Improved decoding of affine-variety codes

General error locator polynomials are polynomials able to decode any correctable syndrome for a given linear code. Such polynomials are known to exist for all cyclic codes and for a large class of linear codes. We provide some decoding techniques for affine-variety codes using some multidimensional extensions of general error locator polynomials. We prove the existence of such polynomials for any correctable affine-variety code and hence for any linear code. We propose two main different approaches, that depend on the underlying geometry. We compute some interesting cases, including Hermitian codes. To prove our coding theory results, we develop a theory for special classes of zero-dimensional ideals, that can be considered generalizations of stratified ideals. Our improvement with respect to stratified ideals is twofold: we generalize from one variable to many variables and we introduce points with multiplicities.     

模拟化学反应系统的快速无偏τ-Leap算法

化学反应系统中的Leap算法可在获得较好精度的同时大幅提高模拟速度.最近提出的无偏Leap方法有效地克服了由Leap时间区间内的反应次数的近似均值与真实均值之间的偏差引起的Leap算法的误差的不足.本文讨论了一个基于物种相对改变估计真实均值的快速无偏T-Leap算法,并将该算法推广到模拟时滞化学系统中.该快速算法具有易于编码、比前者更快等优点.当系统中的反应通道或物种的数目较大时,该方法具有更明显的速度优势.     

Entropy-based evaluation function in a multi-objective approach for the investigation of the genetic code robustness

The genetic code is the interface between the genetic information stored in DNA molecules and the proteins. Considering the hypothesis that the genetic code evolved to its current structure, some researches use optimization algorithms to find hypothetical codes to be compared to the canonical genetic code. For this purpose, a function with only one objective is employed to evaluate the codes, generally a function based on the robustness of the code against mutations. Very few random codes are better than the canonical genetic code when the evaluation function based on robustness is considered. However, most codons are associated with a few amino acids in the best hypothetical codes when only robustness is employed to evaluate the codes, what makes hard to believe that the genetic code evolved based on only one objective, i.e., the robustness against mutations. In this way, we propose here to use entropy as a second objective for the evaluation of the codes. We propose a Pareto approach to deal with both objectives. The results indicate that the Pareto approach generates codes closer to the canonical genetic code when compared to the codes generated by the approach with only one objective employed in the literature.     

The New Minimum Distance Bounds of Goppa Codes and Their Decoding

A couple of new lower bounds of the minimum distance of Goppa codes is derived, using an extended field code for a Goppa code which contains the Goppa code as its subfield-subcode. Also presented are procedures for both error-only and error-and-erasure decoding for Goppa codes up to the new lower bounds, based on the Berlekamp-Massey algorithm and the Feng-Tzeng multisequence shift-register synthesis algorithms which have been used for decoding cyclic codes up to the BCH and HT(Hartmann-Tzeng) bounds.     

On Reed-Solomon Codes

The complexity of decoding the standard Reed-Solomon code is a well-known open problem in coding theory. The main problem is to compute the error distance of a received word. Using the Weil bound for character sum estimate, Li and Wan showed that the error distance can be determined when the degree of the received word as a polynomial is small. In the first part, the result of Li and Wan is improved. On the other hand, one of the important parameters of an error-correcting code is the dimension. In most cases, one can only get bounds for the dimension. In the second part, a formula for the dimension of the generalized trace Reed-Solomon codes in some cases is obtained.     

A convergence theory for a class of anti-jamming strategies

A convergence theory for a class of anti-jamming strategies for nonlinear programming algorithms is presented. This theory generalizes previous results in this area by Zoutendijk, Topkis and Veinott, Mangasarian, and others; it is applicable to algorithms in which the anti-jamming parameter is fixed at some positive value as well as to algorithms in which it tends to zero. In addition, under relatively weak hypotheses, convergence of the entire sequence of iterates is proved.This research was sponsored by the United States Army under Contract No. DA-31-124-ARO-D-462.     

Computing Mixed Volume and All Mixed Cells in Quermassintegral Time

The mixed volume counts the roots of generic sparse polynomial systems. Mixed cells are used to provide starting systems for homotopy algorithms that can find all those roots and track no unnecessary path. Up to now, algorithms for that task were of enumerative type, with no general non-exponential complexity bound. A geometric algorithm is introduced in this paper. Its complexity is bounded in the average and probability-one settings in terms of some geometric invariants: quermassintegrals associated with the tuple of convex hulls of the support of each polynomial. Besides the complexity bounds, numerical results are reported. Those are consistent with an output-sensitive running time for each benchmark family where data are available. For some of those families, an asymptotic running time gain over the best code available at this time was noticed.     

Elementary landscape decomposition of the 0-1 unconstrained quadratic optimization

Landscapes’ theory provides a formal framework in which combinatorial optimization problems can be theoretically characterized as a sum of an especial kind of landscape called elementary landscape. The elementary landscape decomposition of a combinatorial optimization problem is a useful tool for understanding the problem. Such decomposition provides an additional knowledge on the problem that can be exploited to explain the behavior of some existing algorithms when they are applied to the problem or to create new search methods for the problem. In this paper we analyze the 0-1 Unconstrained Quadratic Optimization from the point of view of landscapes’ theory. We prove that the problem can be written as the sum of two elementary components and we give the exact expressions for these components. We use the landscape decomposition to compute autocorrelation measures of the problem, and show some practical applications of the decomposition.     

Subquadrature expansions for TSRK methods

The representation of order conditions for general linear methods formulated using an algebraic theory by Butcher, and the alternative using B-series by Hairer and Wanner for treating vector initial value problems in ordinary differential equations are well-known. Each relies on a recursion over rooted trees; yet tractable forms—for example, those which may be solved to yield particular methods—often are obtained only after extensive computation. In contrast, for Runge–Kutta methods, tractable forms have been used by various authors for obtaining methods. Here, the corresponding recursion formula for two-step Runge–Kutta methods is revised to yield tractable forms which may be exploited to derive such methods and to motivate the selection of efficient algorithms in an obvious way. The new recursion formula is utilized in a MAPLE code.     

Comparative computer results of a new complementary pivot algorithm for solving equality and inequality constrained optimization problems

This paper reports the development of a new algorithm for solving the general constrained optimization problem (that of optimizing an objective function subject to both equality and inequality constraints). The approach is based on the complementary pivoting algorithms which have been developed to solve certain classes of fixed point problems. The specific approach is to use the equality constraints to solve for some variables in terms of the remaining ones thus enabling one to eliminate the equality constraints altogether. The result, under certain circumstances, is an optimization problem which may be transformed into a fixed point problem in such a way that a complementary pivoting code may be used to search for a solution.Seventeen test problems have been solved by this method and the results are compared against those obtained from GRG (Generalized Reduced Gradient method). The results of the tests indicate that the fixed point approach is robust (all 17 problems were solved by this method where as GRG solved 16). As to the computer times, the fixed point code proved to be as fast or faster than GRG on the lower dimensional problems; however, as the dimension increased, the trend reversed and on a 40 dimensional problem GRG was approximately 11 times faster. The conclusion from these tests is that when the dimension of the original problem can be reduced sufficiently by the equality constraints, the fixed point approach appears to be more effective than GRG.     

An approach to evolving novel organizational forms

A key problem in organization theory is to suggest new organizational forms. In this paper, I suggest the use of genetic algorithms to search for novel organizational forms by reproducing some of the mechanics of organizational evolution. Issues in using genetic algorithms include identification of the unit of selection, development of a representation and determination of a method for calculating organizational fitness. As an example of the approach, I test a proposition of Thompson's about how interdependent positions should be assigned to groups. Representing an organization as a collection of routines might be more general and still amenable to evolution with a genetic algorithm. I conclude by discussing possible objections to the application of this technique.Syracuse University School of Information Studies