Smoothing noisy data with spline functions

Summary A procedure for calculating the trace of the influence matrix associated with a polynomial smoothing spline of degree2m–1 fitted ton distinct, not necessarily equally spaced or uniformly weighted, data points is presented. The procedure requires orderm ² n operations and therefore permits efficient orderm ² n calculation of statistics associated with a polynomial smoothing spline, including the generalized cross validation. The method is a significant improvement over an existing method which requires ordern ³ operations.     

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.     

On the limit cycles available from polynomial perturbations of the Bogdanov-Takens Hamiltonian

The displacement map related to small polynomial perturbations of the planar Hamiltonian systemdH=0 is studied in the elliptic caseH=1/2y ²+1/2x ²−1/3x ³. An estimate of the number of isolated zeros for each of the successive Melnikov functionsM _k(h),k=1, 2,…is given in terms of the orderk and the maximal degreen of the perturbation. This sets up an upper bound to the number of limit cycles emerging from the periodic orbits of the Hamiltonian system under polynomial perturbations. Research partially supported by grant MM810/98 from the NSF of Bulgaria and MURST, Italy.     

Polynomial Factorisation and an Application to Regular Directed Graphs

The main theme is the distribution of polynomials of given degree which split into a product of linear factors over a finite field. The work was motivated by the following problem on regular directed graphs. Extending a notion of Chung, Katz has defined a regular directed graph based on thek-algebrak[X]/(f), wherekis the finite field of orderqandfa monic polynomial of degreenoverk. It is shown that the diameter of this graph is at mostn+2 wheneverq≥B(n)=[n(n+2)!]². This improves on the work of Katz who gave a similar result for square-free polynomialsfwithout specifyingB(n).     

The exact bound on the number of zeros of harmonic polynomials

A harmonic polynomial of degreen has at mostn ² zeros. It is shown that this bound is exact. Supported by the fund for the promotion of research at the Technion.     

An inequality relating the order,maximum degree,diameter and connectivity of a strongly connected digraph

We prove that if there is a strongly connected digraph of ordern, maximum degreed, diameterk and connectivityc, thennc d ^k–d /d–1+d+1. It improves the previous known results, and it, in fact, is the best possible for several interesting cases. A similar result for arc connectivity is also established.This project is supported by the National Natural Science Foundation of China.     

Phase portraits of the quadratic vector fields with a polynomial first integral

In this work we classify the phase portraits of all quadratic polynomial differential systems having a polynomial first integral. IfH(x, y) is a polynomial of degreen+1 then the differential systemx′=−∂H/∂y,y′=∂H/∂x is called a Hamiltonian system of degreen. We also prove that all the phase portraits that we obtain in this paper are realizable by Hamiltonian systems of degree 2.     

Centralizers satisfying polynomial identities

The following results are proved: IfR is a simple ring with unit, and for someaεR witha ⁿ in the center ofR, anyn, such that the centralizer ofa inR satisfies a polynomial identity of degreem, thenR satisfies the standard identity of degreenm. WhenR is not simple,R will satisfy a power of the same standard identity, provided thata andn are invertible inR. These theorems are then applied to show that ifG is a finite solvable group of automorphisms of a ringR, and the fixed points ofG inR satisfy a polynomial identity, thenR satisfies a polynomial identity, providedR has characteristic 0 or characteristicp wherep✗|G|. This research was supported in part by NSF Grant No. GP 29119X.     

On the Order of Polynomial Reproduction for Multi-scaling Functions

The objective of this paper is to establish certain necessary and sufficient conditions for amulti-scaling function φ := (φ₁,…, φ_r)^Tto have polynomial reproduction (p. r.) of ordermin terms of the eigenvalues and their corresponding eigenvectors of twofinitematrices.     

Superfluous matrices in linear complementarity

Superfluous matrices were introduced by Howe (1983) in linear complementarity. In general, producing examples of this class is tedious (a few examples can be found in Chapter 6 of Cottle, Pang and Stone (1992)). To overcome this problem, we define a new class of matrices and establish that in superfluous matrices of any ordern 4 can easily be constructed. For every integerk, an example of a superfluous matrix of degreek is exhibited in the end.     

An efficient method for calculating smoothing splines using orthogonal transformations

Summary A procedure for calculating the mean squared residual and the trace of the influence matrix associated with a polynomial smoothing spline of degree 2m–1 using an orthogonal factorization is presented. The procedure substantially overcomes the problem of ill-conditioning encountered by a recently developed method which employs a Cholesky factorization, but still requires only orderm ² n operations and ordermn storage.     

The structure of weighing matrices having large weights

We examine the structure of weighing matricesW(n, w), wherew=n–2,n–3,n–4, obtaining analogues of some useful results known for the casen–1. In this setting we find some natural applications for the theory ofsigned groups and orthogonal matrices with entries from signed groups, as developed in [3]. We construct some new series of Hadamard matrices from weighing matrices, including the following:W(n, n–2) implies an Hadamard matrix of order2n ifn0 mod 4 and order 4n otherwise;W(n, n–3) implies an Hadamard matrix of order 8n; in certain cases,W(n, n–4) implies an Hadamard matrix of order 16n. We explicitly derive 117 new Hadamard matrices of order 2 ^t p, p<4000, the smallest of which is of order 2³·419.Supported by an NSERC grant     

Laurent-Padé approximants to four kinds of Chebyshev polynomial expansions. Part I. Maehly type approximants

Laurent Padé-Chebyshev rational approximants,A _m (z,z ⁻¹)/B _n (z, z ⁻¹), whose Laurent series expansions match that of a given functionf(z,z ⁻¹) up to as high a degree inz, z ⁻¹ as possible, were introduced for first kind Chebyshev polynomials by Clenshaw and Lord [2] and, using Laurent series, by Gragg and Johnson [4]. Further real and complex extensions, based mainly on trigonometric expansions, were discussed by Chisholm and Common [1]. All of these methods require knowledge of Chebyshev coefficients off up to degreem+n. Earlier, Maehly [5] introduced Padé approximants of the same form, which matched expansions betweenf(z,z ⁻¹)B _n (z, z ⁻¹)). The derivation was relatively simple but required knowledge of Chebyshev coefficients off up to degreem+2n. In the present paper, Padé-Chebyshev approximants are developed not only to first, but also to second, third and fourth kind Chebyshev polynomial series, based throughout on Laurent series representations of the Maehly type. The procedures for developing the Padé-Chebyshev coefficients are similar to that for a traditional Padé approximant based on power series [8] but with essential modifications. By equating series coefficients and combining equations appropriately, a linear system of equations is successfully developed into two sub-systems, one for determining the denominator coefficients only and one for explicitly defining the numerator coefficients in terms of the denominator coefficients. In all cases, a type (m, n) Padé-Chebyshev approximant, of degreem in the numerator andn in the denominator, is matched to the Chebyshev series up to terms of degreem+n, based on knowledge of the Chebyshev coefficients up to degreem+2n. Numerical tests are carried out on all four Padé-Chebyshev approximants, and results are outstanding, with some formidable improvements being achieved over partial sums of Laurent-Chebyshev series on a variety of functions. In part II of this paper [7] Padé-Chebyshev approximants of Clenshaw-Lord type will be developed for the four kinds of Chebyshev series and compared with those of the Maehly type.     

An algebraic approach to approximate evaluation of a polynomial on a set of real points

The previous best algorithm for approximate evaluation of a polynomial on a real set was due to Rokhlin and required of the order ofmu+nu ³ infinite precision arithmetic operations to approximate [on a fixed bounded setX(m) ofm+1 real points] a degreen polynomial within the error bound . We develop an approximation algorithm which exploits algebraic computational techniques and decreases Rokhlin's record estimate toO(mlog² u+nmin-u, logn}). For logu=o(logn), this result may also be favorably compared with the record boundO(m+n)log² n) on the complexity of the exact multipoint polynomial evaluation. The new algorithm can be performed in the fields (or rings) generated by the input values, which enables us to decrease the precision of the computations [by using modular (residue) arithmetic] and to simplify our computations further in the case whereu=O(logn). Our algorithm allows NC and simultaneously processor efficient parallel implementation. Because of the fundamental nature of the multipoint polynomial evaluation, our results have further applications to numerical and algebraic computational problems. In passing, we also show a substantial improvement in the Chinese remainder algorithm for integers based on incorporating Kaminski's fast residue computation.     

Constructions of harmonic polynomial maps between spheres

The complexity of _q -eigenmaps, i.e. homogeneous degreeq harmonic polynomial mapsf:S ^m S ⁿ, increases fast with the degreeq and the source dimensionm. Here we introduce a variety of methods of manufacturing new eigenmaps out of old ones. They include degree and source dimension raising operators. As a byproduct, we get estimates on the possible range dimensions of full eigenmaps and obtain a geometric insight of the harmonic product of ₂-eigenmaps.     

Best polynomial approximations: A corrected proof

A proof is given of a theorem concerning the best (in the sense of thep-norm) piecewise polynomial approximation of degreen for a function belonging toC ⁿ⁺¹[a,b]. This corrects an earlier, erroneous proof of the same theorem.     

Torsion sur des familles de courbes de genre g

We construct here, forl=2g ² +2g+1 or2g ² +3g+1, a family with one parameter of hyperelliptic curves of genusg overQ such that its jacobian has a point of orderl rational overQ(t). Wheng=2 the method allows to construct, forl=17, 19 or 21 a family with one parameter of hyperelliptic curves of genus 2 overQ such that its jacobian has a point of orderl rational overQ(t).      

A counterexample in copositive approximation

The present paper gives a converse result by showing that there exists a functionf ∈C _[−1,1], which satisfies that sgn(x)f(x) ≥ 0 forx ∈ [−1, 1], such that {fx75-1} whereE _n ⁽⁰⁾ (f, 1) is the best approximation of degreen tof by polynomials which are copositive with it, that is, polynomialsP withP(x(f(x) ≥ 0 for allx ∈ [−1, 1],E _n(f) is the ordinary best polynomial approximation off of degreen.     

On the complexity of a PL homotopy algorithm for zeros of polynomials

A PL homotopy algorithm is modified to yield a polynomial-time result on its computational complexity. We prove that the cost of locating all zeros of a polynomial of degreen to an accuracy of (measured by the number of evaluations of the polynomial) grows no faster thanO(max{n ⁴,n ³log₂(n/)}).This work is in response to a question raised in a paper by S. Smale as to the efficiency of piecewise linear methods in solving equations. In comparison with a few results reported, the algorithm under discussion is the only one providing correct multiplicities and the only one employing vector labelling.This work is supported in part by the Foundation of Zhongshan University Advanced Research Centre, and in part by the National Natural Science Foundation of China.     

The Hecke-algebras related to the unimodular and modular group over the Hurwitz order of integral quaternions

In the present paper the elementary divisor theory over the Hurwitz order of integral quaternions is applied in order to determine the structure of the Hecke-algebras related to the attached unimodular and modular group of degreen. In the casen = 1 the Hecke-algebras fail to be commutative. Ifn > 1 the Hecke-algebras prove to be commutative and coincide with the tensor product of their primary components. Each primary component turns out to be a polynomial ring inn resp.n + 1 resp. 2n resp. 2n+1 algebraically independent elements. In the case of the modular group of degreen, the law of interchange with the Siegel ϕ-operator is described. The induced homomorphism of the Hecke-algebras is surjective except for the weightsr = 4n-4 andr = 4n-2.