Sparse convolution quadrature for time domain boundary integral formulations of the wave equation

S. A. Sauter Institut für Mathematik, Universität Zürich, Winterthurerstrasse 190, CH-8057 Zürich, Switzerland ^{Many important physical applications are governed by the waveequation. The formulation as time domain boundary integral equationsinvolves retarded potentials. For the numerical solution ofthis problem, we employ the convolution quadrature method forthe discretization in time and the Galerkin boundary elementmethod for the space discretization. We introduce a simple apriori cut-off strategy where small entries of the system matricesare replaced by zero. The threshold for the cut-off is determinedby an a priori analysis which will be developed in this paper.This analysis will also allow to estimate the effect of additionalperturbations such as panel clustering and numerical integrationon the overall discretization error. This method reduces thestorage complexity for time domain integral equations from O(M2N)to O(M2N logM), where N denotes the number of time steps andM is the dimension of the boundary element space.}     

三维非线性抛物型积分-微分方程的A.D.I.Galerkin方法及其分析

研究三维非线性抛物型积分-微分方程的A.D.I.Galerkin方法.通过交替方向,化三维为一维,简化计算;通过Galerkin法,保持高精度.成功处理了Volterra项的影响;对所提Galerkin及A.D.I.Galerkin格式给出稳定性和收敛性分析,得到最佳H1和L2模估计.     

Bernoulli measure on strings,and Thompson-Higman monoids

The Bernoulli measure on strings is used to define height functions for the dense R\mathcal{ R}- and L\mathcal{ L}-orders of the Thompson-Higman monoids M _k,1. The measure can also be used to characterize the D\mathcal{ D}-relation of certain submonoids of M _k,1. The computational complexity of computing the Bernoulli measure of certain sets, and in particular, of computing the R\mathcal{ R}- and L\mathcal{ L}-height of an element of M _k,1 is investigated.     

The Betti Numbers of the Free Loop Space of a Connected Sum

Let M₁ and M₂ be two simply connected closed manifolds of thesame dimension. It is proved that (1) if k is a coefficient field such that neither M₁ nor M₂has the same cohomology as a sphere, then the sequence (b_k)_k1of Betti numbers of the free loop space on M₁ #M₂ is unbounded; (2) if, moreover, the cohomology H*(M₁;k) is not generated asalgebra by only one element, then the sequence (b_k)_k1 has anexponential growth. Thanks to theorems of Gromoll and Meyer and of Gromov, thisimplies, in case 1, that there exist infinitely many closedgeodesics on M₁#M₂ for each Riemannian metric, and, in case2, that for a generic metric, the number of closed geodesicsof length t grows exponentially with t.     

Replacement of Factors by Subgroups in the Factorization of Abelian Groups

The above-titled paper of mine appeared in the Bulletin of theLondon Mathematical Society, 32 (2000) 297–304. Regrettably,there is a careless error in the proofs of Theorems 6 and 8.In line 6 of the proof of Theorem 6, it is claimed that a certainsubset must be a subgroup. For this to hold, the subset mustcontain the zero element. This need not be the case; the truededuction is that the subset is a coset, say M + h, of a subgroupM. Now M and M + h contain the same number of elements, andso the deduction that M has p elements is still correct. Similarly, in the proof of Theorem 8, the subgroup M_k must bereplaced by a coset M_k + h_k. This is the only change neededin this proof, since the sum M_k+h_k+(nBH) being direct impliesthat the sum M_k+(nBH) is also direct. Since the zero elementdoes belong to the sets (mAH) and (nBH), the statements aboutthese sets are correct. So the second paragraph of the Proofof Theorem 8 is correct, and is also a proof of Theorem 6. Now we present an example that, we hope, will clarify the situation,as well as showing that certain statements in the original ‘Proof’of Theorem 6 not only could be wrong but actually are wrong.The smallest numerical example occurs with p = 2, m = 3, n =5. Then G is a cyclic group of order 60, and may be representedas the integers modulo 60. Let A = {0, 1, 2, 3, 4} + {0, 15} and B = {0, 5, 10} + {0, 30}.It is easily verified that A + B = {0, 1,..., 59}. In the notationof Theorem 6, we see that H = {0, 15, 30, 45}, K = {0, 12, 24,36, 48}, L = {0, 20, 40}, and M = {0, 30}. Now we see that mA= {0, 3, 6, 9, 12} + {0, 45} M + K, and that nB = {0, 25, 50}+ {0, 30} M + L. We note, however, that A is a complete setof residues modulo 10; that is, that B can be replaced by M+ L.     

Existence of Feller Cocycles on a C*-Algebra

The quantum stochastic differential equation is considered on a unital C^*-algebra, with separablenoise dimension space. Necessary conditions on the matrix ofbounded linear maps for the existence of a completely positivecontractive solution are shown to be sufficient. It is knownthat for completely positive contraction processes, k satisfiessuch an equation if and only if k is a regular Markovian cocycle.‘Feller’ refers to an invariance condition analogousto probabilistic terminology if the algebra is thought of asa non-commutative topological space. 2000 Mathematics SubjectClassification 81S25, 46L07, 46L53, 47D06.     

Nearest Neighbour Searches and the Curse of Dimensionality

It is shown that efficiency of cut-off algorithms for nearestneighbour searches depends on the ratio of variance in a lowerbound space B to variance in the original space L. The usualchoice of a one dimensional B space fails for a high dimensionalL space because this ratio is then low. If the dimensionalityof B is about half that of L the equivalent of no more than75% of the full distance computations need be done, independentof the dimensionality of L space. If the variance in B spacecan be increased by either sorting or the principal componentstransformation performance is appreciably better.     

A semi-discretization method based on quartic splines for solving one-space-dimensional hyperbolic equations

In this paper, based on C³ quartic splines, a semi-discretization method containing two schemes is constructed to solve one-space-dimensional linear hyperbolic equations. It is shown that both schemes are unconditionally stable and their approximation orders are of O(k⁵+h⁴) and of O(k⁷+h⁴) with k and h being step sizes in time and space, respectively, which are much higher than those of other published schemes. A numerical example is presented and the results are compared with other published numerical results.     

Construction and Analysis of Lattice Boltzmann Methods Applied to a 1D Convection-Diffusion Equation

To solve the 1D (linear) convection-diffusion equation, we construct and we analyze two LBM schemes built on the D1Q2 lattice. We obtain these LBM schemes by showing that the 1D convection-diffusion equation is the fluid limit of a discrete velocity kinetic system. Then, we show in the periodic case that these LBM schemes are equivalent to a finite difference type scheme named LFCCDF scheme. This allows us, firstly, to prove the convergence in L ^∞ of these schemes, and to obtain discrete maximum principles for any time step in the case of the 1D diffusion equation with different boundary conditions. Secondly, this allows us to obtain most of these results for the Du Fort-Frankel scheme for a particular choice of the first iterate. We also underline that these LBM schemes can be applied to the (linear) advection equation and we obtain a stability result in L ^∞ under a classical CFL condition. Moreover, by proposing a probabilistic interpretation of these LBM schemes, we also obtain Monte-Carlo algorithms which approach the 1D (linear) diffusion equation. At last, we present numerical applications justifying these results.     

POLYNOMIAL NUMERICAL INDEX FOR SOME COMPLEX VECTOR-VALUED FUNCTION SPACES

We study the relation between the polynomial numerical indicesof a complex vector-valued function space and the ones of itsrange space. It is proved that the spaces C(K, X) and L(µ,X) have the same polynomial numerical index as the complex Banachspace X for every compact Hausdorff space K and every -finitemeasure µ, which does not hold any more in the real case.We give an example of a complex Banach space X such that, forevery k 2, the polynomial numerical index of order k of X isthe greatest possible, namely 1, while the one of X** is theleast possible, namely k^k/(1–k). We also give new examplesof Banach spaces with the polynomial Daugavet property, namelyL(µ, X) when µ is atomless, and C_w(K, X), C_w*(K,X*) when K is perfect.     

Higher string topology on general spaces

In this paper, I give a generalized analogue of the string topologyresults of Chas and Sullivan, and of Cohen and Jones. For afinite simplicial complex X and k 1, I construct a spectrumMaps(S^k, X)^S(X), which is obtained by taking a generalizationof the Spivak bundle on X (which however is not a stable spherebundle unless X is a Poincaré space), pulling back toMaps(S^k, X) and quotienting out the section at infinity. I showthat the corresponding chain complex is naturally homotopy equivalentto an algebra over the (k + 1)-dimensional unframed little diskoperad C_{k + 1}. I also prove a conjecture of Kontsevich, whichstates that the Quillen cohomology of a based C_k-algebra (inthe category of chain complexes) is equivalent to a shift ofits Hochschild cohomology, as well as prove that the operadC_*C_k is Koszul-dual to itself up to a shift in the derived category.This gives one a natural notion of (derived) Koszul dual C_*C_k-algebras.I show that the cochain complex of X and the chain complex of^k X are Koszul dual to each other as C_*C_k-algebras, and thatthe chain complex of Maps(S^k, X)^S(X) is naturally equivalentto their (equivalent) Hochschild cohomology in the categoryof C_* C_k-algebras. 2000 Mathematics Subject Classification 55P48(primary), 16E40, 55N45, 18D50 (secondary).     

A Version of the Poincare-Birkhoff-Witt Theorem

In this note I shall prove that if L is a finite-dimensionalLie algebra over a field F of characteristic zero which is generatedas an algebra by a set of elements {e₁, e₂,...,e_k}, then theuniversal enveloping algebra U(L) of L is linearly generatedby monomials spanned by the elements {e_i} of an a priori boundedwidth. As an application, a criterion of Kostant for a leftideal of U(L) to be of finite codimension is proved by purelyalgebraic means.     

An analysis of stability and convergence of a finite-difference discretization of a model parabolic PDE in 1D using a moving mesh

^{The aim of this paper is to investigate the stability and convergenceof time integration schemes for the solution of a semi-discretizationof a model parabolic problem in 1D using a moving mesh. Thespatial discretization is achieved using a second-order centralfinite-difference scheme. Using energy techniques we show thatthe backward Euler scheme is unconditionally stable in a mesh-dependentL₂-norm, independently of the mesh movement, but the Crank–Nicolson(CN) scheme is only conditionally stable. By identifying thediffusive and anti-diffusive effects caused by the mesh movement,we devise an adaptive -method that is shown to be unconditionallystable and asymptotically second-order accurate. Numerical experimentsare presented to back up the findings of the analysis.}     

Espaces Homogenes Principaux et Points de 2-Division de Courbes Elliptiques

Dans cet article, nous nous intéressons aux problèmesde structure galoisienne associés aux couples (E/L, a),où E désigne une courbe elliptique définiesur le corps de nombres L et a un endomorphisme de E. Si E està multiplication complexe, nous notons k le corps quadratiqueimaginaire dont l'anneau des entiers décrit End(E) etL une extension de k. Ainsi a est-il selon les cas un entieralgébrique de k ou un élément de Z.     

The Range of Possible Values of f(x)

The purpose of this paper is to explain how to compute the rangeof possible values of a function of one variable, f(x), givenvalues of the function at n distinct points x₁ < x₂ <... < x_M–1 < x_M, and given a finite bound on thekth derivative of f: ||f^(k)|| L, 1 k n.     

A bounded compactness theorem forL 1-embeddability of metric spaces in the plane

LetM=(W, d) be a metric space. LetL ¹ denote theL ¹ metric. AnL ¹-embedding ofM into Cartesiank-space ℝ ^k is a distance-preserving map from (W, d) into (ℝ ^k ,L ¹). Letc(k) be the smallest integer such that for every metric spaceM, M isL ¹-embeddable inR ^k iff everyc(k)-sized subspace ofM isL ¹-embeddable inR ^k. A special case of a theorem of Menger (see p. 94 of [5]) says thatc(1) exists and equals 4. We show thatc(2) exists and satisfies 6≦c(2)≦11. Whether or notc(k) exists for anyk≧3 is an open question. The research of S. M. Malitz was partially supported by NSF Grant CCR-8909953.     

Free Groups of Outer Commutator Varieties of Groups

If F is a free group, 1 < i j 2i and i k i + j + 1 thenF/[_j(F), _i(F), _k(F)] is residually nilpotent and torsion-free.This result is extended to 1 < i j 2i and i k 2i + 2j.It is proved that the analogous Lie rings, L/[L^j, Lⁱ, L^k] whereL is a free Lie ring, are torsion-free. Candidates are foundfor torsion in L/[L^j, Lⁱ, L^k] whenever k is the least of {i,j, k}, and the existence of torsion in L/[L^j, Lⁱ, L^k] is provedwhen i, j, k 5 and k is the least of {i, j, k}.     

The gradient iteration for approximation in reproducing kernel Hilbert spaces

Consider the bounded linear operator, L: F Z, where Z R^N andF are Hilbert spaces defined on a common field X. L is madeup of a series of N bounded linear evaluation functionals, L_i:F R. By the Riesz representation theorem, there exist functionsk(x_i, ^·) F : L_if = f, k(x_i, ^·)_F. The functions,k(x_i, ^·), are known as reproducing kernels and F is areproducing kernel Hilbert space (RKHS). This is a natural frameworkfor approximating functions given a discrete set of observations.In this paper the computational aspects of characterizing suchapproximations are described and a gradient method presentedfor iterative solution. Such iterative solutions are desirablewhen N is large and the matrix computations involved in thebasic solution become infeasible. This is also exactly the casewhere the problem becomes ill-conditioned. An iterative approachto Tikhonov regularization is therefore also introduced. Unlikeiterative solutions for the more general Hilbert space setting,the proofs presented make use of the spectral representationof the kernel.     

The Fast Numerical Solution of Very Large Elliptic Difference Schemes

Let L_kv_k = g_k be a system of difference equations discretizingan elliptic boundary value problem. Assume the system to be"very large", that means that the number of unknowns exceedsthe capacity of storage. We present a method for solving theproblem with much less storage requirement. For two-dimensionalproblems the size of the needed storage decreases from O(h^–2)to (or even O(h^–5/4)). The computational work increasesonly by a factor about six. The technique can be generalizedto nonlinear problems. The algorithm is also useful for computerswith a small number of parallel processors.     

A Note on a Maximal Function Over Arbitrary Sets of Directions

Let M_S be the universal maximal operator over unit vectors ofarbitrary directions. This operator is not bounded in L²(R²).We consider a sequence of operators over sets of finite equidistributeddirections converging to M_S. We provide a new proof of N. Katz'sbound for such operators. As a corollary, we deduce that M_Sis bounded from some subsets of L² to L². These subsets arecomposed of positive functions whose Fourier transforms havea logarithmic decay or which are supported on a disc. 1991 MathematicsSubject Classification 42B25.