Error estimations for some meshless boundary interpolation methods

Meshless methods have become quite popular in numerical treatment of partial differential equations because of their simplicity and the fact that they require neither domain nor boundary mesh. In general, however, they convert the original problem to a highly ill‐conditioned linear system of algebraic equations with a dense matrix. Recently, a special technique has been proposed which circumvents this computational difficulty. This method, called Direct Multi‐Elliptic Interpolation Method, is based on a scattered data interpolation which defines the interpolation function as a solution of a higher order multi‐elliptic equation. Here the boundary version of this meshless method which is based on a multi‐elliptic boundary interpolation is considered. Error estimations are derived justifying the interpolation function to be a good approximation of the solution of the original boundary value problem as well. At the same time, the problem of large, dense and ill‐conditioned matrices as well as the mesh generation are completely avoided. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Fast deconvolution with approximated PSF by RSTLS with antireflective boundary conditions

The problem of reconstructing signals and images from degraded ones is considered in this paper. The latter problem is formulated as a linear system whose coefficient matrix models the unknown point spread function and the right hand side represents the observed image. Moreover, the coefficient matrix is very ill-conditioned, requiring an additional regularization term. Different boundary conditions can be proposed. In this paper antireflective boundary conditions are considered. Since both sides of the linear system have uncertainties and the coefficient matrix is highly structured, the Regularized Structured Total Least Squares approach seems to be the more appropriate one to compute an approximation of the true signal/image. With the latter approach the original problem is formulated as an highly nonconvex one, and seldom can the global minimum be computed. It is shown that Regularized Structured Total Least Squares problems for antireflective boundary conditions can be decomposed into single variable subproblems by a discrete sine transform. Such subproblems are then transformed into one-dimensional unimodal real-valued minimization problems which can be solved globally. Some numerical examples show the effectiveness of the proposed approach.     

Matrix polynomials with spectral radius equal to the numerical radius

In this paper we study a class of matrix polynomials with the property that spectral radius and numerical radius coincide. Special attention is paid to the spectrum on the boundary of the numerical range.     

Linear B-spline finite element method for the improved Boussinesq equation

In this paper, we develop and validate a numerical procedure for solving a class of initial boundary value problems for the improved Boussinesq equation. The finite element method with linear B-spline basis functions is used to discretize the nonlinear partial differential equation in space and derive a second order system involving only ordinary derivatives. It is shown that the coefficient matrix for the second order term in this system is invertible. Consequently, for the first time, the initial boundary value problem can be reduced to an explicit initial value problem to which many accurate numerical methods are readily applicable. Various examples are presented to validate this technique and demonstrate its capacity to simulate wave splitting, wave interaction and blow-up behavior.     

The Laguerre spectral method for solving Neumann boundary value problems

In this paper, we propose a Laguerre spectral method for solving Neumann boundary value problems. This approach differs from the classical spectral method in that the homogeneous boundary condition is satisfied exactly. Moreover, a tridiagonal matrix is employed, instead of the full stiffness matrix encountered in the classical variational formulation of such problems. For analyzing the numerical errors, some basic results on Laguerre approximations are established. The convergence is proved. The numerical results demonstrate the efficiency of this approach.     

Fast Construction of Optimal Circulant Preconditioners for Matrices from the Fast Dense Matrix Method

In this paper, we consider solving non-convolution type integral equations by the preconditioned conjugate gradient method. The fast dense matrix method is a fast multiplication scheme that provides a dense discretization matrix A approximating a given integral equation. The dense matrix A can be constructed in O(n) operations and requires only O(n) storage where n is the size of the matrix. Moreover, the matrix-vector multiplication A xcan be done in O(n log n) operations. Thus if the conjugate gradient method is used to solve the discretized system, the cost per iteration is O(n log n) operations. However, for some integral equations, such as the Fredholm integral equations of the first kind, the system will be ill-conditioned and therefore the convergence rate of the method will be slow. In these cases, preconditioning is required to speed up the convergence rate of the method. A good choice of preconditioner is the optimal circulant preconditioner which is the minimizer of C – A _F in Frobenius norm over all circulant matrices C. It can be obtained by taking arithmetic averages of all the entries of A and therefore the cost of constructing the preconditioner is of O(n ²) operations for general dense matrices. In this paper, we develop an O(n log n) method of constructing the preconditioner for dense matrices A obtained from the fast dense matrix method. Application of these ideas to boundary integral equations from potential theory will be given. These equations are ill-conditioned whereas their optimal circulant preconditioned equations will be well-conditioned. The accuracy of the approximation A, the fast construction of the preconditioner and the fast convergence of the preconditioned systems will be illustrated by numerical examples.     

Some sufficient conditions for the non-negativity preservation property in the discrete heat conduction model

In the course of the numerical approximation of mathematical models there is often a need to solve a system of linear equations with a tridiagonal or a block-tridiagonal matrices. Usually it is efficient to solve these systems using a special algorithm (tridiagonal matrix algorithm or TDMA) which takes advantage of the structure. The main result of this work is to formulate a sufficient condition for the numerical method to preserve the non-negativity for the special algorithm for structured meshes. We show that a different condition can be obtained for such cases where there is no way to fulfill this condition. Moreover, as an example, the numerical solution of the two-dimensional heat conduction equation on a rectangular domain is investigated by applying Dirichlet boundary condition and Neumann boundary condition on different parts of the boundary of the domain. For space discretization, we apply the linear finite element method, and for time discretization, the well-known Θ-method. The theoretical results of the paper are verified by several numerical experiments.     

Chebyshev tau matrix method for Poisson-type equations in irregular domain

In this paper, a new meshless method, Chebyshev tau matrix method (CTMM) is researched. The matrix representations for the differentiation and multiplication of Chebyshev expansions make CTMM easy to implement. Problems with curve boundary can be efficiently treated by CTMM. Poisson-type problems, including standard Poisson problems, Helmholtz problems, problems with variable coefficients and nonlinear problems are computed. Some numerical experiments are implemented to verify the efficiency of CTMM, and numerical results are in good agreement with the analytical one. It appears that CTMM is very effective for Poisson-type problems in irregular domains.     

The boundary of the Krein space tracial numerical range, an algebraic approach and a numerical algorithm

In this article, tracial numerical ranges associated with matrices in an indefinite inner product space are investigated. The boundary equations of these sets are obtained, and the case of the boundary being a polygon is studied. As an application, a numerical algorithm for plotting the tracial numerical range of an arbitrary complex matrix is presented. Our approach uses the elementary idea that the boundary may be traced by computing the supporting lines.     

Banded operational matrices for Bernstein polynomials and application to the fractional advection-dispersion equation

In the papers, dealing with derivation and applications of operational matrices of Bernstein polynomials, a basis transformation, commonly a transformation to power basis, is used. The main disadvantage of this method is that the transformation may be ill-conditioned. Moreover, when applied to the numerical simulation of a functional differential equation, it leads to dense operational matrices and so a dense coefficient matrix is obtained. In this paper, we present a new property for Bernstein polynomials. Using this property, we build exact banded operational matrices for derivatives of Bernstein polynomials. Next, as an application, we propose a new numerical method based on a Petrov-Galerkin variational formulation and the new operational matrices utilizing the dual Bernstein basis for the time-fractional advection-dispersion equation. We show that the proposed method leads to a narrow-banded linear system and so less computational effort is required to obtain the desired accuracy for the approximate solution. We also obtain the error estimation for the method. Some numerical examples are provided to demonstrate the efficiency of the method and to support the theoretical claims.     

Circulant Wavelet Preconditioners for Solving Elliptic Differential Equations and Boundary Integral Equations

In this paper is discussed solving an elliptic equation and a boundary integral equation of the second kind by representation of compactly supported wavelets. By using wavelet bases and the Galerkin method for these equations, we obtain a stiff sparse matrix that can be ill-conditioned. Therefore, we have to introduce an operator which maps every sparse matrix to a circulant sparse matrix. This class of circulant matrices is a class of preconditioners in a Banach space. Based on having some properties in the spectral theory for this class of matrices, we conclude that the circulant matrices are a good class of preconditioners for solving these equations. We called them circulant wavelet preconditioners (CWP). Therefore, a class of algorithms is introduced for rapid numerical application.     

Inverse nodal problem for Dirac operator with integral type nonlocal boundary conditions

In this paper, Dirac operator with some integral type nonlocal boundary conditions is studied. We show that the coefficients of the problem can be uniquely determined by a dense set of nodal points. Moreover, we give an algorithm for the reconstruction of some coefficients of the operator.     

A fast interface solver for the biharmonic Dirichlet problem on polygonal domains

Summary. In this paper we propose and analyze an efficient discretization scheme for the boundary reduction of the biharmonic Dirichlet problem on convex polygonal domains. We show that the biharmonic Dirichlet problem can be reduced to the solution of a harmonic Dirichlet problem and of an equation with a Poincaré-Steklov operator acting between subspaces of the trace spaces. We then propose a mixed FE discretization (by linear elements) of this equation which admits efficient preconditioning and matrix compression resulting in the complexity . Here is the number of degrees of freedom on the underlying boundary, is an error reduction factor, or for rectangular or polygonal boundaries, respectively. As a consequence an asymptotically optimal iterative interface solver for boundary reductions of the biharmonic Dirichlet problem on convex polygonal domains is derived. A numerical example confirms the theory. Received September 1, 1995 / Revised version received February 12, 1996     

Matrix valued adaptive cross approximation

A new variant of the Adaptive Cross Approximation (ACA) for approximation of dense block matrices is presented. This algorithm can be applied to matrices arising from the Boundary Element Methods (BEM) for elliptic or Maxwell systems of partial differential equations. The usual interpolation property of the ACA is generalised for the matrix valued case. Some numerical examples demonstrate the efficiency of the new method. The main example will be the electromagnetic scattering problem, that is, the exterior boundary value problem for the Maxwell system. Here, we will show that the matrix valued ACA method works well for high order BEM, and the corresponding high rate of convergence is preserved. Another example shows the efficiency of the new method in comparison with the standard technique, whilst approximating the smoothed version of the matrix valued fundamental solution of the time harmonic Maxwell system. Copyright © 2016 John Wiley & Sons, Ltd.     

Wavelet Collocation Methods for a First Kind Boundary Integral Equation in Acoustic Scattering

In this paper we consider a wavelet algorithm for the piecewise constant collocation method applied to the boundary element solution of a first kind integral equation arising in acoustic scattering. The conventional stiffness matrix is transformed into the corresponding matrix with respect to wavelet bases, and it is approximated by a compressed matrix. Finally, the stiffness matrix is multiplied by diagonal preconditioners such that the resulting matrix of the system of linear equations is well conditioned and sparse. Using this matrix, the boundary integral equation can be solved effectively.     

A fast BIE iteration method for an arbitrary body in a flow of incompressible inviscid fluid

The paper is concerned with the new iteration algorithm to solve boundary integral equations arising in boundary value problems of mathematical physics. The stability of the algorithm is demonstrated on the problem of a flow around bodies placed in the incompressible inviscid fluid. With a discrete numerical treatment, we approximate the exact matrix by a certain Töeplitz one and then apply a fast algorithm for this matrix, on each iteration step. We illustrate the convergence of this iteration scheme by a number of numerical examples, both for hard and soft boundary conditions. It appears that the method is highly efficient for hard boundaries, being much less efficient for soft boundaries.     

A modification of the invariant imbedding method for a singular boundary value problem

We consider a dynamically-consistent analytical model of a 3D topographic vortex. The model is governed by equations derived from the classical problem of the axisymmetric Taylor–Couette flow. Using linear expansions, these equations can be reduced to a differential sixth-order equation with variable coefficients. For this differential equation, we formulate a boundary value problem, which has a number of issues for numerical solving. To avoid these issues and find the eigenvalues and eigenfunctions of the boundary value problem, we suggest a modification of the invariant imbedding method (the Riccati equation method). In this paper, we show that such a modification is necessary since the boundary conditions possess singular matrices, which sufficiently complicate the derivation of the Riccati equation. We suggest algebraic manipulations, which permit the initial problem to be reduced to a problem with regular boundary conditions. Also, we propose a method for obtaining a numerical solution of the matrix Riccati equation by means of recurrence relations, which allow us to obtain a matrizer converging to the required eigenfunction. The suggested method is tested by calculating the corresponding eigenvalues and eigenfunctions, and then, by constructing fluid particle trajectories on the basis of the eigenfunctions.     

Analysing the Efficiency of Solving Dense Linear Equations on Dawning1000

In this paper, we consider solving dense linear equations on Dawning1000 by using matrix partitioning technique. Based on this partitioning of matrix, we give a parallel block LU decomposition method. The efficiency of solving linear equations by different ways is analysed. The numerical results are given on Dawning1000. By running our parallel program, the best speed up on 32 processors is over 25.     

Mono-implicit Runge–Kutta formulae for the numerical solution of second order nonlinear two-point boundary value problems

Mono-implicit Runge–Kutta (MIRK) formulae are widely used for the numerical solution of first order systems of nonlinear two-point boundary value problems. In order to avoid costly matrix multiplications, MIRK formulae are usually implemented in a deferred correction framework and this is the basis of the well known boundary value code TWPBVP. However, many two-point boundary value problems occur naturally as second (or higher) order equations or systems and for such problems there are significant savings in computational effort to be made if the MIRK methods are tailored for these higher order forms. In this paper, we describe MIRK algorithms for second order equations and report numerical results that illustrate the substantial savings that are possible particularly for second order systems of equations where the first derivative is absent.     

Localized method of fundamental solutions for large-scale modeling of two-dimensional elasticity problems

The traditional method of fundamental solutions (MFS) based on the “global” boundary discretization leads to dense and non-symmetric coefficient matrices that, although smaller in sizes, require huge computational cost to compute the system of equations using direct solvers. In this study, a localized version of the MFS (LMFS) is proposed for the large-scale modeling of two-dimensional (2D) elasticity problems. In the LMFS, the whole analyzed domain can be divided into small subdomains with a simple geometry. To each of the subdomain, the traditional MFS formulation is applied and the unknown coefficients on the local geometric boundary can be calculated by the moving least square method. The new method yields a sparse and banded matrix system which makes the method very attractive for large-scale simulations. Numerical examples with up to 200,000 unknowns are solved successfully using the developed LMFS code.