Spherical interpolation using the partition of unity method: An efficient and flexible algorithm

An efficient and flexible algorithm for the spherical interpolation of large scattered data sets is proposed. It is based on a partition of unity method on the sphere and uses spherical radial basis functions as local approximants. This technique exploits a suitable partition of the sphere into a number of spherical zones, the construction of a certain number of cells such that the sphere is contained in the union of the cells, with some mild overlap among the cells, and finally the employment of an optimized spherical zone searching procedure. Some numerical experiments show the good accuracy of the spherical partition of unity method and the high efficiency of the algorithm.     

Asymptotic properties of some triangulations of the sphere

In this paper we analyse a method for triangulating the sphere originally proposed by Baumgardner and Frederickson in 1985. The method is essentially a refinement procedure for arbitrary spherical triangles that fit into a hemisphere. Refinement is carried out by dividing each triangle into four by introducing the midpoints of the edges as new vertices and connecting them in the usual ‘red’ way. We show that this process can be described by a sequence of piecewise smooth mappings from a reference triangle onto the spherical triangle. We then prove that the whole sequence of mappings is uniformly bi-Lipschitz and converges uniformly to a non-smooth parameterization of the spherical triangle, recovering the Baumgardner and Frederickson spherical barycentric coordinates. We also prove that the sequence of triangulations is quasi-uniform, that is, areas of triangles and lengths of the edges are roughly the same at each refinement level. Some numerical experiments confirm the theoretical results.     

Achieving accuracy and efficiency in spherical modelling of real data

In this paper, a hybrid approximation method on the sphere is analysed. As interpolation scheme, we consider a partition of unity method, such as the modified spherical Shepard method, which uses zonal basis functions plus spherical harmonics as local approximants. The associated algorithm is efficiently implemented and works well also when the amount of data is very large, as it is based on an optimized searching procedure. Locality of the method guarantees stability in numerical computations, and numerical results show good accuracy. Moreover, we aimed to discuss preservation of such features when the method and the related algorithm are applied to experimental data. To achieve this purpose, we considered the Magnetic Field Satellite data. The goal was reached, as efficiency and accuracy are maintained on several sets of real data. Copyright © 2013 John Wiley & Sons, Ltd.     

Binary weighted essentially non-oscillatory (BWENO) approximation

Weighted essentially non-oscillatory (WENO) schemes have been mainly used for solving hyperbolic partial differential equations (PDEs). Such schemes are capable of high order approximation in smooth regions and non-oscillatory sharp resolution of discontinuities. The base of the WENO schemes is a non-oscillatory WENO approximation procedure, which is not necessarily related to PDEs. The typical WENO procedures are WENO interpolation and WENO reconstruction. The WENO algorithm has gained much popularity but the basic idea of approximation did not change much over the years. In this paper, we first briefly review the idea of WENO interpolation and propose a modification of the basic algorithm. New approximation should improve basic characteristics of the approximation and provide a more flexible framework for future applications. New WENO procedure involves a binary tree weighted construction that is based on key ideas of WENO algorithm and we refer to it as the binary weighted essentially non-oscillatory (BWENO) approximation. New algorithm comes in a rational and a polynomial version. Furthermore, we describe the WENO reconstruction procedure, which is usually involved in the numerical schemes for hyperbolic PDEs, and propose the new reconstruction procedure based on the described BWENO interpolation. The obtained numerical results show that the newly proposed procedures perform very well on the considered test examples.     

A Tree Algorithm for Isotropic Finite Elements on the Sphere

The earth's surface is an almost perfect sphere. Deviations from its spherical shape are less than 0.4% of its radius and essentially arise from its rotation. All equipotential surfaces are nearly spherical, too. In consequence, multiscale modeling of geoscientifically relevant data on the sphere plays an important role. In this paper, we deal with isotropic kernel functions showing a local support (briefly called isotropic finite elements) for reconstructing square-integrable functions on the sphere. An essential tool is the concept of multiresolution analysis by virtue of the spherical up function. Because the up function is built by an infinite convolution product, we do not know an explicit representation of it. However, the tree algorithm for the multiresolution analysis based on the up functions can be formulated by convolutions of isotropic kernels of low-order polynomial structure. For these kernels, we are able to find an explicit representation, so that the tree algorithm can be implemented efficiently.     

Highly effective stable evaluation of bandlimited functions on the sphere

An algorithm for fast and accurate evaluation of band-limited functions at many scattered points on the unit 2-d sphere is developed. The algorithm is based on trigonometric representation of spherical harmonics in spherical coordinates and highly localized tensor-product trigonometric kernels (needlets). It is simple, fast, local, memory efficient, numerically stable and with guaranteed accuracy. Comparison of this algorithm with other existing algorithms in the literature is also presented.     

An efficient algorithm for large scale global optimization of continuous functions

A fast descent algorithm, resorting to a “stretching” function technique and built on one hybrid method (GRSA) which combines simulated annealing (SA) algorithm and gradient based methods for large scale global optimizations, is proposed. Unlike the previously proposed method in which the original objective functions remain unchanged during the whole course of optimization, the new method firstly constructs an auxiliary function on one local minimizer obtained by gradient based methods and then SA is executed on this constructed auxiliary function instead of on the original objective function in order that we can improve the jumping ability of SA algorithm to escape from the currently discovered local minimum to a better one from which the gradient based methods restart a new local search. The above procedure is repeated until a global minimum is detected. In addition, corresponding to the adopted “stretching” technique, a new next trial point generating scheme is designed. It is verified by simulation especially on large scale problems that the convergence speed is greatly accelerated, which is its main difference from many other reported methods that mostly cope with functions with less than 50 variables and does not apply to large scale optimization problems. Furthermore, the new algorithm functions as a global optimization procedure with a high success probability and high solution precision.     

Fully discrete spectral boundary integral methods for Helmholtz problems on smooth closed surfaces in ${\mathbb R}^3$

Summary. In this paper we describe and analyse a class of spectral methods, based on spherical polynomial approximation, for second-kind weakly singular boundary integral equations arising from the Helmholtz equation on smooth closed 3D surfaces diffeomorphic to the sphere. Our methods are fully discrete Galerkin methods, based on the application of special quadrature rules for computing the outer and inner integrals arising in the Galerkin matrix entries. For the outer integrals we use, for example, product-Gauss rules. For the inner integrals, a variant of the classical product integration procedure is employed to remove the singularity arising in the kernel. The key to the analysis is a recent result of Sloan and Womersley on the norm of discrete orthogonal projection operators on the sphere. We prove that our methods are stable for continuous data and superalgebraically convergent for smooth data. Our theory includes as a special case a method closely related to one of those proposed by Wienert (1990) for the fast computation of direct and inverse acoustic scattering in 3D. Received May 29, 2000 / Revised version received March 26, 2001/ Published online December 18, 2001     

Morphological Component Analysis and Inpainting on the Sphere: Application in Physics and Astrophysics

Morphological Component Analysis (MCA) is a new method which takes advantage of the sparse representation of structured data in large overcomplete dictionaries to separate features in the data based on the diversity of their morphology. It is an efficient technique in such problems as separating an image into texture and piecewise smooth parts or for inpainting applications. The MCA algorithm consists of an iterative alternating projection and thresholding scheme, using a successively decreasing threshold towards zero with each iteration. In this article, the MCA algorithm is extended to the analysis of spherical data maps as may occur in a number of areas such as geophysics, astrophysics or medical imaging. Practically, this extension is made possible thanks to the variety of recently developed transforms on the sphere including several multiscale transforms such as the undecimated isotropic wavelet transform on the sphere, the ridgelet and curvelet transforms on the sphere. An MCA-inpainting method is then directly extended to the case of spherical maps allowing us to treat problems where parts of the data are missing or corrupted. We demonstrate the usefulness of these new tools of spherical data analysis by focusing on a selection of challenging applications in physics and astrophysics.     

On the construction of local quadratic spline quasi-interpolants on bounded rectangular domains

In this paper local bivariate C¹$C^1$ spline quasi-interpolants on a criss-cross triangulation of bounded rectangular domains are considered and a computational procedure for their construction is proposed. Numerical and graphical tests are provided.     

Construction of spherical spline quasi-interpolants based on blossoming

A general theory of quasi-interpolants based on quadratic spherical Powell-Sabin splines on spherical triangulations of a sphere-like surface S is developed by using polar forms. As application, various families of discrete and differential quasi-interpolants reproducing quadratic spherical Bézier-Bernstein polynomials or the whole space of the spherical Powell-Sabin quadratic splines of class C¹ are presented.     

Estimating the largest singular values of large sparse matrices via modified moments

We describe a procedure for determining a few of the largest singular values of a large sparse matrix. The method by Golub and Kent which uses the method of modified moments for estimating the eigenvalues of operators used in iterative methods for the solution of linear systems of equations is appropriately modified in order to generate a sequence of bidiagonal matrices whose singular values approximate those of the original sparse matrix. A simple Lanczos recursion is proposed for determining the corresponding left and right singular vectors. The potential asynchronous computation of the bidiagonal matrices using modified moments with the iterations of an adapted Chebyshev semi-iterative (CSI) method is an attractive feature for parallel computers. Comparisons in efficiency and accuracy with an appropriate Lanczos algorithm (with selective re-orthogonalization) are presented on large sparse (rectangular) matrices arising from applications such as information retrieval and seismic reflection tomography. This procedure is essentially motivated by the theory of moments and Gauss quadrature.This author's work was supported by the National Science Foundation under grants NSF CCR-8717492 and CCR-910000N (NCSA), the U.S. Department of Energy under grant DOE DE-FG02-85ER25001, and the Air Force Office of Scientific Research under grant AFOSR-90-0044 while at the University of Illinois at Urbana-Champaign Center for Supercomputing Research and Development.This author's work was supported by the U.S. Army Research Office under grant DAAL03-90-G-0105, and the National Science Foundation under grant NSF DCR-8412314.     

Newton's method and complex dynamical systems

This article is devoted to the discussion of Newton's method. Beginning with the old results of A.Cayley and E.Schröder we proceed to the theory of complex dynamical systems on the sphere, which was developed by G.Julia and P.Fatou at the beginning of this century, and continued by several mathematicians in recent years.     

Slip at the surface of a sphere translating perpendicular to a plane wall in micropolar fluid

The Stokes axisymmetrical flow caused by a sphere translating in a micropolar fluid perpendicular to a plane wall at an arbitrary position from the wall is presented using a combined analytical-numerical method. A linear slip, Basset type, boundary condition on the surface of the sphere has been used. To solve the Stokes equations for the fluid velocity field and the microrotation vector, a general solution is constructed from fundamental solutions in both cylindrical, and spherical coordinate systems. Boundary conditions are satisfied first at the plane wall by the Fourier transforms and then on the sphere surface by the collocation method. The drag acting on the sphere is evaluated with good convergence. Numerical results for the hydrodynamic drag force and wall effect with respect to the micropolarity, slip parameters and the separation distance parameter between the sphere and the wall are presented both in tabular and graphical forms. Comparisons are made between the classical fluid and micropolar fluid.      

A Petrov–Galerkin RBF method for diffusion equation on the unit sphere

This paper concerns a numerical solution for the diffusion equation on the unit sphere. The given method is based on the spherical basis function approximation and the Petrov–Galerkin test discretization. The method is meshless because spherical triangulation is not required neither for approximation nor for numerical integration. This feature is achieved through the spherical basis function approximation and the use of local weak forms instead of a global variational formulation. The local Petrov–Galerkin formulation allows to compute the integrals on small independent spherical caps without any dependence on a connected background mesh. Experimental results show the accuracy and the efficiency of the new method.     

An active set strategy to generate quadrilateral grids

We consider the problem of the generation of quadrilateral grids on planar domains. This problem is numerically solved by a two phases method: an iterative procedure based on the well-known variational approach, and an active set procedure to obtain unfolded quadrilaterals. This second phase is performed only when it is really necessary, in fact the first phase alone gives satisfactory results on a large number of domains. This two phases approach provides a robust method with low computational cost. Numerical experiments show that this method is able to generate unfolded grids also on complex domains.     

Smoothed projection methods for the moment problem

Summary We discuss the problem of reconstructing a functionf from a finite set of moments. Problems of this kind typically arise as discretizations of integral equations of the first kind. We propose an algorithm which is based on a pointwise optimization of the pointspread function, which makes it particularly suitable for local reconstructions. The method is compared with known methods as Backus-Gilbert and projection methods. Convergence of the method is proved and the rate of convergence is determined. The influence of noisy data is examined and numerical examples show the usefulness of the method.     

A branch and bound algorithm for bound constrained optimization problems without derivatives

In this paper, we give a new branch and bound algorithm for the global optimization problem with bound constraints. The algorithm is based on the use of inclusion functions. The bounds calculated for the global minimum value are proved to be correct, all rounding errors are rigorously estimated. Our scheme attempts to exclude most uninteresting parts of the search domain and concentrates on its promising subsets. This is done as fast as possible (by involving local descent methods), and uses little information as possible (no derivatives are required). Numerical results for many well-known problems as well as some comparisons with other methods are given.     

多点收缩混沌优化方法及全局收敛性证明

针对目前混沌优化算法在选取局部搜索空间时的盲目性,提出一种具有自适应调节局部搜索空间能力的多点收缩混沌优化方法.该方法在当前搜索空间搜索时保留多个较好搜索点,之后利用这些点来确定之后的局部搜索空间,以达到对不同的函数和当前搜索空间内已进行搜索次数的自适应效果.给出了该算法以概率1收敛的证明.仿真结果表明该算法有效的提高了混沌优化算法的性能,改善了混沌算法的实用性.     

An algorithm for the finite difference approximation of derivatives with arbitrary degree and order of accuracy

In this paper, we introduce an algorithm and a computer code for numerical differentiation of discrete functions. The algorithm presented is suitable for calculating derivatives of any degree with any arbitrary order of accuracy over all the known function sampling points. The algorithm introduced avoids the labour of preliminary differencing and is in fact more convenient than using the tabulated finite difference formulas, in particular when the derivatives are required with high approximation accuracy. Moreover, the given Matlab computer code can be implemented to solve boundary-value ordinary and partial differential equations with high numerical accuracy. The numerical technique is based on the undetermined coefficient method in conjunction with Taylor’s expansion. To avoid the difficulty of solving a system of linear equations, an explicit closed form equation for the weighting coefficients is derived in terms of the elementary symmetric functions. This is done by using an explicit closed formula for the Vandermonde matrix inverse. Moreover, the code is designed to give a unified approximation order throughout the given domain. A numerical differentiation example is used to investigate the validity and feasibility of the algorithm and the code. It is found that the method and the code work properly for any degree of derivative and any order of accuracy.