A Fast Galerkin Algorithm for Singular Integral Equations

A recent paper (Delves, 1977) described a variant of the Galerkinmethod for linear Fredholm integral equations of the secondkind with smooth kernels, for which the total solution timeusing N expansion functions is (N² ln N) compared with the standardGalerkin count of (N³). We describe here a modification of thismethod which retains this operations count and which is applicableto weakly singular Fredholm equations of the form where K₀(x, y) is a smooth kernel and Q contains a known singularity.Particular cases treated in detail include Fredholm equationswith Green's function kernels, or with kernels having logarithmicsingularities; and linear Volterra equations with either regularkernels or of Abel type. The case when g(x) and/or f(x) containsa known singularity is also treated. The method described yieldsboth a priori and a posteriori error estimates which are cheapto compute; for smooth kernels (Q = 1) it yields a modifiedform of the algorithm described in Delves (1977) with the advantagethat the iterative scheme required to solve the equations in(N²) operations is rather simpler than that given there.     

Arbitrary rank jumps for A-hypergeometric systems through Laurent polynomials

We investigate the solution space of hypergeometric systemsof differential equations in the sense of Gel’fand, Graev,Kapranov and Zelevinski. For any integer d 2, we constructa matrix A_(d) ^{d x 2d} and a parameter vector ß_(d)such that the holonomic rank of the A-hypergeometric systemH_A(d)(ß_(d)) exceeds the simplicial volume vol(A_(d))by at least d – 1. The largest previously known gap betweenrank and volume was 2. Our construction gives evidence to the general observation thatrank jumps seem to go hand in hand with the existence of multipleLaurent (or Puiseux) polynomial solutions.     

A Fast Implementation of the Global Element Method

A straightforward implementation of the Global Element Method(Delves & Hall, 1979) for two-dimensional partial differentialequations has an operation count: Set up equations: (MN⁶); solve: (M³N⁶) where M is the number of elements and N the number of one-dimensionalexpansion functions used in each element. We describe here analternative implementation in which both of these counts arereduced to (MN⁴). The method used generalizes to p dimensions, with operationcount (MN^2p) compared with the "standard" count (MP^3p + M³N^3p).     

A Relation between Hausdorff Dimension and a Condition on Time Sets for the Image by the Brownian Sheet to Possess Interior Points

We prove that if W_{N, d} is a Brownian sheet mapping to R^d and E is a set in (0, )^N of Hausdorff dimensiongreater than , then for almost every rotation about a point x and translation _x such that _x(E) (0, )^N, the set _x(E) is such that almost surely W(E) containsinterior points. The techniques are adapted from Kahane andRosen and generalize to higher dimensional time and range.     

Eigenvectors of Order-Preserving Linear Operators

Suppose that K is a closed, total cone in a real Banach spaceX, that A:XX is a bounded linear operator which maps K intoitself, and that A' denotes the Banach space adjoint of A. Assumethat r, the spectral radius of A, is positive, and that thereexist x₀0 and m1 with A^m(x₀)=r^mx₀ (or, more generally, thatthere exist x₀(–K) and m1 with A^m(x₀)r^mx₀). If, in addition,A satisfies some hypotheses of a type used in mean ergodic theorems,it is proved that there exist uK–{0} and K'–{0}with A(u)=ru, A'()=r and (u)>0. The support boundary of Kis used to discuss the algebraic simplicity of the eigenvaluer. The relation of the support boundary to H. Schaefer's ideasof quasi-interior elements of K and irreducible operators Ais treated, and it is noted that, if dim(X)>1, then thereexists an xK–{0} which is not a quasi-interior point.The motivation for the results is recent work of Toland, whoconsidered the case in which X is a Hilbert space and A is self-adjoint;the theorems in the paper generalize several of Toland's propositions.     

On the Structure of the Moving Finite-element Equations

Address from 1st April 1985, School of Mathematics, Universityof Bristol, University Walk, Bristol BS8 1TW. The morning finite-element method for evolutionary partial differentialequations leads to a coupled non-linear system of ordinary differentialequations in time, with a coefficien matrix A, say, for thetime derivaties, We show for linear elements in any number ofdimensions, A can be written in the form M^TCM, where the matrixC depends solely on the mesh geometry and the matrix M on thegradient of the section, As a simple consequence we show thatA is singular only in the cases (i) element degeneracy () and (ii) collinearity of nodes (M not out of fullrank). We give constructions for the inversion of A in all cases. In one dimension, if A is non-singular, it has a simple explicitinverse. If A is singular we replace it by reduced matrix A^*.It can be shown that every case the spectral radius of the Jacobiiteration matrix ia ?and that A or A^* can be efficiently invertedby conjugate gradient methods. Finally, we discuss the applicability of these arguments tosystem of equations in any number of dimensions.     

C*-Algebras with Dense Nilpotent Subalgebras

In a beautiful result, Herrero (D. A. Herrero, ‘Normallimits of nilpotent operators’, Indiana Univ. Math. J.23 (1973/74) 1097–1108) showed that a normal operatoron l² lies in the closure of the set of nilpotent operatorsif and only if its spectrum is connected and contains zero.In the quest for an automatic continuity result for algebrahomomorphisms between C* -algebras, Dales showed that, if adiscontinuous algebra homomorphism : A u exists between C*-algebrasA and u, and if (A) is dense in u, then there is a C*-algebrau₂ with a dense subalgebra N u² such that every x N is quasinilpotent(see p. 685 of H. G. Dales, Banach algebras and automatic continuity,London Mathematical Society Monographs 24, Oxford UniversityPress, 2001). (A discontinuous homomorphism ₂: A₂ u₂ can bedefined with the same basic properties as , but the revisedtarget space u₂ has a dense subalgebra consisting of quasinilpotentelements.) As remarked by Dales, no such C*-algebra was thenknown; but here we present one. Indeed, using the full powerof Herrero's result, one may arrange that every x N is nilpotent.The C*-algebra is constructed in a ‘neat’ way; itis most naturally constructed as a non-separable, concrete C*-algebraof operators on a separable Hilbert space K but one can arrangethat the algebra u itself be separable if desired. 2000 MathematicsSubject Classification 47C15, 46H40 (primary), 47A10, 46L06,46L05, 46H35 (secondary).     

Rado Partition Theorem for Random Subsets of Integers

For an l x k matrix A = (a_ij) of integers, denote by L(A) thesystem of homogenous linear equations a_i1x₁ + ... + a_ikx_k =0, 1 i l. We say that A is density regular if every subsetof N with positive density, contains a solution to L(A). Fora density regular l x k matrix A, an integer r and a set ofintegers F, we write if for any partition F = F₁ ... F_r there exists i {1, 2,..., r} and a column vector x such that Ax = 0 and all entriesof x belong to F_i. Let [n]_N be a random N-element subset of{1, 2, ..., n} chosen uniformly from among all such subsets.In this paper we determine for every density regular matrixA a parameter = (A) such that lim_n P([n]_N (A)_r)=0 if N =O(n) and 1 if N = (n). 1991 Mathematics Subject Classification:05D10, 11B25, 60C05     

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.     

Reducibility of Nonautonomous Linear Differential Equations

A linear autonomous system of differential equations =Ax can be transformed to its Jordan normalform, that is, the transformed system is in block diagonal formand the blocks correspond to different eigenvalues. This resultis generalized to arbitrary nonautonomous linear systems =A(t)x with a locally integrable matrix functionA:R R^NxN.     

On Positive Multipeak Solutions of a Nonlinear Elliptic Problem

In this paper we continue our investigation in [5, 7, 8] onmultipeak solutions to the problem –²u+u=Q(x)|u|^q–2u, xR^N, uH¹(R^N) (1.1) where = ^N_i=1²/x²_i is the Laplace operator in R^N, 2 < q < for N = 1, 2, 2 < q < 2N/(N–2) for N3, and Q(x)is a bounded positive continuous function on R^N satisfying thefollowing conditions. (Q₁) Q has a strict local minimum at some point x₀R^N, that is,for some > 0 Q(x)>Q(x₀) for all 0 < |x–x₀| < . (Q₂) There are constants C, > 0 such that |Q(x)–Q(y)|C|x–y| for all |x–x₀| , |y–y₀| . Our aim here is to show that corresponding to each strict localminimum point x₀ of Q(x) in R^N, and for each positive integerk, (1.1) has a positive solution with k-peaks concentratingnear x₀, provided is sufficiently small, that is, a solutionwith k-maximum points converging to x₀, while vanishing as 0 everywhere else in R^N.     

On the division of polynomial matrices

The main purpose of this paper is to determine two new algorithmsfor the division of the polynomial matrix B(s) R[s]^pxq by A(s) R[s]^pxp (a) based on the Laurent matrix expansion at s = =of the inverse of A(s), i.e. A(s)^–1, and (b) in a waysimilar to the one presented by Gantmacher (1959).     

An infinite Family of 4-Arc-Transitive Cubic Graphs Each with Girth 12

If p is any prime, and is that automorphism of the group SL(3,p) which takes each matrix to the transpose of its inverse,then there exists a connected trivalent graph (p) on vertices with the split extensionSL(3, p) as a group of automorphisms acting regularly on its4-arcs. In fact if p 3 then this group is the full automorphismgroup of (p), while the graph (3) is 5-arc-transitive with fullautomorphism group SL(3,3)0 x C₂. The girth of (p) is 12, exceptin th case p = 2 (where the girth is 6). Furthermore, in allcases (p) is bipartite, with SL(3, p) fixing each part. Alsowhen p 1 mod 3 the graph (p) is a triple cover of another trivalentgraph, which has automorphism group PSL(3, p)0 acting regularlyon its 4-arcs. These claims are proved using elementary theoryof symmetric graphs, together with a suitable choice of threematrices which generate SL(3, Z). They also provide a proofthat the group 4⁺(a¹²) described by Biggs in Computational grouptheor(ed. M. Atkinson) is infinite.     

A separation property of the zeros of Eisenstein series for SL(2, Z)

Let E_k(z) be the Eisenstein series with weight k for the modulargroup SL(2, ). We prove that the zeros of E_k(eⁱ) interlace withthe zeros of E_k+12(eⁱ) on /2 < < 2/3. That is, any zeroof E_k(eⁱ) lies between two consecutive zeros of E_k+12(eⁱ) on/2 < < 2/3.     

Intertwining Maps from Certain Group Algebras

In [17, 18, 19], we began to investigate the continuity propertiesof homomorphisms from (non-abelian) group algebras. Alreadyin [19], we worked with general intertwining maps [3, 12]. Thesemaps not only provide a unified approach to both homomorphismsand derivations, but also have some significance in their ownright in connection with the cohomology comparison problem [4]. The present paper is a continuation of [17, 18, 19]; this timewe focus on groups which are connected or factorizable in thesense of [26]. In [26], G. A. Willis showed that if G is a connectedor factorizable, locally compact group, then every derivationfrom L¹(G) into a Banach L¹(G)-module is automatically continuous.For general intertwining maps from L¹(G), this conclusion isfalse: if G is connected and, for some nN, has an infinite numberof inequivalent, n-dimensional, irreducible unitary representations,then there is a discontinuous homomorphism from L¹(G into aBanach algebra by [18, Theorem 2.2] (provided that the continuumhypothesis is assumed). Hence, for an arbitrary intertwiningmap from L¹(G), the best we can reasonably hope for is a resultasserting the continuity of on a ‘large’, preferablydense subspace of L¹(G). Even if the target space of is a Banachmodule (which implies that the continuity ideal I() of is closed),it is not a priori evident that is automatically continuous:the proofs of the automatic continuity theorems in [26] relyon the fact that we can always confine ourselves to restrictionsto L¹(G) of derivations from M(G) [25, Lemmas 3.1 and 3.4].It is not clear if this strategy still works for an arbitraryintertwining map from L¹(G) into a Banach L¹(G)-module.     

On the Existence of Extremals for the Sobolev Trace Embedding Theorem with Critical Exponent

In this paper, the existence problem is studied for extremalsof the Sobolev trace inequality W^1,p()L^p*(), where is a boundedsmooth domain in R^N, p*=p(N–1)/(N–p), is the criticalSobolev exponent, and 1 < p < N. 2000 Mathematics SubjectClassification 35J65 (primary), 35B33 (secondary).     

Projective Modules over the Non-Commutative Sphere

The positive cone of the K₀-group of the non-commutative sphereB is explicitly determined by means of the four basic unboundedtrace functionals discovered by Bratteli, Elliott, Evans andKishimoto. The C*-algebra B is the crossed product A x Z₂ ofthe irrational rotation algebra A by the flip automorphism defined on the canonical unitary generators U, V by (U) = U*,(V) = V*, where VU = e²ⁱ UV and is an irrational real number.This result combined with Rieffel's cancellation techniquesis used to show that cancellation holds for all finitely generatedprojective modules over B. Subsequently, these modules are determinedup to isomorphism as finite direct sums of basic modules. Italso follows that two projections p and q in a matrix algebraover B are unitarily equivalent if, and only if, their vectortraces are equal: [p] = [q]. These results will have the following ramifications. They areused (elsewhere) to show that the flip automorphism on A isan inductive limit automorphism with respect to the basic buildingblock construction of Elliott and Evans for the irrational rotationalgebra. This will, in turn, yield a two-tower proof of thefact that B is approximately finite dimensional, first provedby Bratteli and Kishimoto.     

Fast evaluation of polyharmonic splines in three dimensions

M. J. D. Powell ^{This paper concerns the fast evaluation of radial basis functions.It describes the mathematics of hierarchical and fast multipolemethods for fast evaluation of splines of the form where is a positive integer andp is a low-degree polynomial. Splines s of this form are polyharmonicsplines in 3 and have been found to be very useful for providingsolutions to scattered data interpolation problems in 3. Asit is now well known, hierarchical methods reduce the incrementalcost of a single extra evaluation from O(N) to O(log N) operationsand reduce the cost of a matrix–vector product (evaluationof s at all the centres) from O(N2) to O(N log N) operations.We give appropriate far- and near-field expansions, togetherwith error estimates, uniqueness theorems and translation formulae.A hierarchical code based on these formulae is detailed andsome numerical results are given.}     

Isomorphisms between Semisimple Weighted Measure Algebras

It is shown that, if is an isomorphism between semisimple weightedmeasure algebras M(w₁) and M(w₂), then maps L¹(R⁺, w₁) ontoL¹(R⁺, w₂). This is used to describe all the automorphisms ofM(R⁺, w). A necessary and sufficient condition is given forM(w₁) and M(w₂) to be isomorphic.     

The Effects of Rounding Error on an Algorithm for Downdating a Cholesky Factorization

Let the positive definite matrix A have a Cholesky factorizationA= R^TR. For a given vector xsuppose that ? =A - xx^T has a Choleskyfactorization ? = ^T.This paper considers an algorithm for computing from R and x and an extension for removing a row from the QR factorizationof a regression problem. It is shown that the algorithm is stablein the presence of rounding errors. However, it is also shownthat the matrix can be a very ill-conditioned function of R and x.