A New Multisection Technique in Interval Methods for Global Optimization

A new multisection technique in interval methods for global optimization is investigated, and numerical tests demonstrate that the efficiency of the underlying global optimization method can be improved substantially. The heuristic rule is based on experiences that suggest the subdivision of the current subinterval into a larger number of pieces only if it is located in the neighbourhood of a minimizer point. An estimator of the proximity of a subinterval to the region of attraction to a minimizer point is utilized. According to the numerical study made, the new multisection strategies seem to be indispensable, and can improve both the computational and the memory complexity substantially. Received May 31, 1999; revised January 20, 2000     

On the Convergence of a Multigrid Method for Linear Reaction-Diffusion Problems

In this note we consider discrete linear reaction-diffusion problems. For the discretization a standard conforming finite element method is used. For the approximate solution of the resulting discrete problem a multigrid method with a damped Jacobi or symmetric Gauss-Seidel smoother is applied. We analyze the convergence of the multigrid V- and W-cycle in the framework of the approximation- and smoothing property. The multigrid method is shown to be robust in the sense that the contraction number can be bounded by a constant smaller than one which does not depend on the mesh size or on the diffusion-reaction ratio. Received June 15, 2000     

Computation of Lagrange Multipliers for Linear Least Squares Problems with Equality Constraints

Received December 21, 2000; revised June 7, 2001     

Simulated Annealing for Fitting Linear Combinations of Gaussians to Data

 It is difficult to find a good fit of a combination of Gaussians to arbitrary empirical data. The surface defined by the objective function contains many local minima, which trap gradient descent algorithms and cause stochastic methods to tarry unreasonably in the vicinity. A number of techniques for accelerating convergence when using simulated annealing are presented. These are tested on a sample of known Gaussian combinations and are compared for accuracy and resource consumption. A single `best' set of techniques is found which gives good results on the test samples and on empirical data. Received September 27, 1999; revised March 13, 2000     

Iterative Stokes Solvers in the Harmonic Velte Subspace

We explore the prospects of utilizing the decomposition of the function space (H ¹ ₀) ⁿ (where n=2,3) into three orthogonal subspaces (as introduced by Velte) for the iterative solution of the Stokes problem. It is shown that Uzawa and Arrow-Hurwitz iterations – after at most two initial steps – can proceed fully in the third, smallest subspace. For both methods, we also compute optimal iteration parameters. Here, for two-dimensional problems, the lower estimate of the inf-sup constant by Horgan and Payne proves useful and provides an inclusion of the spectrum of the Schur complement operator of the Stokes problem. We further consider the conjugate gradient method in the third Velte subspace and derive a corresponding convergence estimate. Computational results show the effectiveness of this approach for discretizations which admit a discrete Velte decomposition. Received June 11, 1999; revised October 27, 2000     

On the Stability of the Direct Elimination Method for Equality Constrained Least Squares Problems

A backward error analysis of the direct elimination method for linear equality constrained least squares problems is presented. It is proved that the solution computed by the method is the exact solution of a perturbed problem and bounds for data perturbations are given. The numerical stability of the method is related to the way in which the constraints are used to eliminate variables and these theoretical conclusions are confirmed by a numerical example. Received February 15, 1999; revised December 10, 1999     

A Dynamic Method for Weighted Linear Least Squares Problems

A new method for solving the weighted linear least squares problems with full rank is proposed. Based on the theory of Liapunov's stability, the method associates a dynamic system with a weighted linear least squares problem, whose solution we are interested in and integrates the former numerically by an A-stable numerical method. The numerical tests suggest that the new method is more than comparative with current conventional techniques based on the normal equations. Received August 4, 2000; revised August 29, 2001 Published online April 25, 2002     

Spectral Galerkin Discretization for Hydrodynamic Stability Problems

A spectral Galerkin discretization for calculating the eigenvalues of the Orr-Sommerfeld equation is presented. The matrices of the resulting generalized eigenvalue problem are sparse. A convergence analysis of the method is presented which indicates that a) no spurious eigenvalues occur and b) reliable results can only be expected under the assumption of scale resolution, i.e., that Re/p ² is small; here Re is the Reynolds number and p is the spectral order. Numerical experiments support that the assumption of scale resolution is necessary in order to obtain reliable results. Exponential convergence of the method is shown theoretically and observed numerically. Received November 11, 1998; revised March 1, 2000     

Gradient Recovery for Singularly Perturbed Boundary Value Problems I: One-Dimensional Convection-Diffusion

We consider a Galerkin finite element method that uses piecewise linears on a class of Shishkin-type meshes for a model singularly perturbed convection-diffusion problem. We pursue two approaches in constructing superconvergent approximations of the gradient. The first approach uses superconvergence points for the derivative, while the second one combines the consistency of a recovery operator with the superconvergence property of an interpolant. Numerical experiments support our theoretical results. Received November 12, 1999; revised September 9, 2000     

Horner's Rule for Interval Evaluation Revisited

Interval arithmetic can be used to enclose the range of a real function over a domain. However, due to some weak properties of interval arithmetic, a computed interval can be much larger than the exact range. This phenomenon is called dependency problem. In this paper, Horner's rule for polynomial interval evaluation is revisited. We introduce a new factorization scheme based on well-known symbolic identities in order to handle the dependency problem of interval arithmetic. The experimental results show an improvement of 25% of the width of computed intervals with respect to Horner's rule. Received December 14, 2001; revised March 27, 2002 Published online: July 8, 2002     

Robust Multigrid Methods for Nearly Incompressible Elasticity

We consider multigrid methods for problems in linear elasticity which are robust with respect to the Poisson ratio. Therefore, we consider mixed approximations involving the displacement vector and the pressure, where the pressure is approximated by discontinuous functions. Then, the pressure can be eliminated by static condensation. The method is based on a saddle point smoother which was introduced for the Stokes problem and which is transferred to the elasticity system. The performance and the robustness of the multigrid method are demonstrated on several examples with different discretizations in 2D and 3D. Furthermore, we compare the multigrid method for the saddle point formulation and for the condensed positive definite system. Received February 5, 1999; revised October 5, 1999     

Complexity Results for Single-Machine Problems with Positive Finish-Start Time-Lags

In a single-machine problem with time-lags a set of jobs has to be processed on a single machine in such a way that certain timing restrictions between the finishing and starting times of the jobs are satisfied and a given objective function is minimized. We consider the case of positive finish-start time-lags which mean that between the finishing time of job i and the starting time of job j the minimal distance has to be respected. New complexity results are derived for single-machine problems with constant positive time-lags which also lead to new results for flow-shop problems with unit processing times and job precedences. Received: May 13, 1998; revised November 23, 1998     

Multiresolution Visualization of Higher Order Adaptive Finite Element Simulations

h –p–adaptive projection with respect to any prescribed threshold value for the visual error. This projection can then be processed by various local rendering methods, e.g. color coding of data or isosurface extraction. Especially for color coding purposes modern texture capabilities are used to directly render higher polynomial data by superposition of polynomial basis function textures and final color look-up tables. Numerical experiments from CFD clearly demonstrate the applicability and efficiency of our approach. Received September 25, 2001; revised March 31, 2003 Published online: May 26, 2003 The authors acknowledge the valuable hints of the anonymous referees.     

Stabilised hp-Finite Element Approximation of Partial Differential Equations with Nonnegative Characteristic Form

This paper is devoted to the a priori error analysis of the hp-version of a streamline-diffusion finite element method for partial differential equations with nonnegative characteristic form. This class of equations includes second-order elliptic and parabolic problems, first-order hyperbolic problems and second-order problems of mixed elliptic-parabolic-hyperbolic type. We derive error bounds which are simultaneously optimal in both the mesh size h and the spectral order p. Numerical examples are presented to confirm the theoretical results. Received October 28, 1999; revised May 26, 2000     

On the Multivariate Horner Scheme II: Running Error Analysis

 As an extension of our previous paper which gave forward and backward error estimates, we perform a running error analysis of the multivariate Horner scheme. This leads to a modified algorithm which computes the value of the polynomial together with an error estimate. Received November 9, 1999; revised May 29, 2000     

Cache-Aware Multigrid Methods for Solving Poisson's Equation in Two Dimensions

Conventional implementations of iterative numerical algorithms, especially multigrid methods, merely reach a disappointing small percentage of the theoretically available CPU performance when applied to representative large problems. One of the most important reasons for this phenomenon is that the need for data locality due to poor main memory latency and limited bandwidth is entirely neglected by many developers designing numerical software. Only when most of the data to be accessed during the computation are found in the system cache (or in one of the caches if the machine architecture comprises a cache hierarchy) fast program execution can be expected. Otherwise, i.e. in case of a significant rate of cache misses, the processor must stay idle until the necessary operands are fetched from main memory, whose cycle time is in general extremely large compared to the time needed to execute a floating point instruction. In this paper, we describe program transformation techniques developed to improve the cache performance of two-dimensional multigrid algorithms. Although we merely consider the solution of Poisson's equation on the unit square using structured grids, our techniques provide valuable hints towards the efficient treatment of more general problems. Received January 31, 1999; revised October 17, 1999     

ℋ-matrices for Convection-diffusion Problems with Constant Convection

L ^∞-coefficients. This paper analyses the application of hierarchical matrices to the convection-dominant convection-diffusion equation with constant convection. In the case of increasing convection, the convergence of a standard ℋ-matrix approximant towards the original matrix will deteriorate. We derive a modified partitioning and admissibility condition that ensures good convergence also for the singularly perturbed case. Received January 1, 2003; revised March 4, 2003 Published online: May 2, 2003     

A Note on Transformed Density Rejection

In this paper we describe a version of transformed density rejection that requires less uniform random numbers. Random variates below the squeeze are generated by inversion. For the expensive part between squeeze and density an algorithm that uses a covering with triangles is introduced. Received August 23, 1999; revised March 6, 2000     

Multilevel Stabilization of Convection–Diffusion Problems by Variable-Order Inner Products

We are concerned with the task of stabilizing discrete approximations to convection–diffusion problems. We propose to consistently modify the exact variational formulation of the problem by adding a fractional order inner product, involving the residual of the equation. The inner product is expressed through a multilevel decomposition of its arguments, in terms of components along a multiscale basis. The order of the inner product locally varies from −1/2 to −1, depending on the value of a suitably-defined multiscale Péclet number. Numerical approximations obtained via the Galerkin method applied to the modified formulation are analyzed. Received January 1, 2000; revised November 2, 2000