On the approximate evaluation of Hadamard finite-part integrals

Grnwald's algorithms for the numerical evaluation of Hadamardfinite-part integrals with non-integer exponent are extendedto the case of integer exponent. These algorithms are basedon the use of Bernstein polynomials and it is shown how, byan appropriate modification of the first algorithm, a convergencerate of order 1/N² may be obtained, where N is the number offunction evaluations.     

Arbitrary-norm hyperplane separation by variable neighbourhood search

^** Email: alejandro.karam{at}hec.ca^*** Email: gilles.caporossi{at}gerad.ca^**** Email: pierre.hansen{at}gerad.ca We consider the problem of separating two sets of points ina Euclidean space with a hyperplane that minimizes the sum ofp-norm distances to the plane of points lying on the ‘wrong’side of the plane. A variable neighbourhood search heuristicis used to determine the plane coefficients. For a set of exampleswith L₁-norm, L₂-norm and L-norm, for which the exact solutioncan be computed, we show that our algorithm finds it in mostcases and gets good approximations in the others. The use ofour heuristic solutions for problems in these norms can dramaticallyaccelerate exact algorithms. Our method can be applied on verylarge instances that are intractable by exact algorithms. Sincethe proposed approach works for truly arbitrary norms (otherthan the traditional 1, 2 and ), we can explore for the firsttime the effects of the choice of p on the generalization propertiesof p-norm hyperplane separation.     

Fast Solution of Vandermonde-Like Systems Involving Orthogonal Polynomials

Consider the (n + 1) ? (n + 1) Vandermonde-like matrix P=[p_i-1(_j-1)],where the polynomials p_o(x), ..., p_n(x) satisfy a three-termrecurrence relation. We develop algorithms for solving the primaland dual systems, Px = b and P^Ta = f respectively, in O(n²)arithmetic operations and O(n) elements of storage. These algorithmsgeneralize those of Bj?rck & Pereyra which apply to themonomial case p_i(x). When the p_i(x) are the Chebyshev polynomials,the algorithms are shown to be numerically unstable. However,it is found empirically that the addition of just one step ofiterative refinement is, in single precision, enough to makethe algorithms numerically stable.     

An Efficient Algorithm for Solving the Rectilinear Multifacility Location Problem

One of the efficient methods for solving large rectilinear multifacilitylocation problems is the Direct Search method. The only drawbackof this method lies in the following difficulty. In some situations,when t new facilities are located together at one point, thenumber of arithmetic operations which are needed to establishoptimality is proportional to t²2^t. Therefore the method needsa prohibitive amount of computation time whenever t exceeds,say, 20. This paper gives a simple remedy for this problem.The paper states and proves a new necessary and sufficient optimalitycondition. This condition transforms the problem of computinga descent direction into a constrained linear least-squaresproblem. The latter problem is solved by a relaxation methodthat takes advantage of its special structure. The new techniqueis incorporated into the Direct Search method. This yields animproved algorithm that handles efficiently very large clusters.Numerical results are included.     

A Finite Element Galerkin Method for a Unidimensional Single-Phase Nonlinear Stefan Problem with Dirichlet Boundary Conditions

Based on straightening the free boundary, an H¹-Galerkin methodis proposed and analysed for a single-phase nonlinear Stefanproblem with Dirichlet boundary conditions. Optimal H¹ estimatesfor continuous-time Galerkin approximations are derived.     

Multiplicative Error Analysis of Matrix Transformation Algorithms

The author's recently introduced relative error measure forvectors is applied to the error analysis of algorithms whichproceed by successive transformation of a matrix. Instead ofmodelling the roundoff errors at each stage by A: = T(A)+E onemodels them by A: =e^E T(A) where E is a small linear transformation.This can simplify analyses considerably. Applications to theparallel Jacobi method for eigenvalues, and to Gaussian elimination,are given.     

Minimal bases of matrix pencils and coprime matrix fraction descriptions

Two new methods for the construction of coprime MFDs are proposedstarting from a minimal state space realization of a transferfunction matrix. The approaches are based on the constructionof minimal bases for the kernels of the state-space-based pencils[s I – A, – B], [s I – A^t, –C^t]. Thelatter problem is explicitly solved using the Toeplitz matrixconstruction of minimal bases of matrix pencils. The numericalalgorithms of the methods are presented and some examples demonstratingthe implementation of the algorithms are also given. Received 18 May 2000. Revised 5 September 2000. Accepted 5 September 2000.     

Piecewise Polynomial Approximate Solutions of an Automatic Control Problem

This paper considers piecewise polynomial approximate solutionsof a variational problem in which boundary conditions dependon values on the solution at interior points. The approximatesolutions are shown to converge to the solution of the variationalproblem in the L² and uniform norms, and algorithms for findingthe approximate solutions are obtained. Numerical examples arealso given.     

On the Least Q-order of Convergence of Variable Metric Algorithms

It is shown in this paper that the infimum of the Q-order ofthe convergence of variable metric algorithms is only 1, eventhough the objective function is twice continuously differentiableand uniformly convex. It is shown by example that the Q-ordercan be 1 + 1/N for any large N, though the R-order is (1+N)^1/2.     

A finite element method for a unidimensional single-phase nonlinear free boundary problem in groundwater flow

Consider a unidimensional, single-phase nonlinear Stefan problemwith nonlinear source and permeance terms, and a Dirichlet boundarycondition depending on the free boundary function. This problemis important in groundwater flow. By immobilizing the free boundarywith the help of a Landau-type transformation, together witha homogeneous transformation dealing with the nonhomogeneousDirichlet boundary condition, an H¹-finite element method forthe problem is proposed and analyzed. Global existence of theapproximate solution is established, and optimal error estimatesin L², L, H¹ and H² norms are derived for both semi-discreteand fully discrete schemes.     

Decomposition strategies for large-scale continuous location-allocation problems

^** Email: nenad.mladenovic{at}brunel.ac.uk The continuous location–allocation problem requires findingsites for m new facilities in the plane in order to serve nusers such that the total transportation costs are minimized.Several heuristics have been developed to solve this well-studiedglobal optimization problem. However, little work has been doneusing decomposition techniques. In this paper, we examine afew new ways to decompose the location–allocation problem.These strategies are then embedded in a variable neighbourhooddecomposition search heuristic and tested on large instancesof this problem.     

A qualocation method for a unidimensional single phase semilinear Stefan problem

Based on straightening the free boundary, a qualocation methodis proposed and analysed for a single phase unidimensional Stefanproblem. This method may be considered as a discrete versionof the H¹-Galerkin method in which the discretization is achievedby approximating the integrals by a composite Gauss quadraturerule. Optimal error estimates are derived in L(W^j,), j = 0,1,and L (H^j), j = 0,1,2, norms for a semidiscrete scheme withoutany quasi-uniformity assumption on the finite element mesh.     

An unfitted finite-element method for elliptic and parabolic interface problems

Bhupen Deka Department of Mathematics, Assam University, Silchar-788011, India ^{A finite-element discretization, independent of the locationof the interface, is proposed and analysed for linear ellipticand parabolic interface problems. We establish error estimatesof optimal order in the H1-norm and almost optimal order inthe L2-norm for elliptic interface problems. An extension toparabolic interface problems is also discussed and an optimalerror estimate in the L2(0, T;H1())-norm and an almost optimalorder estimate in the L2(0, T;L2())-norm are derived for thespatially discrete scheme. A fully discrete scheme based onthe backward Euler method is analysed and an optimal order errorestimate in the L2(0, T;H1())-norm is derived. The interfacesare assumed to be of arbitrary shape and smooth for our purpose.}     

Natural Tiling, Lattice Tiling and Lebesgue Measure of Integral Self-Affine Tiles

In the existing theory of self-affine tiles, one knows thatthe Lebesgue measure of any integral self-affine tile correspondingto a standard digit set must be a positive integer and everyintegral self-affine tile admits some lattice Zⁿ as a translationtiling set of Rⁿ. In this paper, we give algorithms to evaluatethe Lebesgue measure of any such integral self-affine tile Kand to determine all of the lattice tilings of Rⁿ by K. Moreover,we also propose and determine algorithmically another type oftranslation tiling of Rⁿ by K, which we call natural tiling.We also provide an algorithm to decide whether or not Lebesguemeasure of the set K (K+j), j–Zⁿ, is strictly positive.     

Numerical Solution of Matrix Polynomial Equations by Newton's Method

Let P(X) = _v=1ⁿ A_vX^v with A_v, X C^m?m (v = 1, ..., n) be a matrixpolynomial. We present a Newton method to solve the equationP(X) = B, and we prove that the algorithm converges quadraticallynear simple solvents. We need the inverse of the Fr?chet-derivativeP' of P. This leads to linear equations for the correctionsH of type In the second part, we turn to the case of scalar coefficients, i.e. A_v = _vI, with_v C (v = 1, ..., n). The derivative P' and the usual algebraicderivative P' are compared and we show that the use of P' leadsto difficulties. In particular, those algorithms based on P'are not self-correcting, while our proposed method is self-correcting.Numerical examples are included. In the Appendix, an existencetheorem is proved by using a modified Newton method.     

On the Algebra of Operations for Hopf Cohomology

In his thesis (Mem. Amer. Math. Soc. 42 (1962)) A. Liuleviciusdefined Steenrod squaring operations Sq^k on the cohomology ringof any cocommutative Hopf algebra over Z/2. Later, J. P. Mayshowed that these operations satisfy Adem relations, interpretedso that Sq⁰ is not the unit but an independent operation. Thus,these Adem relations are homogeneous of length two in the generators.This paper is concerned with the bigraded algebra B that isgenerated by elements Sq^k and subject to Adem relations; itshows that the Cartan formula gives a well-defined coproducton B. Also, it is shown that B with both multiplication andcomultiplication should be considered neither a Hopf algebranor a bialgebra, but another kind of structure, for which thename ‘algebra with coproducts’ is proposed in thepaper. 2000 Mathematics Subject Classification 55S10 (primary),55T15 (secondary).     

Local Rigidity of Infinite-Dimensional Teichmuller Spaces

This paper presents a rigidity theorem for infinite-dimensionalBergman spaces of hyperbolic Riemann surfaces, which statesthat the Bergman space A¹(M), for such a Riemann surface M,is isomorphic to the Banach space of summable sequence, l¹.This implies that whenever M and N are Riemann surfaces thatare not analytically finite, and in particular are not necessarilyhomeomorphic, then A¹(M) is isomorphic to A¹(N). It is knownfrom V. Markovic that if there is a linear isometry betweenA¹(M) and A¹(N), for two Riemann surfaces M and N of non-exceptionaltype, then this isometry is induced by a conformal mapping betweenM and N. As a corollary to this rigidity theorem presented here,taking the Banach duals of A¹(M) and l¹ shows that the spaceof holomorphic quadratic differentials on M, Q(M), is isomorphicto the Banach space of bounded sequences, l. As a consequenceof this theorem and the Bers embedding, the Teichmüllerspaces of such Riemann surfaces are locally bi-Lipschitz equivalent.     

Capacitated dynamic location problems with opening, closure and reopening of facilities

^** Email: joana{at}fe.uc.pt In this paper a capacitated dynamic location problem with opening,closure and reopening of facilities is formulated and a primal–dualheuristic that can solve this problem is described. In thisproblem both maximum and minimum capacity restrictions are considered.The problem formulated is NP-hard. Computational results arepresented and discussed.     

Two Diophantine Birds with One Stone

Integer Solutions are found to the equations t²–3(a²,b², (a + b)², (a–b)²) = p², q², r², s². These lead surprisinglyto solutions to the equations u² + (c², d², (c + d)², (c –d)²) = p², q², v², w², with the same values of p and q.     

Some Eigenfunction Methods for Computing a Numerical Fourier Transform

A number of methods for calculating the Fourier transform ofa function given numerically are studied. These methods exploitthe fact that the Hermite functions are eigen-functions of theFourier transform. The transforms of four types of functionsare considered: (i) functions of the form p(x) exp (–x²/2),where p(x) is a polynomial, (ii) functions with bounded support.(iii) rapidly decreasing functions, and (iv) functions whosetransform has bounded support. In each case algorithms for calculatingthe transformed function are derived. Error estimates are madein two of the cases and results of numerical experiments presentedin an appendix.