A parameter-uniform numerical method for time-dependent singularly perturbed differential-difference equations

A numerical study is made for solving a class of time-dependent singularly perturbed convection–diffusion problems with retarded terms which often arise in computational neuroscience. To approximate the retarded terms, a Taylor’s series expansion has been used and the resulting time-dependent singularly perturbed differential equation is approximated using parameter-uniform numerical methods comprised of a standard implicit finite difference scheme to discretize in the temporal direction on a uniform mesh by means of Rothe’s method and a B-spline collocation method in the spatial direction on a piecewise-uniform mesh of Shishkin type. The method is shown to be accurate of order O(M⁻¹ + N⁻² ln³N), where M and N are the number of mesh points used in the temporal direction and in the spatial direction respectively. An extensive amount of analysis has been carried out to prove the uniform convergence with respect to the singular perturbation parameter. Numerical results are given to illustrate the parameter-uniform convergence of the numerical approximations. Comparisons of the numerical solutions are performed with an upwind and midpoint upwind finite difference scheme on a piecewise-uniform mesh to demonstrate the efficiency of the method.     

Coupling of a multilevel fast multipole method and a microlocal discretization for the 3-D integral equations of electromagnetism

The aim of this work is to propose an accurate and efficient numerical approximation for high frequency diffraction of electromagnetic waves. In the context of the boundary integral equations presented in F. Collino and B. Després, to be published in J. Comput. Appl. Math., the strategy we propose combines the microlocal discretization (T. Abboud et al., in: Third International Conference on Mathematical Aspects of Wave Propagation Phenomena, SIAM, 1995, pp. 178–187) and the multilevel fast multipole method (J.M. Song, W.C. Chew, Microw. Opt. Tech. Lett. 10 (1) (1995) 14–19). This leads to a numerical method with a reduced complexity, of order O(N^4/3ln(N)+N_iterN^2/3), instead of the complexity O(N_iterN²) for a classical numerical iterative solution of integral equations. Computations on an academic geometry show that the new method improves the efficiency, for a solution with a good level of accuracy. To cite this article: A. Bachelot et al., C. R. Acad. Sci. Paris, Ser. I 336 (2003).     

Numerical shadows: Measures and densities on the numerical range

For any operator M acting on an N-dimensional Hilbert space H_N we introduce its numerical shadow, which is a probability measure on the complex plane supported by the numerical range of M. The shadow of M at point z is defined as the probability that the inner product (Mu, u) is equal to z, where u stands for a random complex vector from H_N, satisfying ||u||=1. In the case of N=2 the numerical shadow of a non-normal operator can be interpreted as a shadow of a hollow sphere projected on a plane. A similar interpretation is provided also for higher dimensions. For a hermitian M its numerical shadow forms a probability distribution on the real axis which is shown to be a one dimensional B-spline. In the case of a normal M the numerical shadow corresponds to a shadow of a transparent solid simplex in R^N-1 onto the complex plane. Numerical shadow is found explicitly for Jordan matrices J_N, direct sums of matrices and in all cases where the shadow is rotation invariant. Results concerning the moments of shadow measures play an important role. A general technique to study numerical shadow via the Cartesian decomposition is described, and a link of the numerical shadow of an operator to its higher-rank numerical range is emphasized.     

Type III1 equilibrium states of the Toeplitz algebra of the affine semigroup over the natural numbers

We complete the analysis of KMS-states of the Toeplitz algebra T(N?N^×) of the affine semigroup over the natural numbers, recently studied by Raeburn and the first author, by showing that for every inverse temperature β in the critical interval 1?β?2, the unique KMSβ-state is of type III₁. We prove this by reducing the type classification from T(N?N^×) to that of the symmetric part of the Bost-Connes system, with a shift in inverse temperature. To carry out this reduction we first obtain a parametrization of the Nica spectrum of N?N^× in terms of an adelic space. Combining a characterization of traces on crossed products due to the second author with an analysis of the action of N?N^× on the Nica spectrum, we can also recover all the KMS-states of T(N?N^×) originally computed by Raeburn and the first author. Our computation sheds light on why there is a free transitive circle action on the extremal KMSβ-states for β>2 that does not ostensibly come from an action of T on the C^?-algebra.     

Fredholm-Volterra integral equation with singular kernel

The purpose of this paper is to obtain the solution of Fredholm-Volterra integral equation with singular kernel in the space L₂(?1, 1) × C(0,T), 0 ≤t ≤T < ∞, under certain conditions. The numerical method is used to solve the Fredholm integral equation of the second kind with weak singular kernel using the Toeplitz matrices. Also, the error estimate is computed and some numerical examples are computed using the MathCad package.     

Number-theoretic degeneracy of the energy levels of a perturbed N-dimensional isotropic harmonic oscillator

The problem of constructing all integer solutions n₁ ≥ n₂ ≥ … ≥ n_N to the pair of Diophantine equations n = n₁ + … + n_N, m = n₁² + … + n_N² arises in the determination of the degeneracy of a given energy level of an N-dimensional isotropic quantum oscillator that is perturbed by an isotropic quartic potential energy term. This problem is solved recursively (in N) using the concept of a multiplet, which is a finite set of points in a lattice space L^N whose points are N-tuples of integers that sum to zero. The basic definition and properties of multiplets are given and then used to obtain the solutions to the Diophantine equations described above. The classification of multiplets into two types, fundamental and nonfundamental, is shown to have an important role in elucidating the structure of multiplets. The concept of a fundamental multiplet is demonstrated to be an important characterization of the solutions to a pair of Diophantine equations that are closely related to those of the original problem.     

Advanced combinations of splitting–shooting–integrating methods for digital image transformations

An image consists of many discrete pixels with greyness of different levels, which can be quantified by greyness values. The greyness values at a pixel can also be represented by an integral as the mean of continuous greyness functions over a small pixel region. Based on such an idea, the discrete images can be produced by numerical integration; several efficient algorithms are developed to convert images under transformations. Among these algorithms, the combination of splitting–shooting–integrating methods (CSIM) is most promising because no solutions of nonlinear equations are required for the inverse transformation. The CSIM is proposed in [6] to facilitate images and patterns under a cycle transformations T⁻¹T, where T is a nonlinear transformation. When a pixel region in two dimensions is split into N² subpixels, convergence rates of pixel greyness by CSIM are proven in [8] to be only O(1/N). In [10], the convergence rates O_p(1/N^1.5) in probability and O_p(1/N²) in probability using a local partition are discovered. The CSIM is well suited to binary images and the images with a few greyness levels due to its simplicity. However, for images with large (e.g., 256) multi-greyness levels, the CSIM still needs more CPU time since a rather large division number is needed.In this paper, a partition technique for numerical integration is proposed to evaluate carefully any overlaps between the transformed subpixel regions and the standard square pixel regions. This technique is employed to evolve the CSIM such that the convergence rate O(1/N²) of greyness solutions can be achieved. The new combinations are simple to carry out for image transformations because no solutions of nonlinear equations are involved in, either. The computational figures for real images of 256×256 with 256 greyness levels display that N=4 is good enough for real applications. This clearly shows validity and effectiveness of the new algorithms in this paper.     

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.     

Studies in the formation of heterocyclic rings containing nitrogen

Synthesis of 1-benzyl-3-methyl (I), 1-beazyl-3-substituted benzyl (II) and 1-methyl-3-substituted benzyl (III)-2-aryl benzimidazolines is described. (I) acc obtained by the condensation of N¹benzyl-N²methyl-o-phenylenediamine with various aldehydes in metharol. Compounds (II) are prepared from N¹-benzyl-N²-arylidene-o-phenylenediamines in acetic acid, through a process of disproportionation involving an oxidation-reduction process. Likewise, (III) are obtained from N¹-methyl-N²-arylidenc-o-phenylenediamines. The exact structure of N¹-benzyl-N²-arylidene-o-phenylenediamines which can exist in the open chain form or in the ring form has been investigated using nmr spectroscopy.     

The kernel of the sum of two cooperative games

A sum of two gamesG ¹=(N ¹,v ¹) andG ²=(N ²,v ²) with disjoint sets of players is defined to be a gameG=(N, v), whereN=N ¹ ∪N ² andv (S)=max {v ¹ (S ∩N ¹),v ² (S ∩N ²)}. The kernel of the sum of two games is given in terms of the parts of kernels of the modified component games. The sum of games from certain classes is considered. When the components of the sum are simple games one of the corollaries of the main theorem coincides with known results.     

Numerical Approach for Assessing System Dynamic Availability Via Continuous Time Homogeneous Semi-Markov Processes

Continuous-time homogeneous semi-Markov processes (CTHSMP) are important stochastic tools to model reliability measures for systems whose future behavior is dependent on the current and next states occupied by the process as well as on sojourn times in these states. A method to solve the interval transition probabilities of CTHSMP consists of directly applying any general quadrature method to the N ² coupled integral equations which describe the future behavior of a CTHSMP, where N is the number of states. However, the major drawback of this approach is its considerable computational effort. In this work, it is proposed a new more efficient numerical approach for CTHSMPs described through either transition probabilities or transition rates. Rather than N ² coupled integral equations, the approach consists of solving only N coupled integral equations and N straightforward integrations. Two examples in the context of availability assessment are presented in order to validate the effectiveness of this method against the comparison with the results provided by the classical and Monte Carlo approaches. From these examples, it is shown that the proposed approach is significantly less time-consuming and has accuracy comparable to the method of N ² computational effort.     

Numerical experiments on the condition number of the interpolation matrices for radial basis functions

Through numerical experiments, we examine the condition numbers of the interpolation matrix for many species of radial basis functions (RBFs), mostly on uniform grids. For most RBF species that give infinite order accuracy when interpolating smooth f(x)—Gaussians, sech's and Inverse Quadratics—the condition number κ(α,N) rapidly asymptotes to a limit κasymp(α) that is independent of N and depends only on α, the inverse width relative to the grid spacing. Multiquadrics are an exception in that the condition number for fixed α grows as N². For all four, there is growth proportional to an exponential of 1/α (1/α² for Gaussians). For splines and thin-plate splines, which contain no width parameter, the condition numbers grows asymptotically as a power of N—a large power as the order of the RBF increases. Random grids typically increase the condition number (for fixed RBF width) by orders of magnitude. The quasi-random, low discrepancy Halton grid may, however, have a lower condition number than a uniform grid of the same size.     

Approximating eigenfunctions of Fredholm operators in Banach spaces

A singular Fredholm operator A is perturbed by an operator of finite rank to obtain an invertible operator B. Theory previously developed for A and B in Hilbert spaces is extended here to Banach spaces. The operator B^?1 is used to construct independent elements in the null spaces N(A), N(A²),…, N(A^k), for some positive integer k, and a basis for N(A) and N(A²). The theory is used to compute approximations to eigenfunctions and generalized eigenfunctions of integral operators.     

Filter matrix based on interpolation wavelets for solving Fredholm integral equations

The interpolation wavelet is used to solve the Fredholm integral equation of the second kind in this study. Hence, by the extension of interpolation wavelets that [−1, 1] is divided to 2^N+1 (N ⩾  − 1) subinterval, we have polynomials with a degree less than M + 1 in each new interval. Therefore, by considering the two-scale relation the filter coefficients and filter matrix are used as the proof of theorems. The important point is interpolation wavelets lead to more sparse matrix when we try to solve integral equation by an approximate kernel decomposed to a lower and upper resolution. Using n-time, where (n ⩾ 2), two-scale relation in this method errors of approximate solution as O((2^−(N+1))ⁿ⁺¹). Also, the filter coefficient simplifies the proof of some theorems and the order of convergence is estimated by numerical errors.     

The use of solutions on embedded grids for the approximation of singularly perturbed parabolic convection-diffusion equations on adapted grids

The Dirichlet problem on a closed interval for a parabolic convection-diffusion equation is considered. The higher order derivative is multiplied by a parameter ? taking arbitrary values in the semi-open interval (0, 1]. For the boundary value problem, a finite difference scheme on a posteriori adapted grids is constructed. The classical approximations of the equation on uniform grids in the main domain are used; in some subdomains, these grids are subjected to refinement to improve the grid solution. The subdomains in which the grid should be refined are determined using the difference of the grid solutions of intermediate problems solved on embedded grids. Special schemes on a posteriori piecewise uniform grids are constructed that make it possible to obtain approximate solutions that converge almost ?-uniformly, i.e., with an error that weakly depends on the parameter ?: |u(x, t) ? z(x, t)| ≤ M[N ₁ ^?1 ln² N ₁ + N ₀ ^?1 lnN ₀ + ?^?1 N ₁ ^?K ln ^K?1 N ₁], (x, t) ε ? _h , where N ₁ + 1 and N ₀ + 1 are the numbers of grid points in x and t, respectively; K is the number of refinement iterations (with respect to x) in the adapted grid; and M = M(K). Outside the σ-neighborhood of the outflow part of the boundary (in a neighborhood of the boundary layer), the scheme converges ?-uniformly at a rate O(N ₁ ^?1 ln² N ₁ + N ₀ ^?1 lnN ₀), where σ ≤ MN ₁ ^{?K + 1} ln ^K?1 N ₁ for K ≥ 2.     

Numerical recipes for the high efficient inverse of the confluent Vandermonde matrices

In this paper, we derive a numerical recipe for the calculation of the inversion of the confluent Vandermonde matrix. The main result of this article does not require any symbolic calculations and therefore can be performed by a numerical algorithm implemented either in any high level (like Matlab or Mathematica) or low level programming language (C/C++/Java/Pascal/Fortran, etc.). The computational complexity of the presented algorithm is of an O(N²) class being, by the linear term, better than the ordinary Gauss elimination method. Moreover, a ready to use C++ full implementation of the algorithm is attached.     

Fast multipole method for multidimensional integrals

We give a fast algorithm to evaluate a class of d-dimensional integrals. A direct numerical evaluation of these integrals costs N^d, where d is the number of variables and N is the number of discrete points of each variable. The algorithm we present in this Note permits to reduce this cost from N^d to a cost of the order O(N). This recursive algorithm takes its inspiration from the well-known Fast-Multipole method. At the end of this paper we give some physical applications of such an algorithm.     

Evaluation of the Riemann-Mellin integral

A method for evaluating the Riemann-Mellin integral $$ f(t) = \frac{1} {{2\pi i}}\int\limits_{c - i\infty }^{c + i\infty } {e^{zt} F(z)dz,c > 0,} $$ which determines the inverse Laplace transform, is considered; the method consists in reducing the integral to the form I = ∝ _?∞ ^∞ g(u) by means of a suitable deformation of the contour of integration and applying the trapezoidal quadrature formulas with an infinite number of nodes (I _h = hΣ _k=?∞ ^∞ g(kh)) or with a finite number 2N + 1 of nodes (I _{h, N} = hΣ _{k = ?N} ^N g(kh)). For parabolic and hyperbolic contours of integration, procedures for choosing the step size h in numerical integration and the summation limits ±N for truncating the infinite sum in the trapezoidal formula, which depend on the arrangement of the singular points of the image, are suggested. Errors are estimated, and their asymptotic behavior with increasing N is described.     

Uniform grid approximation of nonsmooth solutions with improved convergence for a singularly perturbed convection-diffusion equation with characteristic layers

A mixed boundary value problem for a singularly perturbed elliptic convection-diffusion equation with constant coefficients in a square domain is considered. Dirichlet conditions are specified on two sides orthogonal to the flow, and Neumann conditions are set on the other two sides. The right-hand side and the boundary functions are assumed to be sufficiently smooth, which ensures the required smoothness of the desired solution in the domain, except for neighborhoods of the corner points. Only zero-order compatibility conditions are assumed to hold at the corner points. The problem is solved numerically by applying an inhomogeneous monotone difference scheme on a rectangular piecewise uniform Shishkin mesh. The inhomogeneity of the scheme lies in that the approximating difference equations are not identical at different grid nodes but depend on the perturbation parameter. Under the assumptions made, the numerical solution is proved to converge ?-uniformly to the exact solution in a discrete uniform metric at an O(N ^?3/2ln² N) rate, where N is the number of grid nodes in each coordinate direction.