一类奇性积分方程的多尺度配置快速算法

This paper develops fast multiscale collocation methods for a class of Fredholm integral equations of the second kind with singular kernels. A truncation strategy for the coefficient matrix of the corresponding discrete system is proposed, which forms a basis for fast algorithms. The convergence, stability and computational complexity of these algorithms are analyzed.     

MULTILEVEL AUGMENTATION METHODS FOR SOLVING OPERATOR EQUATIONS

We introduce multilevel augmentation methods for solving operator equations based on direct sum decompositions of the range space of the operator and the solution space of the operator equation and a matrix splitting scheme. We establish a general setting for the analysis of these methods, showing that the methods yield approximate solutions of the same convergence order as the best approximation from the subspace. These augmentation methods allow us to develop fast, accurate and stable nonconventional numerical algorithms for solving operator equations. In particular, for second kind equations, special splitting techniques are proposed to develop such algorithms. These algorithms are then applied to solve the linear systems resulting from matrix compression schemes using wavelet-like functions for solving Fredholm integral equations of the second kind. For this special case, a complete analysis for computational complexity and convergence order is presented. Numerical examples are included to demonstra     

AN INTERIOR TRUST REGION ALGORITHM FOR NONLINEAR MINIMIZATION WITH LINEAR CONSTRAINTS

AbstractAn interior trust-region-based algorithm for linearly constrained minimization problems is proposed and analyzed. This algorithm is similar to trust region algorithms for unconstrained minimization: a trust region subproblem on a subspace is solved in each iteration. We establish that the proposed algorithm has convergence properties analogous to those of the trust region algorithms for unconstrained minimization. Namely, every limit point of the generated sequence satisfies the Krush-Kuhn-Tucker (KKT) conditions and at least one limit point satisfies second order necessary optimality conditions. In addition, if one limit point is a strong local minimizer and the Hessian is Lipschitz continuous in a neighborhood of that point, then the generated sequence converges globally to that point in the rate of at least 2-step quadratic. We are mainly concerned with the theoretical properties of the algorithm in this paper. Implementation issues and adaptation to large-scale problems will be addressed in a     

QUADRATURE METHODS FOR HIGHLY OSCILLATORY SINGULAR INTEGRALS

We address the evaluation of highly oscillatory integrals,with power-law and logarithmic singularities.Such problems arise in numerical methods in engineering.Notably,the evaluation of oscillatory integrals dominates the run-time for wave-enriched boundary integral formulations for wave scattering,and many of these exhibit singularities.We show that the asymptotic behaviour of the integral depends on the integrand and its derivatives at the singular point of the integrand,the stationary points and the endpoints of the integral.A truncated asymptotic expansion achieves an error that decays faster for increasing frequency.Based on the asymptotic analysis,a Filon-type method is constructed to approximate the integral.Unlike an asymptotic expansion,the Filon method achieves high accuracy for both small and large frequency.Complex-valued quadrature involves interpolation at the zeros of polynomials orthogonal to a complex weight function.Numerical results indicate that the complex-valued Gaussian quadrature achieves the highest accuracy when the three methods are compared.However,while it achieves higher accuracy for the same number of function evaluations,it requires signi cant additional cost of computation of orthogonal polynomials and their zeros.     

CENTER CONDITIONS AND BIFURCATION OF LIMIT CYCLES FOR A CLASS OF FIFTH DEGREE SYSTEMS

The center conditions and bifurcation of limit cycles for a class of fifth degree systems are investigated. Two recursive formulas to compute singular quantities at infinity and at the origin are given. The first nine singular point quantities at infinity and first seven singular point quantities at the origin for the system are given in order to get center conditions and study bifurcation of limit cycles. Two fifth degree systems are constructed. One allows the appearance of eight limit cycles in the neighborhood of infinity,which is the first example that a polynomial differential system bifurcates eight limit cycles at infinity. The other perturbs six limit cycles at the origin.     

Numerical realization of the conditions of Max NSther＇s residual intersection theorem

The aim of this paper is to study numerical realization of the conditions of Max Nother＇s residual intersection theorem. The numerical realization relies on obtaining the inter- section of two algebraic curves by homotopy continuation method, computing the approximate places of an algebraic curve, getting the exact orders of a polynomial at the places, and determin- ing the multiplicity and character of a point of an algebraic curve. The numerical experiments show that our method is accurate, effective and robust without using multiprecision arithmetic, even if the coefficients of algebraic curves are inexact. We also conclude that the computational complexity of the numerical realization is polynomial time.     

ON THE ORDER OF SUMMABILITY OF THE FOURIER INVERSION FORMULA

In this article we show that the order of the point value, in the sense of Lojasiewicz, of a tempered distribution and the order of summability of the pointwise Fourier inversion formula are closely related. Assuming that the order of the point values and certain order of growth at infinity are given for a tempered distribution, we estimate the order of summability of the Fourier inversion formula. For Fourier series, and in other cases, it is shown that if the distribution has a distributional point value of order k, then its Fourier series is e.v. Cesaro summable to the distributional point value of order k＋1. Conversely, we also show that if the pointwise Fourier inversion formula is e.v. Cesaro summable of order k, then the distribution is the （k ＋ 1）-th derivative of a locally integrable function, and the distribution has a distributional point value of order k ＋ 2. We also establish connections between orders of summability and local behavior for other Fourier inversion problems.     

Numerical realization of the conditions of Max Nther's residual intersection theorem

The aim of this paper is to study numerical realization of the conditions of Max Nther's residual intersection theorem. The numerical realization relies on obtaining the intersection of two algebraic curves by homotopy continuation method, computing the approximate places of an algebraic curve, getting the exact orders of a polynomial at the places, and determining the multiplicity and character of a point of an algebraic curve. The numerical experiments show that our method is accurate, effective and robust without using multiprecision arithmetic,even if the coefficients of algebraic curves are inexact. We also conclude that the computational complexity of the numerical realization is polynomial time.     

Tree wavelet approximations with applications

We construct a tree wavelet approximation by using a constructive greedy scheme (CGS). We define a function class which contains the functions whose piecewise polynomial approximations generated by the CGS have a prescribed global convergence rate and establish embedding properties of this class. We provide sufficient conditions on a tree index set and on bi-orthogonal wavelet bases which ensure optimal order of convergence for the wavelet approximations encoded on the tree index set using the bi-orthogonal wavelet bases. We then show that if we use the tree index set associated with the partition generated by the CGS to encode a wavelet approximation, it gives optimal order of convergence.     

Fast Parallel Method for Polynomial Evaluation at Points in Arithmetic Progression

We present a fast method for polynomial evaluation at points in arithmetic progression. By dividing the progression into rn new ones and evaluating the polynomial at each point of these new progressions recursively, this method saves most of the multiplications in the price of little increase of additions comparing to Horner＇s method, while their accuracy are almost the same. We also introduce vector structure to the recursive process making it suitable for parallel applications.     

Construction algorithms for higher order polynomial lattice rules

Higher order polynomial lattice point sets are special types of digital higher order nets which are known to achieve almost optimal convergence rates when used in a quasi-Monte Carlo algorithm to approximate high-dimensional integrals over the unit cube. The existence of higher order polynomial lattice point sets of “good” quality has recently been established, but their construction was not addressed.We use a component-by-component approach to construct higher order polynomial lattice rules achieving optimal convergence rates for functions of arbitrarily high smoothness and at the same time–under certain conditions on the weights–(strong) polynomial tractability. Combining this approach with a sieve-type algorithm yields higher order polynomial lattice rules adjusting themselves to the smoothness of the integrand up to a certain given degree. Higher order Korobov polynomial lattice rules achieve analogous results.     

Strong tractability of multivariate integration of arbitrary high order using digitally shifted polynomial lattice rules

In this paper we prove the existence of digitally shifted polynomial lattice rules which achieve strong tractability results for Sobolev spaces of arbitrary high smoothness. The convergence rate is shown to be the best possible up to a given degree of smoothness of the integrand. Indeed we even show the existence of polynomial lattice rules which automatically adjust themselves to the smoothness of the integrand up to a certain given degree.Further we show that strong tractability under certain conditions on the weights can be obtained and that polynomial lattice rules exist for which the worst-case error can be bounded independently of the dimension. These results hold independent of the smoothness.     

Collocation methods for fractional integro-differential equations with weakly singular kernels

In this paper, the piecewise polynomial collocation methods are used for solving the fractional integro-differential equations with weakly singular kernels. We present that a suitable transformation can convert fractional integro-differential equations to one type of second kind Volterra integral equations (VIEs) with weakly singular kernels. Then we solve the VIEs by standard piecewise polynomial collocation methods. It is shown that such kinds of methods are able to yield optimal convergence rate. Finally, some numerical experiments are given to show that the numerical results are consistent with the theoretical results.     

AC 0-collocation-like method for two-point boundary value problems

Summary A method of a collocation type based onC ⁰-piecewise polynomial spaces is presented for a two-point boundary value problem of the second order. The method has an optimal order of convergence under smoothness requirements on the exact solution which are weaker than forC ¹-collocation methods. If the differential operator is symmetric, a modification of this method leads to a symmetric system of linear equations. It is shown that if the collocation solution is a piecewise polynomial of degree not greater thanr, the method is stable and convergent with orderh ^r inH ¹-norm. A similar symmetric modification forC ⁰-colloction-finite element method [7] is also obtained. Superconvergence at the nodes is established.     

Spline collocation for singular integro-differential equations over (0.1)

Summary This paper analyses the convergence of spline collocation methods for singular integro-differential equations over the interval (0.1). As trial functions we utilize smooth polynomial splines the degree of which coincides with the order of the equation. Depending on the choice of collocation points we obtain sufficient and even necessary conditions for the convergence in sobolev norms. We give asymptotic error estimates and some numerical results.     

A High-Order Piecewise Quartic Spline Rule for Hadamard Integral and Its Application of the Cavity Scattering

We develop a fourth-order piecewise quartic spline rule for Hadamard integral. The quadrature formula of Hadamard integral is obtained by replacing the integrand function with the piecewise quartic spline interpolation function. We establish corresponding error estimates and analyze the numerical stability. The rule can achieve fourth-order convergence at any point in the interval, even when the singular point coincides with the grid point. Since the derivative information of the integrand is not required, the rule can be easily applied to solve many practical problems. Finally, the quadrature formula is applied to solve the electromagnetic scattering from cavities with different wave numbers, which improves the whole accuracy of the solution. Numerical experiments are presented to show the efficiency and accuracy of the theoretical analysis.     

The piecewise polynomial collocation method for nonlinear weakly singular Volterra equations

Second-kind Volterra integral equations with weakly singular kernels typically have solutions which are nonsmooth near the initial point of the interval of integration. Using an adaptation of the analysis originally developed for nonlinear weakly singular Fredholm integral equations, we present a complete discussion of the optimal (global and local) order of convergence of piecewise polynomial collocation methods on graded grids for nonlinear Volterra integral equations with algebraic or logarithmic singularities in their kernels.

     

Isogeometric Collocation: Cost Comparison with Galerkin Methods and Extension to Adaptive Hierarchical NURBS Discretizations

Collocation is based on the discretization of the strong form of the underlying partial differential equations, which requires basis functions of sufficient order and smoothness. Consequently, the use of isogeometric analysis (IGA) for collocation suggests itself, since splines can be readily adjusted to any order in polynomial degree and continuity required by the differential operators. In addition, they can be generated for domains of arbitrary geometric and topological complexity, directly linked to and fully supported by CAD technology. The major advantage of isogeometric collocation over Galerkin type IGA is the minimization of the computational effort for numerical quadrature. (© 2013 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)