A parallel algorithm for discrete least squares rational approximation

Summary A new method for discrete least squares linearized rational approximation is presented. It generalizes the algorithm of Rutishauser-Gragg-Harrod-Reichel for discrete least squares polynomial approximation to the rational case. The algorithm is fast in the sense that it requires orderm computation time wherem is the number of data points and is the degree of the approximant. We describe how this algorithm can be implemented in parallel.     

Relative perturbation results for eigenvalues and eigenvectors of diagonalisable matrices

Let and be a perturbed eigenpair of a diagonalisable matrixA. The problem is to bound the error in and . We present one absolute perturbation bound and two relative perturbation bounds. The absolute perturbation bound is an extension of Davis and Kahan's sin θ Theorem from Hermitian to diagonalisable matrices. The two relative perturbation bounds assume that and are an exact eigenpair of a perturbed matrixD ₁ AD ₂ , whereD ₁ andD ₂ are non-singular, butD ₁ AD ₂ is not necessarily diagonalisable. We derive a bound on the relative error in and a sin θ theorem based on a relative eigenvalue separation. The perturbation bounds contain both the deviation ofD ₁ andD ₂ from similarity and the deviation ofD ₂ from identity. This work was partially supported by NSF grant CCR-9400921.     

Some lower bounds for the spectral radius of matrices using traces

Let A be an n×n matrix with eigenvalues λ₁,λ₂,…,λ_n, and let m be an integer satisfying rank(A)?m?n. If A is real, the best possible lower bound for its spectral radius in terms of m, trA and trA² is obtained. If A is any complex matrix, two lower bounds for are compared, and furthermore a new lower bound for the spectral radius is given only in terms of trA,trA²,‖A‖,‖A^∗A-AA^∗‖,n and m.     

Quadrature error expansions

Summary We continue the work of Part I, treating in detail the theory of numerical quadrature over a square [0, 1]² using anm ² copy,Q ^(m), of a one-point quadrature rule. As before, we determine the nature of an asymptotic expansion for the quadrature error functionalQ ^(m) F—IF in inverse powers ofm and related functions, valid for specified classes of the integrand functionF. The extreme case treated here is one in which the integrand function has a full-corner algebraic singularity. This has the formx y r, (x, y). Here , , and need not be integer, andr is (x ²+y ²)^/2 or some other similar homogeneous function. The error expansion forms the theoretic basis for the use of extrapolation, for this kind of integrand.This work was supported by the Applied Mathematical Sciences subprogram of the Office of Energy Research, U.S. Department of Energy, under Contract W-31-109-Eng-38     

Truncation error bounds for limit-periodic continued fractionsK(a n /1) with lima n =0

Summary Truncation error bounds are developed for continued fractionsK(a _n /1) where |a _n |1/4 for alln sufficiently large. The bounds are particularly suited (some are shown to be best) for the limit-periodic case when lima _n =0. Among the principal results is the following: If |a _n |/n ^p for alln sufficiently large (with constants >0,p>0), then |f–f _m |C[D/(m+2)] ^p(m+2) for allm sufficiently large (for some constantsC>0,D>0). Heref denotes the limit (assumed finite) ofK(a _n /1) andf _m denotes itsmth approximant. Applications are given for continued fraction expansions of ratios of Kummer functions₁ F ₁ and of ratios of hypergeometric functions₀ F ₁. It is shown thatp=1 for₁ F ₁ andp=2 for₀ F ₁, wherep is the parameter determining the rate of convergence. Numerical examples indicate that the error bounds are indeed sharp.Research supported in part by the National Science Foundation under Grant MCS-8202230 and DMS-8401717     

Convergence acceleration of limit periodic continued fractions under asymptotic side conditions

Summary We present a method of convergence acceleration for limitk-periodic continued fractionsK(a _n /1) orK(1/b _n ) satisfying certain asymptotic side conditions. The method represents an improvement of the fixed point modification considered by Thron and Waadeland [8], under these conditions. The regularC-fraction expansions of hypergeometric functions₂ F ₁(a, 1;c; z) and₂ F ₁(a, b; c; z)/₂ F ₁(a, b+1;c+1;z) are examples of continued fractions satisfying these conditions.     

Stability of the method of lines

Summary It is well known that a necessary condition for the Lax-stability of the method of lines is that the eigenvalues of the spatial discretization operator, scaled by the time stepk, lie within a distanceO(k) of the stability region of the time integration formula ask0. In this paper we show that a necessary and sufficient condition for stability, except for an algebraic factor, is that the -pseudo-eigenvalues of the same operator lie within a distanceO()+O(k) of the stability region ask, 0. Our results generalize those of an earlier paper by considering: (a) Runge-Kutta and other one-step formulas, (b) implicit as well as explicit linear multistep formulas, (c) weighted norms, (d) algebraic stability, (e) finite and infinite time intervals, and (f) stability regions with cusps.In summary, the theory presented in this paper amounts to a transplantation of the Kreiss matrix theorem from the unit disk (for simple power iterations) to an arbitrary stability region (for method of lines calculations).Work supported by an NSF Presidential Young Investigator Award to L.N. Trefethen     

Two counterexamples related to the Kreiss matrix theorem

The modern version of the Kreiss matrix theorem states that A ⁿ esK (for alln0) ifA is ans ×s matrix satisfying a resolvent condition with respect to the unit disk with constantK. In this paper we show for any fixedK + 1 that the upper boundesK is sharp in the sense that a linear dependence on the dimensions is the best possible. An analogous result is obtained for the continuous version of the Kreiss matrix theorem, which states that exp(tA) esK (for allt0) ifA is ans ×s matrix satisfying a resolvent condition with respect to the left half plane with constantK.The research has been made possible by a fellowship of the Royal Netherlands Academy of Arts and Sciences (K.N.A.W.) and was carried out at the Department of Mathematics and Computer Science, University of Leiden, The Netherlands.     

Invariance of closed convex sets and domination criteria for semigroups

Let a and b be two positive continuous and closed sesquilinear forms on the Hilbert space H=L ²(, ). Denote by T=T(t) _t0and S=S(t) _t0the semigroups generated by a and b on H. We give criteria in terms of a and b guaranteeing that the semigroup T is dominated by S, i.e. |T(t)f|S(t)|f| for all t0 and fH. The method proposed uses ideas on invariance of closed convex sets of H under semigroups. Applications to elliptic operators and concrete examples are given.     

Distoriton of area and conditioned Brownian motion

Summary In a simply connected planar domainD the expected lifetime of conditioned Brownian motion may be viewed as a function on the set of hyperbolic geodesics for the domain. We show that each hyperbolic geodesic induces a decomposition ofD into disjoint subregions and that the subregions are obtained in a natural way using Euclidean geometric quantities relating toD. The lifetime associated with on each _j is then shown to be bounded by the product of the diameter of the smallest ball containing _j and the diameter of the largest ball in _j . Because this quantity is never larger than, and in general is much smaller than, the area of the largest ball in _j it leads to finite lifetime estimates in a variety of domains of infinite area.Research of the first author was supported in part by NSF Grant DMS-9100811Research of the second author was supported in part by NSF Grant DMS-9105407     

Spline approximations to spherically symmetric distributions

Summary We discuss the problem of approximating a functionf of the radial distancer in ^d on 0r< by a spline function of degreem withn (variable) knots. The spline is to be constructed so as to match the first 2n moments off. We show that if a solution exists, it can be obtained from ann-point Gauss-Christoffel quadrature formula relative to an appropriate moment functional or, iff is suitably restricted, relative to a measure, both depending onf. The moment functional and the measure may or may not be positive definite. Pointwise convergence is discussed asn. Examples are given including distributions from statistical mechanics.The work of the first author was supported in part by the National Science Foundation under grant DCR-8320561.     

The Whitney embedding theorem for tropical torsion modules: Classification of tropical modules

We prove here a tropical version of the well-known Whitney embedding theorem [32] stating that a smooth connected m-dimensional compact differential manifold can be embedded into R^2m+1.The tropical version of this theorem states that a tropical torsion module with m generators can always be embedded into the free tropical module , where p (equals to 2 for m=2, and otherwise) is the number of rows supporting the torsion, when the generators are given by the (independent) columns of a matrix of size n×m.As a corollary, we get that tropical m-dimensional torsion modules are classified by a (m-1)(m(m-1)-1)-parameter family.     

L 2-approximation by the translates of a function and related attenuation factors

Summary Let be thek-dimensional subspace spanned by the translates (·–2j/k),j=0, 1, ...,k–1, of a continuous, piecewise smooth, complexvalued, 2-periodic function . For a given functionfL ²(–, ), its least squares approximantS _kf from can be expressed in terms of an orthonormal basis. Iff is continuous,S _kf can be computed via its discrete analogue by fast Fourier transform. The discrete least squares approximant is used to approximate Fourier coefficients, and this complements the works of Gautschi on attenuation factors. Examples of include the space of trigonometric polynomials where is the de la Valleé Poussin kernel, algebraic polynomial splines where is the periodic B-spline, and trigonometric polynomial splines where is the trigonometric B-spline.     

Equilibria of Pairs of Nonlinear Maps Associated with Cones

Let K₁, K₂ be closed, full, pointed convex cones in finite-dimensional real vector spaces of the same dimension, and let F : K₁ span K₂ be a homogeneous, continuous, K₂-convex map that satisfies F(K₁) int K₂= and FK₁ int K₂ . Using an equivalent formulation of the Borsuk-Ulam theorem in algebraic topology, we show that we have and We also prove that if, in addition, G : K₁ span K₂ is any homogeneous, continuous map which is (K₁, K₂)-positive and K₂-concave, then there exist a unique real scalar ₀ and a (up to scalar multiples) unique nonzero vector x₀ K₁ such that Gx₀ = ₀Fx₀, and moreover we have ₀ > 0 and x₀ int K₁ and we also have a characterization of the scalar ₀. Then, we reformulate the above result in the setting when K₁ is replaced by a compact convex set and recapture a classical result of Ky Fan on the equilibrium value of a finite system of convex and concave functions.     

Norms and Generating Functions in Clifford Algebras

Generating functions are commonly used in combinatorics to recover sequences from power series expansions. Convergence of formal power series in Clifford algebras of arbitrary signature is discussed. Given , powers of u are recovered by expanding (1 − tu)⁻¹ as a polynomial in t with Clifford-algebraic coefficients. It is clear that (1 − tu)(1 + tu + t ² u ² + ...) = 1, provided the sum (1 + tu + t ² u ² + ...) exists, in which case u ^m is the Cliffordalgebraic coefficient of t ^m in the series expansion of (1 − tu)⁻¹. In this paper, conditions on for the existence of (1 − tu)⁻¹ are given, and an explicit formulation of the generating function is obtained. Allowing A to be an m × m matrix with entries in , a “Clifford-Frobenius” norm of A is defined. Norm inequalities are then considered, and conditions for the existence of (I − tA)⁻¹ are determined. As an application, adjacency matrices for graphs are defined with vectors of as entries. For positive odd integer k > 3, k-cycles based at a fixed vertex of a graph are enumerated by considering the appropriate entry of A ^k . Moreover, k-cycles in finite graphs are enumerated and expected numbers of k-cycles in random graphs are obtained from the norm of the degree-2k part of tr(1 − tu)⁻¹. Unlike earlier work using commutative subalgebras of , this approach represents a “true” application of Clifford algebras to graph theory.      

Triangularizing matrix polynomials

For an algebraically closed field F$\mathbb{F}$, we show that any matrix polynomial P(λ)∈F[λ]^n×m$P(\lambda )\in \mathbb{F}{[\lambda ]}^{n\times m}$, n?m$n?m$, can be reduced to triangular form, preserving the degree and the finite and infinite elementary divisors. We also characterize the real matrix polynomials that are triangularizable over the real numbers and show that those that are not triangularizable are quasi-triangularizable with diagonal blocks of sizes 1×1$1\times 1$ and 2×2$2\times 2$. The proofs we present solve the structured inverse problem of building up triangular matrix polynomials starting from lists of elementary divisors.     

Exact solution of linear equations usingP-adic expansions

Summary A method is described for computing the exact rational solution to a regular systemAx=b of linear equations with integer coefficients. The method involves: (i) computing the inverse (modp) ofA for some primep; (ii) using successive refinements to compute an integer vector such that (modp ^m ) for a suitably large integerm; and (iii) deducing the rational solutionx from thep-adic approximation . For matricesA andb with entries of bounded size and dimensionsn×n andn×1, this method can be implemented in timeO(n ³(logn)²) which is better than methods previously used.This research was supported in part by the Natural Sciences and Engineering Research Council of Canada (Grant No. A 7171)     

An algorithm for determining copositive matrices

In this paper, we present an algorithm of simple exponential growth called COPOMATRIX for determining the copositivity of a real symmetric matrix. The core of this algorithm is a decomposition theorem, which is used to deal with simplicial subdivision of on the standard simplex Δ_m, where each component of the vector β is −1, 0 or 1.     

A priori-Schranken für diskrete Lösungen monotoner Operatorgleichungen und Anwendungen

Summary Operator equationsTu=f are approximated by Galerkin's method, whereT is a monotone operator in the sense of Browder and Minty, so that existence results are available in a reflexive Banach spaceX. In a normed spaceY error estimates are established, which require a priori bounds for the discrete solutionsu _h in the norm of a suitable space . Sufficient conditions for the uniform boundedness u _{h Z} =O(1) ash0 are proved. Well-known error estimates in [3] for the special caseX=Y=Z are generalized by this. The theory is applied to quasilinear elliptic boundary value problems of order 2m in a bounded domain . The approximating subspaces are finite element spaces. Especially the caseX=W ₀ ^{m, p} (), 1<p<,Y=W ₀ ^{m. 2} (),Z=W ₀ ^{m. max (2,p)} ()W^m, () is treated. Some examples for 1<p<2 are considered. Forp2 a refined technique is introduced in the author's paper [7].

     

Error estimates for the numerical solution of a time-periodic linear parabolic problem

In this paper we consider the numerical solution of a time-periodic linear parabolic problem. We derive optimal order error estimates inL ₂() for approximate solutions obtained by discretizing in space by a Galerkin finite-element method and in time by single-step finite difference methods, using known estimates for the associated initial value problem. We generalize this approach and obtain error estimates for more general discretization methods in the norm of a Banach spaceB L ₂(), e.g.,B=H ₀ ¹ () orL (). Finally, we consider some computational aspects and give a numerical example.