Adaptive filtering

Summary. In this paper, the adaptive filtering method is introduced and analysed. This method leads to robust algorithms for the solution of systems of linear equations which arise from the discretisation of partial differential equations with strongly varying coefficients. These iterative algorithms are based on the tangential frequency filtering decompositions (TFFD). During the iteration with a preliminary preconditioner, the adaptive test vector method calculates new test vectors for the TFFD. The adaptive test vector iterative method allows the combination of the tangential frequency decomposition and other iterative methods such as multi-grid. The connection with the TFFD improves the robustness of these iterative methods with respect to varying coefficients. Interface problems as well as problems with stochastically distributed properties are considered. Realistic numerical experiments confirm the efficiency of the presented algorithms. Received June 26, 1996 / Revised version received October 7, 1996     

On the derivation of explicit two-step peer methods

The so-called two-step peer methods for the numerical solution of Initial Value Problems (IVP) in differential systems were introduced by R. Weiner, B.A. Schmitt and coworkers as a tool to solve different types of IVPs either in sequential or parallel computers. These methods combine the advantages of Runge-Kutta (RK) and multistep methods to obtain high stage order and therefore provide in a natural way a dense output. In particular, several explicit peer methods have been proved to be competitive with standard RK methods in a wide selection of non-stiff test problems.The aim of this paper is to propose an alternative procedure to construct families of explicit two step peer methods in which the available parameters appear in a transparent way. This allows us to obtain families of fixed stepsize s stage methods with stage order 2s−1, which provide dense output without extra cost, depending on some free parameters that can be selected taking into account the stability properties and leading error terms. A study of the extension of these methods to variable stepsize is also carried out. Optimal s stage methods with s=2,3 are derived.     

Extended phase properties and stability analysis of RKN-type integrators for solving general oscillatory second-order initial value problems

In this paper, we study in detail the phase properties and stability of numerical methods for general oscillatory second-order initial value problems whose right-hand side functions depend on both the position y and velocity y ^'. In order to analyze comprehensively the numerical stability of integrators for oscillatory systems, we introduce a novel linear test model y ^?(t) + ? ² y(t) + µ y ^'(t)=0 with µ<2?. Based on the new model, further discussions and analysis on the phase properties and stability of numerical methods are presented for general oscillatory problems. We give the new definitions of dispersion and dissipation which can be viewed as an essential extension of the traditional ones based on the linear test model y ^?(t) + ? ² y(t)=0. The numerical experiments are carried out, and the numerical results showthatthe analysisofphase properties and stability presentedinthispaper ismoresuitableforthenumericalmethodswhentheyareappliedtothe generaloscillatory second-order initial value problem involving both the position and velocity.     

A secant method for nonlinear least-squares minimization

Quasi-Newton methods have played a prominent role, over many years, in the design of effective practical methods for the numerical solution of nonlinear minimization problems and in multi-dimensional zero-finding. There is a wide literature outlining the properties of these methods and illustrating their performance (e.g., Dennis and Schnabel, Numerical Methods for Unconstrained Optimization and Nonlinear Equations, 1996). In addition, most modern optimization libraries house a quasi-Newton collection of codes and they are widely used. The quasi-Newton contribution to practical nonlinear optimization is unchallenged.     

Haruspicy and anisotropic generating functions

Guttmann and Enting [Phys. Rev. Lett. 76 (1996) 344–347] proposed the examination of anisotropic generating functions as a test of the solvability of models of bond animals. In this article we describe a technique for examining some properties of anisotropic generating functions. For a wide range of solved and unsolved families of bond animals, we show that the coefficients of yⁿ is rational, the degree of its numerator is at most that of its denominator, and the denominator is a product of cyclotomic polynomials. Further, we are able to find a multiplicative upper bound for these denominators which, by comparison with numerical studies [Jensen, personal communication; Jensen and Guttmann, personal communication], appears to be very tight. These facts can be used to greatly reduce the amount of computation required in generating series expansions. They also have strong and negative implications for the solvability of these problems.     

An improved approximate Newton method for implicit Runge-Kutta formulas

Implicit Runge-Kutta (IRK) methods (such as the s-stage Radau IIA method with s=3,5, or 7) for solving stiff ordinary differential equation systems have excellent stability properties and high solution accuracy orders, but their high computing costs in solving their nonlinear stage equations have seriously limited their applications to large scale problems. To reduce such a cost, several approximate Newton algorithms were developed, including a commonly used one called the simplified Newton method. In this paper, a new approximate Jacobian matrix and two new test rules for controlling the updating of approximate Jacobian matrices are proposed, yielding an improved approximate Newton method. Theoretical and numerical analysis show that the improved approximate Newton method can significantly improve the convergence and performance of the simplified Newton method.     

Mathematical programming approaches for generating p-efficient points

Probabilistically constrained problems, in which the random variables are finitely distributed, are non-convex in general and hard to solve. The p-efficiency concept has been widely used to develop efficient methods to solve such problems. Those methods require the generation of p-efficient points (pLEPs) and use an enumeration scheme to identify pLEPs. In this paper, we consider a random vector characterized by a finite set of scenarios and generate pLEPs by solving a mixed-integer programming (MIP) problem. We solve this computationally challenging MIP problem with a new mathematical programming framework. It involves solving a series of increasingly tighter outer approximations and employs, as algorithmic techniques, a bundle preprocessing method, strengthening valid inequalities, and a fixing strategy. The method is exact (resp., heuristic) and ensures the generation of pLEPs (resp., quasi pLEPs) if the fixing strategy is not (resp., is) employed, and it can be used to generate multiple pLEPs. To the best of our knowledge, generating a set of pLEPs using an optimization-based approach and developing effective methods for the application of the p-efficiency concept to the random variables described by a finite set of scenarios are novel. We present extensive numerical results that highlight the computational efficiency and effectiveness of the overall framework and of each of the specific algorithmic techniques.     

H-p clouds—an h-p meshless method

A new methodology to build discrete models of boundary-value problems is presented. The h-p cloud method is applicable to arbitrary domains and employs only a scattered set of nodes to build approximate solutions to BVPs. This new method uses radial basis functions of varying size of supports and with polynomial-reproducing properties of arbitrary order. The approximating properties of the h-p cloud functions are investigated in this article and several theorems concerning these properties are presented. Moving least squares interpolants are used to build a partition of unity on the domain of interest. These functions are then used to construct, at a very low cost, trial and test functions for Galerkin approximations. The method exhibits a very high rate of convergence and has a greater flexibility than traditional h-p finite element methods. Several numerical experiments in 1-D and 2-D are also presented. © 1996 John Wiley & Sons, Inc.     

One-leg variable-coefficient formulas for ordinary differential equations and local–global step size control

In this paper we discuss a class of numerical algorithms termed one-leg methods. This concept was introduced by Dahlquist in 1975 with the purpose of studying nonlinear stability properties of multistep methods for ordinary differential equations. Later, it was found out that these methods are themselves suitable for numerical integration because of good stability. Here, we investigate one-leg formulas on nonuniform grids. We prove that there exist zero-stable one-leg variable-coefficient methods at least up to order 11 and give examples of two-step methods of orders 2 and 3. In this paper we also develop local and global error estimation techniques for one-leg methods and implement them with the local–global step size selection suggested by Kulikov and Shindin in 1999. The goal of this error control is to obtain automatically numerical solutions for any reasonable accuracy set by the user. We show that the error control is more complicated in one-leg methods, especially when applied to stiff problems. Thus, we adapt our local–global step size selection strategy to one-leg methods.     

Multiple invariants conserving Runge-Kutta type methods for Hamiltonian problems

In a recent series of papers, the class of energy-conserving Runge-Kutta methods named Hamiltonian BVMs (HBVMs) has been defined and studied. Such methods have been further generalized for the efficient solution of general conservative problems, thus providing the class of Line Integral Methods (LIMs). In this paper we derive a further extension, which we name Enhanced Line Integral Methods (ELIMs), more tailored for Hamiltonian problems, allowing for the conservation of multiple invariants of the continuous dynamical system. The analysis of the methods is fully carried out and some numerical tests are reported, in order to confirm the theoretical achievements.     

Exact augmented Lagrangian functions for nonlinear semidefinite programming

In this paper, we study augmented Lagrangian functions for nonlinear semidefinite programming (NSDP) problems with exactness properties. The term exact is used in the sense that the penalty parameter can be taken appropriately, so a single minimization of the augmented Lagrangian recovers a solution of the original problem. This leads to reformulations of NSDP problems into unconstrained nonlinear programming ones. Here, we first establish a unified framework for constructing these exact functions, generalizing Di Pillo and Lucidi’s work from 1996, that was aimed at solving nonlinear programming problems. Then, through our framework, we propose a practical augmented Lagrangian function for NSDP, proving that it is continuously differentiable and exact under the so-called nondegeneracy condition. We also present some preliminary numerical experiments.     

Three-level schemes of the alternating triangular method

In this paper, the schemes of the alternating triangular method are set out in the class of splitting methods used for the approximate solution of Cauchy problems for evolutionary problems. These schemes are based on splitting the problem operator into two operators that are conjugate transposes of each other. Economical schemes for the numerical solution of boundary value problems for parabolic equations are designed on the basis of an explicit-implicit splitting of the problem operator. The alternating triangular method is also of interest for the construction of numerical algorithms that solve boundary value problems for systems of partial differential equations and vector systems. The conventional schemes of the alternating triangular method used for first-order evolutionary equations are two-level ones. The approximation properties of such splitting methods can be improved by transiting to three-level schemes. Their construction is based on a general principle for improving the properties of difference schemes, namely, on the regularization principle of A.A. Samarskii. The analysis conducted in this paper is based on the general stability (or correctness) theory of operator-difference schemes.     

A further study on inverse linear programming problems

In this paper we continue our previous study (Zhang and Liu, J. Comput. Appl. Math. 72 (1996) 261–273) on inverse linear programming problems which requires us to adjust the cost coefficients of a given LP problem as less as possible so that a known feasible solution becomes the optimal one. In particular, we consider the cases in which the given feasible solution and one optimal solution of the LP problem are 0–1 vectors which often occur in network programming and combinatorial optimization, and give very simple methods for solving this type of inverse LP problems. Besides, instead of the commonly used l₁ measure, we also consider the inverse LP problems under l_∞ measure and propose solution methods.     

Global Convergence of a Memory Gradient Method for Unconstrained Optimization

Memory gradient methods are used for unconstrained optimization, especially large scale problems. The first idea of memory gradient methods was proposed by Miele and Cantrell (1969) and Cragg and Levy (1969). In this paper, we present a new memory gradient method which generates a descent search direction for the objective function at every iteration. We show that our method converges globally to the solution if the Wolfe conditions are satisfied within the framework of the line search strategy. Our numerical results show that the proposed method is efficient for given standard test problems if we choose a good parameter included in the method.     

New efficient numerical procedures for solving stochastic variational problems with a priori maximum pointwise error estimates

In a previous paper we gave a new formulation and derived the Euler equations and other necessary conditions to solve strong, pathwise, stochastic variational problems with trajectories driven by Brownian motion. Thus, unlike current methods which minimize the control over deterministic functionals (the expected value), we find the control which gives the critical point solution of random functionals of a Brownian path and then, if we choose, find the expected value.This increase in information is balanced by the fact that our methods are anticipative while current methods are not. However, our methods are more directly connected to the theory and meaningful examples of deterministic variational theory and provide better means of solution for free and constrained problems. In addition, examples indicate that there are methods to obtain nonanticipative solutions from our equations although the anticipative optimal cost function has smaller expected value.In this paper we give new, efficient numerical methods to find the solution of these problems in the quadratic case. Of interest is that our numerical solution has a maximal, a priori, pointwise error of O(h3/2) where h is the node size. We believe our results are unique for any theory of stochastic control and that our methods of proof involve new and sophisticated ideas for strong solutions which extend previous deterministic results by the first author where the error was O(h²).We note that, although our solutions are given in terms of stochastic differential equations, we are not using the now standard numerical methods for stochastic differential equations. Instead we find an approximation to the critical point solution of the variational problem using relations derived from setting to zero the directional derivative of the cost functional in the direction of simple test functions.Our results are even more significant than they first appear because we can reformulate stochastic control problems or constrained calculus of variations problems in the unconstrained, stochastic calculus of variations formulation of this paper. This will allow us to find efficient and accurate numerical solutions for general constrained, stochastic optimization problems. This is not yet being done, even in the deterministic case, except by the first author.     

A parameter-free stabilized finite element method for scalar advection-diffusion problems

We formulate and study numerically a new, parameter-free stabilized finite element method for advection-diffusion problems. Using properties of compatible finite element spaces we establish connection between nodal diffusive fluxes and one-dimensional diffusion equations on the edges of the mesh. To define the stabilized method we extend this relationship to the advection-diffusion case by solving simplified one-dimensional versions of the governing equations on the edges. Then we use H(curl)-conforming edge elements to expand the resulting edge fluxes into an exponentially fitted flux field inside each element. Substitution of the nodal flux by this new flux completes the formulation of the method. Utilization of edge elements to define the numerical flux and the lack of stabilization parameters differentiate our approach from other stabilized methods. Numerical studies with representative advection-diffusion test problems confirm the excellent stability and robustness of the new method. In particular, the results show minimal overshoots and undershoots for both internal and boundary layers on uniform and non-uniform grids.     

Matching-based preprocessing algorithms to the solution of saddle-point problems in large-scale nonconvex interior-point optimization

Interior-point methods are among the most efficient approaches for solving large-scale nonlinear programming problems. At the core of these methods, highly ill-conditioned symmetric saddle-point problems have to be solved. We present combinatorial methods to preprocess these matrices in order to establish more favorable numerical properties for the subsequent factorization. Our approach is based on symmetric weighted matchings and is used in a sparse direct LDL ^T factorization method where the pivoting is restricted to static supernode data structures. In addition, we will dynamically expand the supernode data structure in cases where additional fill-in helps to select better numerical pivot elements. This technique can be seen as an alternative to the more traditional threshold pivoting techniques. We demonstrate the competitiveness of this approach within an interior-point method on a large set of test problems from the CUTE and COPS sets, as well as large optimal control problems based on partial differential equations. The largest nonlinear optimization problem solved has more than 12 million variables and 6 million constraints.     

A new stepsize strategy for explicit Runge-Kutta codes

When the stepsize in Runge-Kutta codes is restricted by stability, an uneven pattern of stepsizes with many step rejections is frequently observed. A modified strategy is proposed to smooth out this type of behaviour. Several new estimates for the dominant eigenvalue of the Jacobian are derived. It is shown that such estimates can be used, in a strictly controlled way, to improve the stepsize strategy. Some numerical evidence is presented to show that the modified strategy is effective on a set of widely used test problems.     

On the asymptotic stability properties of Runge-Kutta methods for delay differential equations

Summary. In this paper asymptotic stability properties of Runge-Kutta (R-K) methods for delay differential equations (DDEs) are considered with respect to the following test equation: where and is a continuous real-valued function. In the last few years, stability properties of R-K methods applied to DDEs have been studied by numerous authors who have considered regions of asymptotic stability for “any positive delay” (and thus independent of the specific value of ). In this work we direct attention at the dependence of stability regions on a fixed delay . In particular, natural Runge-Kutta methods for DDEs are extensively examined. Received April 15, 1996 / Revised version received August 8, 1996