Fast computations with the harmonic Poincaré–Steklov operators on nested refined meshes

In this paper we develop asymptotically optimal algorithms for fast computations with the discrete harmonic Poincaré–Steklov operators (Dirichlet–Neumann mapping) for interior and exterior problems in the presence of a nested mesh refinement. Our approach is based on the multilevel interface solver applied to the Schur complement reduction onto the nested refined interface associated with a nonmatching decomposition of a polygon by rectangular substructures. This paper extends methods from Khoromskij and Prössdorf (1995), where the finite element approximations of interior problems on quasi‐uniform grids have been considered. For both interior and exterior problems, the matrix–vector multiplication with the compressed Schur complement matrix on the interface is shown to have a complexity of the order O(N _r log³ N _u), where N_r = O((1 + p _r) N _u) is the number of degrees of freedom on the polygonal boundary under consideration, N _u is the boundary dimension of a finest quasi‐uniform level and p _r ⩾ 0 defines the refinement depth. The corresponding memory needs are estimated by O(N _r log^q N _u), where q = 2 or q = 3 in the case of interior and exterior problems, respectively.

     

Gibbs' phenomenon and arclength

The arclengths of the graphs Γ(s_N(f)) of the partial sums s_N(f) of the Fourier series of a piecewise smooth function f with a jump discontinuity grow at the rate O(logN). This problem does not arise if f is continuous, and can be removed by using the standard summability methods.     

Modified nodal cubic spline collocation for biharmonic equations

We formulate a modified nodal cubic spline collocation scheme for the solution of the biharmonic Dirichlet problem on the unit square. We prove existence and uniqueness of a solution of the scheme and show how the scheme can be solved on an N × N uniform partition of the square at a cost O(N ² log₂ N + mN ²) using fast Fourier transforms and m iterations of the preconditioned conjugate gradient method. We demonstrate numerically that m proportional to log₂ N guarantees the desired convergence rates. Numerical results indicate the fourth order accuracy of the approximations in the global maximum norm and the fourth order accuracy of the approximations to the first order partial derivatives at the partition nodes.      

A capacitance matrix method for Dirichlet problem on polygon region

Summary An efficient algorithm for the solution of linear equations arising in a finite element method for the Dirichlet problem is given. The cost of the algorithm is proportional toN ²log₂ N (N=1/h) where the cost of solving the capacitance matrix equations isNlog₂ N on regular grids andN ^3/2log₂ N on irregular ones.     

On a Problem of Erd?s Involving the Largest Prime Factor of n

Let P(n) denote the largest prime factor of an integer n (N(x) = x (2+O(?{log₂ x/logx} ) )ò₂^xr(logx/logt) [(logt)/(t²)] d t,N(x) = x \left(2+O\left(\sqrt{\log_{2}\,x/\!\log x}\,\right) \right)\int_2^x\rho(\log x/\!\log t) {\log t\over t^2} {\rm d} t,     

Euclidean minimum spanning trees and bichromatic closest pairs

We present an algorithm to compute a Euclidean minimum spanning tree of a given setS ofN points inE ^d in timeO(F _d (N,N) log ^d N), whereF _d (n,m) is the time required to compute a bichromatic closest pair amongn red andm green points inE ^d . IfF _d (N,N)=Ω(N ^1+ε), for some fixed ɛ>0, then the running time improves toO(F _d (N,N)). Furthermore, we describe a randomized algorithm to compute a bichromatic closest pair in expected timeO((nm logn logm)^2/3+m log² n+n log² m) inE ₃, which yields anO(N ^4/3 log^4/3 N) expected time, algorithm for computing a Euclidean minimum spanning tree ofN points inE ³. Ind≥4 dimensions we obtain expected timeO((nm)^{1−1/([d/2]+1)+ε}+m logn+n logm) for the bichromatic closest pair problem andO(N ^{2−2/([d/2]+1)ε}) for the Euclidean minimum spanning tree problem, for any positive ɛ. The first, second, and fourth authors acknowledge support from the Center for Discrete Mathematics and Theoretical Computer Science (DIMACS), a National Science Foundation Science and Technology Center under NSF Grant STC 88-09648. The second author's work was supported by the National Science Foundation under Grant CCR-8714565. The third author's work was supported by the Deutsche Forschungsgemeinschaft under Grant A1 253/1-3, Schwerpunktprogramm “Datenstrukturen und effiziente Algorithmen”. The last two authors' work was also partially supported by the ESPRIT II Basic Research Action of the EC under Contract No. 3075 (project ALCOM).     

A fourth order finite difference method for the Dirichlet biharmonic problem

Using the coupled approach, we formulate a fourth order finite difference scheme for the solution of the Dirichlet biharmonic problem on the unit square. On an N × N uniform partition of the square the scheme is solved at a cost O(N ² log₂ N)+m8N ² using fast Fourier transforms and m iterations of the preconditioned conjugate gradient method. Numerical tests confirm the fourth order accuracy of the scheme at the partition nodes with m proportional to log₂ N.     

A fast transform for spherical harmonics

Spherical harmonics arise on the sphere S² in the same way that the (Fourier) exponential functions {e^ik}k arise on the circle. Spherical harmonic series have many of the same wonderful properties as Fourier series, but have lacked one important thing: a numerically stable fast transform analogous to the Fast Fourier Transform (FFT). Without a fast transform, evaluating (or expanding in) spherical harmonic series on the computer is slow—for large computations probibitively slow. This paper provides a fast transform.For a grid ofO(N²) points on the sphere, a direct calculation has computational complexityO(N⁴), but a simple separation of variables and FFT reduce it toO(N³) time. Here we present algorithms with timesO(N^5/2 log N) andO(N²(log N)²). The problem quickly reduces to the fast application of matrices of associated Legendre functions of certain orders. The essential insight is that although these matrices are dense and oscillatory, locally they can be represented efficiently in trigonometric series.     

Efficient Reconstruction of Functions on the Sphere from Scattered Data

Recently, fast and reliable algorithms for the evaluation of spherical harmonic expansions have been developed. The corresponding sampling problem is the computation of Fourier coefficients of a function from sampled values at scattered nodes. We consider a least squares approximation and an interpolation of the given data. Our main result is that the rate of convergence of the two proposed iterative schemes depends only on the mesh norm and the separation distance of the nodes. In conjunction with the nonequispaced FFT on the sphere, the reconstruction of N² Fourier coefficients from M reasonably distributed samples is shown to take O(N² log² N + M) floating point operations. Numerical results support our theoretical findings.     

A fast algorithm for nonequispaced Fourier transforms on the rotation group

In this paper we present algorithms to calculate the fast Fourier synthesis and its adjoint on the rotation group SO(3) for arbitrary sampling sets. They are based on the fast Fourier transform for nonequispaced nodes on the three-dimensional torus. Our algorithms evaluate the SO(3) Fourier synthesis and its adjoint, respectively, of B-bandlimited functions at M arbitrary input nodes in O(M+B⁴)\mathcal O(M+B^4) or even O(M + B³ log² B)\mathcal O(M + B^3 \log^2 B) flops instead of O(MB³)\mathcal O(MB^3). Numerical results will be presented establishing the algorithm’s numerical stability and time requirements.     

FFTs for the 2-Sphere-Improvements and Variations

Earlier work by Driscoll and Healy has produced an efficient algorithm for computing the Fourier transform of band-limited functions on the 2-sphere. In this article we present a reformulation and variation of the original algorithm which results in a greatly improved inverse transform, and consequent improved convolution algorithm for such functions. All require at most O(N log² N) operations where N is the number of sample points. We also address implementation considerations and give heuristics for allowing reliable and computationally efficient floating point implementations of slightly modified algorithms. These claims are supported by extensive numerical experiments from our implementation in C on DEC, HP, SGI and Linux Pentium platforms. These results indicate that variations of the algorithm are both reliable and efficient for a large range of useful problem sizes. Performance appears to be architecture-dependent. The article concludes with a brief discussion of a few potential applications.     

A parallel algorithm for generating multiple ordering spanning trees in undirected weighted graphs

1.IntroductionLetG=(V,E,W)beaconnected,weightedandundirectedgraph,VeEE,w(e)(相似文献   

A locality-preserving cache-oblivious dynamic dictionary

This paper presents a simple dictionary structure designed for a hierarchical memory. The proposed data structure is cache-oblivious and locality-preserving. A cache-oblivious data structure has memory performance optimized for all levels of the memory hierarchy even though it has no memory-hierarchy-specific parameterization. A locality-preserving dictionary maintains elements of similar key values stored close together for fast access to ranges of data with consecutive keys.The data structure presented here is a simplification of the cache-oblivious B-tree of Bender, Demaine, and Farach-Colton. The structure supports search operations on N data items using O(log_BN+1) block transfers at a level of the memory hierarchy with block size B. Insertion and deletion operations use O(log_BN+log²N/B+1) amortized block transfers. Finally, the data structure returns all k data items in a given search range using O(log_BN+k/B+1) block transfers.This data structure was implemented and its performance was evaluated on a simulated memory hierarchy. This paper presents the results of this simulation for various combinations of block and memory sizes.     

Geometric Pattern Matching in d -Dimensional Space

We show that, using the L _∞ metric, the minimum Hausdorff distance under translation between two point sets of cardinality n in d -dimensional space can be computed in time O(n ^(4d-2)/3 log ² n) for 3 < d 8, and in time O(n ^5d/4 log ² n) for any d > 8 . Thus we improve the previous time bound of O(n ^2d-2 log ² n) due to Chew and Kedem. For d=3 we obtain a better result of O(n ³ log ² n) time by exploiting the fact that the union of n axis-parallel unit cubes can be decomposed into O(n) disjoint axis-parallel boxes. We prove that the number of different translations that achieve the minimum Hausdorff distance in d -space is . Furthermore, we present an algorithm which computes the minimum Hausdorff distance under the L ₂ metric in d -space in time , for any δ > 0. Received March 17, 1997, and in revised form January 19, 1998.     

Asymptotic enumeration ofN-free partial orders

LetN(n) andN ^* (n) denote, respectively, the number of unlabeled and labeledN-free posets withn elements. It is proved thatN(n)=2 ^{n logn+o(n logn)} andN ^*(n)=2^{2n logn+o(n logn)}. This is obtained by considering the class ofN-free interval posets which can be easily counted.     

About strongly polynomial time algorithms for quadratic optimization over submodular constraints

We present new strongly polynomial algorithms for special cases of convex separable quadratic minimization over submodular constraints. The main results are: an O(NM log(N ²/M)) algorithm for the problemNetwork defined on a network onM arcs andN nodes; an O(n logn) algorithm for thetree problem onn variables; an O(n logn) algorithm for theNested problem, and a linear time algorithm for theGeneralized Upper Bound problem. These algorithms are the best known so far for these problems. The status of the general problem and open questions are presented as well.This research has been supported in part by ONR grant N00014-91-J-1241.Corresponding author.     

Approximate Nearest Neighbor Queries Revisited

This paper proposes new methods to answer approximate nearest neighbor queries on a set of n points in d -dimensional Euclidean space. For any fixed constant d , a data structure with O( ^(1-d)/2 n log n) preprocessing time and O( ^(1-d)/2 log n) query time achieves an approximation factor 1+ for any given 0 < < 1; a variant reduces the -dependence by a factor of ^-1/2 . For any arbitrary d , a data structure with O(d ² n log n) preprocessing time and O(d ² log n) query time achieves an approximation factor O(d ^3/2 ) . Applications to various proximity problems are discussed. Received May 28, 1997, and in revised form March 4, 1998.     

On Fast Computations with the Inverse to Harmonic Potential Operators via Domain Decomposition

In this paper a method for fast computations with the inverse to weakly singular, hypersingular and double layer potential boundary integral operators associated with the Laplacian on Lipschitz domains is proposed and analyzed. It is based on the representation formulae suggested for above-mentioned boundary operations in terms of the Poincare-Steklov interface mappings generated by the special decompositions of the interior and exterior domains. Computations with the discrete counterparts of these formulae can be efficiently performed by iterative substructuring algorithms provided some asymptotically optimal techniques for treatment of interface operators on subdomain boundaries. For both two- and three-dimensional cases the computation cost and memory needs are of the order O(N log^p N) and O(N log² N), respectively, with 1 ≤ p ≤ 3, where N is the number of degrees of freedom on the boundary under consideration (some kinds of polygons and polyhedra). The proposed algorithms are well suited for serial and parallel computations.     

On the rate of convergence to normality for generalized linear rank statistics

Summary A generalized linear rank statistic is introduced to include, as special cases, both signed as well as unsigned linear rank statistics. For this statistic, the rate of convergence to asymptotic normality is investigated. It is shown that this rate is of orderO(N ^−1/2 logN) if the score generating function ϕ is twice differentiable, and it is of orderO(N ^−1/2) if the second derivative of ϕ satisfies Lipschitz's condition of order ≧1/2. The results obtained extend as well as generalize most of the earlier results obtained in this direction.     

Analysis of Carry Propagation in Addition: An Elementary Approach

Our goal in this paper is to analyze carry propagation in addition using only elementary methods (that is, those not involving residues, contour integration, or methods of complex analysis). Our results concern the length of the longest carry chain when two independent uniformly distributed n-bit numbers are added. First, we show using just first- and second-moment arguments that the expected length C_n of the longest carry chain satisfies C_n = log₂n + O(1). Second, we use a sieve (inclusion–exclusion) argument to give an exact formula for C_n. Third, we give an elementary derivation of an asymptotic formula due to Knuth, C_n = log₂n + Φ(log₂ n) + O((logn)⁴/n), where Φ(ν) is a bounded periodic function of ν, with period 1, for which we give both a simple integral expression and a Fourier series. Fourth, we give an analogous asymptotic formula for the variance V_n of the length of the longest carry chain: V_n = Ψ(log₂ n) + O((logn)⁵/n), where Ψ(ν) is another bounded periodic function of ν, with period 1. Our approach can be adapted to addition with the “end-around” carry that occurs in the sign-magnitude and 1s-complement representations. Finally, our approach can be adapted to give elementary derivations of some asymptotic formulas arising in connection with radix-exchange sorting and collision-resolution algorithms, which have previously been derived using contour integration and residues.