The numerical stability of evaluation schemes for polynomials based on the lagrange interpolation form

For evaluation schemes based on the Lagrangian form of a polynomial with degreen, a rigorous error analysis is performed, taking into account that data, computation and even the nodes of interpolation might be perturbed by round-off. The error norm of the scheme is betweenn ² andn ²+(3n+7) _n , where _n denotes the Lebesgue constant belonging to the nodes. Hence, the error norm is of least possible orderO(n ²) if, for instance, the nodes are chosen to be the Chebyshev points or the Fekete points.     

Fast inversion of vandermonde-like matrices involving orthogonal polynomials

Let {q} _j ^=0n–1 be a family of polynomials that satisfy a three-term recurrence relation and let {t _k } _k ⁼¹ⁿ be a set of distinct nodes. Define the Vandermonde-like matrixW _n =[w _jk ] _k,j ⁼¹ⁿ ,w _jk =q _j–1(t _k ). We describe a fast algorithm for computing the elements of the inverse ofW _n inO(n ²) arithmetic operations. Our algorithm generalizes a scheme presented by Traub [22] for fast inversion of Vandermonde matrices. Numerical examples show that our scheme often yields higher accuracy than the LINPACK subroutine SGEDI for inverting a general matrix. SGEDI uses Gaussian elimination with partial pivoting and requiresO(n ³) arithmetic operations.Dedicated to Gene H. Golub on his 60th birthdayResearch supported by NSF grant DMS-9002884.     

On richardson extrapolation for finite difference methods on regular grids

Summary Difference solutions of partial differential equations can in certain cases be expanded by even powers of a discretization parameterh. If we haven solutions corresponding to different mesh widthsh ₁,...,h _n we can improve the accuracy by Richardson extrapolation and get a solution of order 2n, yet only on the intersection of all grids used, i.e. normally on the coarsest grid. To interpolate this high order solution with the same accuracy in points not belonging to all grids, we need 2n points in an interval of length (2n–1)h ₁.This drawback can be avoided by combining such an interpolation with the extrapolation byh. In this case the approximation depends only on grid points in an interval of length 3/2h ₁. The length of this interval is independent of the desired order.By combining this approach with the method of Kreiss, boundary conditions on curved boundaries can be discretized with a high order even on coarse grids.This paper is based on a lecture held at the 5th Sanmarinian University Session of the International Academy of Sciences San Marino, at San Marino, 1988-08-27-1988-09-05     

A Lie-theoretic setting for the classical interpolation theories

The three classical interpolation theories — Newton-Lagrange, Thiele and Pick-Nevanlinna — are developed within a common Lie-theoretic framework. They essentially involve a recursive process, each step geometrically providing an analytic map from a Riemann surface to a Grassmann manifold. The operation which passes from the (n−1)st to the nth involves the action of what the physicists call a group of gauge transformations. There is also a first-order difference operator which maps the set of solutions of the nth order interpolation to the (n−1)st: This difference operator is, in each case, covariant with respect to the action of the Lie groups involved. For Newton-Lagrange interpolation, this Lie group is the group of affine transformations of the complex plane; for Thiele interpolation the group SL(2, C) of projective transformations; and for Pick-Nevanlinna interpolation the subgroup SU(1, 1) of SL(2, C) which leaves invariant the disk in the complex plane. National Research Council Senior Research Associate at the Ames Research Center (NASA)}.     

A parallel method for fast and practical high-order newton interpolation

We present parallel algorithms for the computation and evaluation of interpolating polynomials. The algorithms use parallel prefix techniques for the calculation of divided differences in the Newton representation of the interpolating polynomial. Forn+1 given input pairs, the proposed interpolation algorithm requires only 2 [log(n+1)]+2 parallel arithmetic steps and circuit sizeO(n ²), reducing the best known circuit size for parallel interpolation by a factor of logn. The algorithm for the computation of the divided differences is shown to be numerically stable and does not require equidistant points, precomputation, or the fast Fourier transform. We report on numerical experiments comparing this with other serial and parallel algorithms. The experiments indicate that the method can be very useful for very high-order interpolation, which is made possible for special sets of interpolation nodes.Supported in part by the National Science Foundation under Grant No. NSF DCR-8603722.Supported by the National Science Foundation under Grants No. US NSF MIP-8410110, US NSF DCR85-09970, and US NSF CCR-8717942 and AT&T under Grant AT&T AFFL67Sameh.     

Folding a surface to a polygon

A concept of folding for compact connected surfaces, involving the partition of the surface into combinatorially identical n-sided topological polygons, is defined. The existence of such foldings for given n and given surfaces is explored, with definitive results for the sphere and the torus. We obtain necessary conditions for the existence of such foldings in all other cases.Supported by Kuwait University Grant SM 043.     

Weakly union-free maximum packings

Frankl and Füredi [11] established that the largest number of 3-subsets of ann-set, for which no four distinct setsA,B,D satisfyAB=CD, is at most . Chee, Colbourn, and Ling [6] established that this upper bound is met with few exceptions whenn0, 1 (mod 3). In this paper, it is established that the upper bound is also met with few exceptions whenn2 (mod 3).The research was supported in part by the US Army Research Office under Grant DAAG55-98-1-0272.     

Reconstruction of quasi developable surfaces from ribbon curves

This paper deals with the acquisition and reconstruction of physical surfaces by mean of a ribbon device equipped with micro-sensors, providing geodesic curves running on the surface. The whole process involves the reconstruction of these 3D ribbon curves together with their global treatment so as to produce a consistent network for the geodesic surface interpolation by filling methods based on triangular Coons-like approaches. However, the ribbon curves follow their own way, subdividing thus the surface into arbitrary n-sided patches. We present here a method for the reconstruction of quasi developable surfaces from such n-sided curvilinear boundary curves acquired with the ribbon device.     

An approximate Dirac-type theorem for k-uniform hypergraphs

A k-uniform hypergraph is hamiltonian if for some cyclic ordering of its vertex set, every k consecutive vertices form an edge. In 1952 Dirac proved that if the minimum degree in an n-vertex graph is at least n/2 then the graph is hamiltonian. We prove an approximate version of an analogous result for uniform hypergraphs: For every K ≥ 3 and γ > 0, and for all n large enough, a sufficient condition for an n-vertex k-uniform hypergraph to be hamiltonian is that each (k − 1)-element set of vertices is contained in at least (1/2 + γ)n edges. Research supported by NSF grant DMS-0300529. Research supported by KBN grant 2P03A 015 23 and N201036 32/2546. Part of research performed at Emory University, Atlanta. Research supported by NSF grant DMS-0100784.     

Maximal order for quadratures usingn evaluations

The problem is to find approximationsI (f; h) to the integralI(f; h)= ₀ ^h f. Such an approximation has local orderp ifI(f; h)–I (f; h)=O(h ^p ) ash0. Let(n) denote the maximal local order possible for a method usingn evaluations of a function or its derivatives. We show that (n)=2n+1 if the information used is Hermitian. This is conjectured to be true in general. The conjecture is established for all methods using three or fewer evaluations.This research was supported in part by the National Science Foundation under Grant MCS75-222-55 and the Office of Naval Research under Contract N00014-76-C-0370, NR 044-422. Numerical results reported in this paper were obtained through the computing facilities of the University of Maryland.     

Fast verification of solutions of matrix equations

Summary. In this paper, we are concerned with a matrix equation where A is an real matrix and x and b are n-vectors. Assume that an approximate solution is given together with an approximate LU decomposition. We will present fast algorithms for proving nonsingularity of A and for calculating rigorous error bounds for . The emphasis is on rigour of the bounds. The purpose of this paper is to propose different algorithms, the fastest with flops computational cost for the verification step, the same as for the LU decomposition. The presented algorithms exclusively use library routines for LU decomposition and for all other matrix and vector operations. Received June 16, 1999 / Revised version received January 25, 2001 / Published online June 20, 2001     

Proof Of A Conjecture Of Erdős On Triangles In Set-Systems

A triangle is a family of three sets A,B,C such that A∩B, B∩C, C∩A are each nonempty, and . Let be a family of r-element subsets of an n-element set, containing no triangle. Our main result implies that for r ≥ 3 and n ≥ 3r/2, we have This settles a longstanding conjecture of Erdős [7], by improving on earlier results of Bermond, Chvátal, Frankl, and Füredi. We also show that equality holds if and only if consists of all r-element subsets containing a fixed element. Analogous results are obtained for nonuniform families.     

An asymptotic expansion in wavelet analysis and its application to accurate numerical wavelet decomposition

We consider a dilation operatorT admitting a scaling function with compact support as fixed point. It is shown that the adjoint operatorT*admits a sequence of polynomial eigenfunctions and that a smooth functionf admits an expansion in these eigenfunctions, which reveals the asymptotic behavior ofT* forn.Due to this asymptotic expansion, an extrapolation technique can be applied for the accurate numerical computation of the integrals appearing in the wavelet decomposition of a smooth function. This extrapolation technique fits well in a multiresolution scheme.     

Heavy Transversals and Indecomposable Hypergraphs

A weighted hypergraph is a hypergraph H = (V, E) with a weighting function , where R is the set of reals. A multiset S V generates a partial hypergraph H ^S with edges , where both the cardinality and the total weight w(S) are counted with multiplicities of vertices in S. The transversal number of H is represented by (H). We prove the following: there exists a function f(n) such that, for any weighted n-Helly hypergraph H, (H ^B ) 1, for all multisets B V if and only if (H ^A ) 1, for all multisets A V with . We provide lower and upper bounds for f(n) using a link between indecomposable hypergraphs and critical weighted n-Helly hypergraphs.* On leave from Computing and Automation Research Institute, Hungarian Academy of Sciences.     

Small transversals in hypergraphs

For each positive integerk, we consider the setA _k of all ordered pairs [a, b] such that in everyk-graph withn vertices andm edges some set of at mostam+bn vertices meets all the edges. We show that eachA _k withk2 has infinitely many extreme points and conjecture that, for every positive , it has only finitely many extreme points [a, b] witha. With the extreme points ordered by the first coordinate, we identify the last two extreme points of everyA _k , identify the last three extreme points ofA ₃, and describeA ₂ completely. A by-product of our arguments is a new algorithmic proof of Turán's theorem.     

Non-uniform Turán-type problems

Given positive integers n,k,t, with 2?k?n, and t<2^k, let m(n,k,t) be the minimum size of a family F of (nonempty distinct) subsets of [n] such that every k-subset of [n] contains at least t members of F, and every (k-1)-subset of [n] contains at most t-1 members of F. For fixed k and t, we determine the order of magnitude of m(n,k,t). We also consider related Turán numbers T_?r(n,k,t) and T_r(n,k,t), where T_?r(n,k,t) (T_r(n,k,t)) denotes the minimum size of a family such that every k-subset of [n] contains at least t members of F. We prove that T_?r(n,k,t)=(1+o(1))T_r(n,k,t) for fixed r,k,t with and n→∞.     

UOBYQA: unconstrained optimization by quadratic approximation

UOBYQA is a new algorithm for general unconstrained optimization calculations, that takes account of the curvature of the objective function, F say, by forming quadratic models by interpolation. Therefore, because no first derivatives are required, each model is defined by ?(n+1)(n+2) values of F, where n is the number of variables, and the interpolation points must have the property that no nonzero quadratic polynomial vanishes at all of them. A typical iteration of the algorithm generates a new vector of variables, _t say, either by minimizing the quadratic model subject to a trust region bound, or by a procedure that should improve the accuracy of the model. Then usually F( _t ) is obtained, and one of the interpolation points is replaced by _t . Therefore the paper addresses the initial positions of the interpolation points, the adjustment of trust region radii, the calculation of _t in the two cases that have been mentioned, and the selection of the point to be replaced. Further, UOBYQA works with the Lagrange functions of the interpolation equations explicitly, so their coefficients are updated when an interpolation point is moved. The Lagrange functions assist the procedure that improves the model, and also they provide an estimate of the error of the quadratic approximation to F, which allows the algorithm to achieve a fast rate of convergence. These features are discussed and a summary of the algorithm is given. Finally, a Fortran implementation of UOBYQA is applied to several choices of F, in order to investigate accuracy, robustness in the presence of rounding errors, the effects of first derivative discontinuities, and the amount of work. The numerical results are very promising for n≤20, but larger values are problematical, because the routine work of an iteration is of fourth order in the number of variables. Received: December 7, 2000 / Accepted: August 31, 2001?Published online April 12, 2002     

Directional approximation of the jacobians in ROW-methods

In this paper a new technique for avoiding exact Jacobians in ROW methods is proposed. The Jacobiansf' _n are substituted by matricesA _n satisfying a directional consistency conditionA _n f _n =f' _n f _n +O(h). In contrast to generalW-methods this enables us to reduce the number of order conditions and we construct a 2-stage method of order 3 and families of imbedded 4-stage methods of order 4(3). The directional approximation of the Jacobians has been realized via rank-1 updating as known from quasi-Newton methods.     

Small Forbidden Configurations IV: The 3 Rowed Case

The present paper continues the work begun by Anstee, Griggs and Sali on small forbidden configurations. We define a matrix to be simple if it is a (0,1)-matrix with no repeated columns. Let F be a k×l (0,1)-matrix (the forbidden configuration). Small refers to the size of k and in this paper k = 3. Assume A is an m×n simple matrix which has no submatrix which is a row and column permutation of F. We define forb(m,F) as the best possible upper bound on n, for such a matrix A, which depends on m and F. We complete the classification for all 3-rowed (0,1)-matrices of forb (m,F) as either Θ(m), Θ(m²) or Θ(m³) (with constants depending on F). * Research is supported in part by NSERC. † Research was done while the second author visited the University of British Columbia supported by NSERC of first author. Research was partially supported by Hungarian National Research Fund (OTKA) numbers T034702 and T037846.     

Linear Codes and Character Sums

Let V be an rn-dimensional linear subspace of . Suppose the smallest Hamming weight of non-zero vectors in V is d. (In coding-theoretic terminology, V is a linear code of length n, rate r and distance d.) We settle two extremal problems on such spaces.First, we prove a (weak form) of a conjecture by Kalai and Linial and show that the fraction of vectors in V with weight d is exponentially small. Specifically, in the interesting case of a small r, this fraction does not exceed .We also answer a question of Ben-Or and show that if , then for every k, at most vectors of V have weight k.Our work draws on a simple connection between extremal properties of linear subspaces of and the distribution of values in short sums of -characters.* Supported in part by grants from the Israeli Academy of Sciences and the Binational Science Foundation Israel-USA. This work was done while the author was a student in the Hebrew University of Jerusalem, Israel.