Multi-step methods are essentially one-step methods

Summary In this note the geometry of multi-step methods is studied using invariant manifold theory for maps, as familiar from dynamical systems theory. This permits to associate a one-step method to each multi-step method to which the former is not only equivalent asymptotically, but equal in each step if the one-step method is used to produce the initial data of the multi-step method.     

Numerical methods

In this work, we construct explicit travelling wave solutions involving parameters of the Drinfel’d–Sokolov–Wilson equation as

Apportionment methods

Most democratic countries use apportionment methods to transform election results into whole numbers, which usually give the number of seats in a legislative body that the parties obtained. Which apportionment method does this best can be specified by measuring the error between the allocated result and the ideal proportion. We show how to find an apportionment method which is best suited to a given error function. We also discuss several properties of apportionment methods that have been labelled paradoxa. In particular we explain the highly publicised “Alabama” Paradox for the Hare/Hamilton method and show that other popular apportionment methods come with their very own paradoxa.     

Probabilistic methods

An overview of the “probabilistic method” in Combinatorial Analysis and Graph Theory is given.     

Stochastic global optimization methods part I: Clustering methods

In this stochastic approach to global optimization, clustering techniques are applied to identify local minima of a real valued objective function that are potentially global. Three different methods of this type are described; their accuracy and efficiency are analyzed in detail.     

Stabilization of algebraic multilevel iteration methods; additive methods

There exist two main versions of preconditioners of algebraic multilevel type, the additive and the multiplicative methods. They correspond to preconditioners in block diagonal and block matrix factorized form, respectively. Both can be defined and analysed as recursive two-by-two block methods. Although the analytical framework for such methods is simple, for many finite element approximations it still permits the derivation of the strongest results, such as optimal, or nearly optimal, rate of convergence and optimal, or nearly optimal order of computational complexity, when proper recursive global orderings of node points have been used or when they are applied for hierarchical basis function finite element methods for elliptic self-adjoint equations and stabilized in a certain way. This holds for general elliptic problems of second order, independent of the regularity of the problem, including independence of discontinuities of coefficients between elements and of anisotropy. Important ingredients in the methods are a proper balance of the size of the coarse mesh to the finest mesh and a proper solver on the coarse mesh. This paper presents in a survey form the basic results of such methods and considers in particular additive methods. This method has excellent parallelization properties. This revised version was published online in June 2006 with corrections to the Cover Date.     

Diagonalized multiplier methods and quasi-Newton methods for constrained optimization

Two approaches to quasi-Newton methods for constrained optimization problems inR ⁿ are presented. These approaches are based on a class of Lagrange multiplier approximation formulas used by the author in his previous work on Newton's method for constrained problems. The first approach is set in the framework of a diagonalized multiplier method. From this point of view, a new update rule for the Lagrange multipliers which depends on the particular quasi-Newton method employed is given. This update rule, in contrast to most other update rules, does not require exact minimization of the intermediate unconstrained problem. In fact, the optimal convergence rate is attained in the extreme case when only one step of a quasi-Newton method is taken on this intermediate problem. The second approach transforms the constrained optimization problem into an unconstrained problem of the same dimension.The author would like to thank J. Moré and M. J. D. Powell for comments related to the material in Section 13. He also thanks J. Nocedal for the computer results in Tables 1–3 and M. Wright for the results in Table 4, which were obtained via one of her general programs. Discussions with M. R. Hestenes and A. Miele regarding their contributions to this area were very helpful. Many individuals, including J. E. Dennis, made useful general comments at various stages of this paper. Finally, the author is particularly thankful to R. Byrd, M. Heath, and R. McCord for reading the paper in detail and suggesting many improvements.This work was supported by the Energy Research and Development Administration, Contract No. E-(40-1)-5046, and was performed in part while the author was visiting the Department of Operations Research, Stanford University, Stanford, California.     

On preconditioned Uzawa methods and SOR methods for saddle-point problems

This paper studies convergence analysis of a preconditioned inexact Uzawa method for nondifferentiable saddle-point problems. The SOR-Newton method and the SOR-BFGS method are special cases of this method. We relax the Bramble-Pasciak-Vassilev condition on preconditioners for convergence of the inexact Uzawa method for linear saddle-point problems. The relaxed condition is used to determine the relaxation parameters in the SOR-Newton method and the SOR-BFGS method. Furthermore, we study global convergence of the multistep inexact Uzawa method for nondifferentiable saddle-point problems.     

Stochastic global optimization methods part II: Multi level methods

In Part II of our paper, two stochastic methods for global optimization are described that, with probability 1, find all relevant local minima of the objective function with the smallest possible number of local searches. The computational performance of these methods is examined both analytically and empirically.     

Extrapolation methods to compute hypersingular integral in boundary element methods

The composite trapezoidal rule for the computation of Hadamard finite-part integrals in boundary element methods with the hypersingular kernel 1/sin 2(x-s) is discussed,and the main part of the asymptotic expansion of error function is obtained.Based on the main part of the asymptotic expansion,a series is constructed to approach the singular point.An extrapolation algorithm is presented and the convergence rate is proved.Some numerical results are also presented to confirm the theoretical results and show the efficiency of the algorithms.     

自适应间断Galerkin 有限元的多水平方法

本文讨论在自适应网格上间断Galerkin 有限元离散系统的局部多水平算法. 对于光滑系数和间断系数情形, 利用Schwarz 理论分析了算法的收敛性. 理论和数值试验均说明算法的收敛率与网格层数以及网格尺寸无关. 对强间断系数情形算法是拟最优的, 即收敛率仅与网格层数有关.     

Modern factorization methods

In this expository paper the progress in factorization of large integers since the introduction of computers is reported. Thanks to theoretical advances and refinements, as well as to more powerful computers, the practical limit of integers possible to factor has been raised considerably during the past 20 years. The present practical limit is around 10⁷⁵ if supercomputers are used and if much computer time is available.     

Multihomogeneous Newton methods

We study multihomogeneous analytic functions and a multihomogeneous Newton's method for finding their zeros. We give a convergence result for this iteration and we study two examples: the evaluation map and the generalized eigenvalue problem.

     

Autoregressive-output-analysis methods revisited

We revisit and update the autoregressive-output-analysis method for constructing a confidence interval for the steady-state mean of a simulated process by using Rissanen's predictive least-squares criterion to estimate the autoregressive order of the process. This order estimator is strongly consistent when the output is autoregressive. The order estimator is combined with the standard autoregressive-output-analysis method to form a confidence-interval procedure. Alternatives for estimating the degrees of freedom for the procedure are investigated. The main result is an asymptotically valid confidence-interval procedure that, empirically, has good small-sample properties.     

Canonical Runge-Kutta methods

Summary In the present note we provide a complete characterization of all Runge-Kutta methods which generate a canonical transformation if applied to a Hamiltonian system of ordinary differential equations.     

Multilevel Schwarz methods

Summary We consider the solution of the algebraic system of equations which result from the discretization of second order elliptic equations. A class of multilevel algorithms are studied using the additive Schwarz framework. We establish that the condition number of the iteration operators are bounded independent of mesh sizes and the number of levels. This is an improvement on Dryja and Widlund's result on a multilevel additive Schwarz algorithm, as well as Bramble, Pasciak and Xu's result on the BPX algorithm. Some multiplicative variants of the multilevel methods are also considered. We establish that the energy norms of the corresponding iteration operators are bounded by a constant less than one, which is independent of the number of levels. For a proper ordering, the iteration operators correspond to the error propagation operators of certain V-cycle multigrid methods, using Gauss-Seidel and damped Jacobi methods as smoothers, respectively.This work was supported in part by the National Science Foundation under Grants NSF-CCR-8903003 at Courant Institute of Mathematical Sciences, New York University and NSF-ASC-8958544 at Department of Computer Science, University of Maryland.     

Renormalization group methods

An especially intractable breed of problems in physics involves those with very many or an infinite number of degrees of freedom and in addition involve “renormalization.” Renormalization is explained as the existence of very many length or energy scales of importance in the physics of the problem. The renormalization group approach is a way of reducing the complexity of these problems to the point where numerical methods can be used to solve them. The Kondo problem (dilute magnetic alloys) is used as an illustration.