Search

This paper develops an efficient local meshless collocation algorithm for approximating the time fractional evolution model that is applied for the modeling of heat flow in materials with memory. The model is based on the Riemann-Liouville fractional integral. The proposed method discretizes the unknown solution using two main parts. First, the temporal direction is approximated through the second-order finite difference scheme. Second, the spatial direction of the governing problem is discretized via the local radial basis function partition of unity technique. The major drawback of global collocation techniques is the computational cost associated with arisen dense algebraic system. This localized method is based on partitioning the original domain to several subdomains by means of the kernel approximation on each local domain and allows one to significantly sparsify the algebraic system having small condition number in addition to lowering the computational cost. The stability and convergence of the time difference formulation are discussed in detail with respect to the H 1 -norm. Numerical results and comparisons are illustrated in order to confirm theoretical analysis and the accuracy of the method.

The truncated singular value decomposition (TSVD) is a popular method for solving linear discrete ill-posed problems with a small to moderately sized matrix A. This method replaces the matrix A by the closest matrix A k of low rank k, and then computes the minimal norm solution of the linear system of equations with a rank-deficient matrix so obtained. The modified TSVD (MTSVD) method improves the TSVD method, by replacing A by a matrix that is closer to A than A k in a unitarily invariant matrix norm and has the same spectral condition number as A k . Approximations of the SVD of a large matrix A can be computed quite efficiently by using a randomized SVD (RSVD) method. This paper presents a novel modified truncated randomized singular value decomposition (MTRSVD) method for computing approximate solutions to large-scale linear discrete ill-posed problems. The rank, k, is determined with the aid of the discrepancy principle, but other techniques for selecting a suitable rank also can be used. Numerical examples illustrate the effectiveness of the proposed method and compare it to the truncated RSVD method.

We develop a preconditioned fast divided-and-conquer finite element approximation for the initial-boundary value problem of variable-order time-fractional diffusion equations. Due to the impact of the time-dependent variable order, the coefficient matrix of the resulting all-at-once system does not have a Toeplitz-like structure. In this paper we derive a fast approximation of the coefficient matrix by the means of a sum of Toeplitz matrices multiplied by diagonal matrices. We show that the approximation is asymptotically consistent with the original problem, which requires O ( M N log 3 ⁡ N ) computational complexity and O ( M N log 2 ⁡ N ) memory with M and N being the numbers of degrees of freedom in space and time, respectively. Furthermore, a preconditioner is introduced to reduce the number of iterations caused by the bad condition number of the coefficient matrix. Numerical experiments are presented to demonstrate the effectiveness and the efficiency of the proposed method.

For Laplace's equation in a bounded simply-connected domain Ω in 3D, the method of fundamental solutions (MFS) is studied in this paper. Although some numerical computations can be found in Chen et al. [10] , the theoretical analysis is much behind (Li [23] only for unit sphere Ω). Our efforts are devoted to exploring a strict error analysis of the MFS. The error bounds are derived, and the optimal polynomial convergence rates can be achieved. Numerical experiments are carried out to support the analysis made, and several useful locations of source nodes are investigated numerically. The analysis in this paper may lay a theoretical basis of the MFS for 3D problems, as Bogomolny [8] and [24] for 2D problems. Besides, the method of particular solutions (MPS) in [26] is also studied by using the spherical harmonic functions (SHF). The optimal polynomial convergence rates and the exponential growth of condition number (Cond) are obtained. The source nodes are located based on the abscissas of quadrature rules on surfaces; they are “grid-like”. Since most of 3D problems, in reality, can not be simplified to 2D problems, and since the MFS has more advantages for 3D problems in algorithm simplicity and wide application, the study in this paper is essential and important to the MFS.

SimRank is popularly used for evaluating similarities between nodes in a graph. Though some recent work has transformed the SimRank into a linear system which can be solved by using conjugate gradient (CG) algorithm. However, the diagonal preconditioner used in the algorithm still left some room for improvement. There is no work showing what should be an optimal preconditioner for the linear system. For such a sake, in this paper, we theoretically study the preconditioner problem and propose a polynomial preconditioner which can improve the computation speed significantly. In our investigation, we also modify the original linear system to adapt to all situations of the graph. We further prove that the condition number of a polynomial preconditioned matrix is bounded in a narrow interval. It implies that the new preconditioner can effectively accelerate the convergence rate of the CG algorithm. The experimental results show the proposed algorithm outperforms the state-of-the-art algorithms for the all-pairs SimRank computation.

In this paper we first consider a special class of nonhomogeneous and anisotropic Helmholtz equation with variable coefficients and the source term. Combined with local spectral element method, a generalized plane wave discontinuous Galerkin method for the discretization of such Helmholtz equation is designed. Then we define new generalized plane wave basis functions for two-dimensional anisotropic Helmholtz equation with the variable coefficient. Besides, the error estimates of the approximation solutions generated by the proposed discretization method are derived. Especially, the orders of the condition number ρ of the anisotropic matrix in the error estimates are optimal. Finally, numerical results verify the validity of the theoretical results, and indicate that the new method possesses high accuracy and is slightly affected by the pollution effect for the large wavenumbers.

The condition number of a linear function of the indefinite least squares solution is called the partial condition number for the indefinite least squares problem. In this paper, based on a new and very general condition number which can be called the unified condition number, the expression of the partial unified condition number is first presented when the data space is measured by the general weighted product norm. Then, by setting the specific norms and weight parameters, we obtain the expressions of the partial normwise, mixed and componentwise condition numbers. Moreover, the corresponding structured partial condition numbers are also taken into consideration when the problem is structured, whose expressions are given. Considering the connections between the indefinite and total least squares problems, we derive the (structured) partial condition numbers for the latter, which generalize the ones in the literature. To estimate these condition numbers effectively and reliably, the probabilistic spectral norm estimator and the small-sample statistical condition estimation method are applied and three related algorithms are devised. Finally, the obtained results are illustrated by numerical experiments., 22 pages

We consider the situation where a basic preconditioner is improved with a coarse grid correction. The latter can be implemented either additively (like in the standard additive Schwarz method) or multiplicatively (like in the balancing preconditioner). In a previous study, Nabben and Vuik compare both variants, and state that a theoretical comparison of the condition numbers is not possible: whereas it is admitted that the condition number is in most cases smaller with the multiplicative variant, they provide an example for which the converse is true. Here we show that the multiplicative variant has in fact always lower condition number when the basic preconditioner is appropriately scaled. On the other hand, we also show, again assuming an appropriate scaling, that the condition number of the additive variant is at worst a modest multiple of that of the multiplicative variant. Hence both approaches are qualitatively equivalent. Eventually, we show with some examples that both the upper and lower bounds on the condition number of the additive variant are sharp: it can be in some cases equal to the condition number of the multiplicative variant, and in other cases arbitrarily close to the aforementioned modest multiple of this latter value.

We extend the classical Nitsche type weak boundary conditions to a fictitious domain setting. An additional penalty term, acting on the jumps of the gradients over element faces in the interface zone, is added to ensure that the conditioning of the matrix is independent of how the boundary cuts the mesh. Optimal a priori error estimates in the H1- and L2-norms are proved as well as an upper bound on the condition number of the system matrix.

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 @k(@a,N) rapidly asymptotes to a limit @k"a"s"y"m"p(@a) that is independent of N and depends only on @a, the inverse width relative to the grid spacing. Multiquadrics are an exception in that the condition number for fixed @a grows as N^2. For all four, there is growth proportional to an exponential of 1/@a (1/@a^2 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.

The classical Goldstein's method has been well studied in the context of variational inequalities (VIs). In particular, it has been shown in the literature that the Goldstein's method works well for co-coercive VIs where the underlying mapping is co-coercive. In this paper, we show that the Goldstein's method can be extended to solve co-coercive variant variational inequalities (VVIs). We first show that when the Goldstein's method is applied to solve VVIs, the iterative scheme can be improved by identifying a refined step-size if the involved co-coercive modulus is known. By doing so, the allowable range of the involved scaling parameter ensuring convergence is enlarged compared to that in the context of VVIs with Lipschitz and strongly monotone operators. Then, we show that for such a VVI whose co-coercive modulus is unknown, the Goldstein's method is still convergent provided that an easily-implementable Armijo's type strategy of adjusting the scaling parameter self-adaptively is employed. Some numerical results are reported to verify that the proposed Goldstein's type methods are efficient for solving VVIs.

How to calculate highly oscillatory integrals rapidly and accurately is one of the key problems in many fields. In this paper, an oscillatory quadrature algorithm based on Levin method is put forward. This method has a high computational speed and has addressed the problem that the Levin method is susceptible to the ill conditioning. Numerical experiments confirm the benefits of this method.

This paper presents the mechanical quadrature methods (MQMs) for solving boundary integral equations (BIEs) of the first kind on open arcs. The spectral condition number of MQMs is only O(h^-^1), where h is the maximal mesh width. The errors of MQMs have multivariate asymptotic expansions, accompanied with O(h"i^3) for all mesh widths h"i. Hence, once discrete equations with coarse meshes are solved in parallel, the accuracy order of numerical approximations can be greatly improved by splitting extrapolation algorithms (SEAs). Moreover, a posteriori asymptotic error estimates are derived, which can be used to formulate self-adaptive algorithms. Numerical examples are also provided to support our algorithms and analysis. Furthermore, compared with the existing algorithms, such as Galerkin and collocation methods, the accuracy order of the MQMs is higher, and the discrete matrix entries are explicit, to prove that the MQMs in this paper are more promising and beneficial to practical applications.

Finite element tearing and interconnecting (FETI) methods and boundary element tearing and interconnecting (BETI) methods are special iterative substructuring methods with Lagrange multipliers. For elliptic boundary value problems on bounded domains, the condition number of these methods can be rigorously bounded by C(1+log(H/h))^2, where H is the subdomain diameter and h the mesh size. The constant C is independent of H, h and possible jumps in the coefficients of the partial differential equation. In certain situations, e.g., in electromagnetic field computations, instead of imposing artificial boundary conditions one may be interested in modelling the real physical behaviour in an exterior domain with a radiation condition. In this work we analyze one-level BETI methods for such unbounded domains and show explicit condition number estimates similar to the one above. Our theoretical results are confirmed in numerical experiments.

In this paper we present the additive Schwarz method for the hypersingular integral equation of the first kind in two dimensions for the h version of the Galerkin method on algebraically graded meshes. We prove that the condition number of the preconditioned system grows only polylogarithmically with respect to the number of unknowns. Our theoretical results are underlined by numerical experiments.

Eigenvalues of smallest magnitude become a major bottleneck for iterative solvers especially when the underlying physical properties have severe contrasts. These contrasts are commonly found in many applications such as composite materials, geological rock properties and thermal and electrical conductivity. The main objective of this work is to construct a method as algebraic as possible. However, the underlying physics is utilized to distinguish between high and low degrees of freedom which is central to the construction of the proposed preconditioner. Namely, we propose an algebraic way of separating binary-like systems according to a given threshold into high- and low-conductivity regimes of coefficient size O(m) and O(1), respectively where [email protected]?1. So, the proposed preconditioner is essentially physics-based because without the utilization of underlying physics such an algebraic distinction, hence, the construction of the preconditioner would not be possible. The condition number of the linear system depends both on the mesh size @Dx and the coefficient size m. For our purposes, we address only the m dependence since the condition number of the linear system is mainly governed by the high-conductivity sub-block. Thus, the proposed strategy is inspired by capturing the relevant physics governing the problem. Based on the algebraic construction, a two-stage preconditioning strategy is developed as follows: (1) a first stage that comprises approximation to the components of the solution associated to small eigenvalues and, (2) a second stage that deals with the remaining solution components with a deflation strategy (if ever needed). Due to its algebraic nature, the proposed approach can support a wide range of realistic geometries (e.g., layered and channelized media). Numerical examples show that the proposed class of physics-based preconditioners are more effective and robust compared to a class of Krylov-based deflation methods on highly heterogeneous media.

Two trust-region methods for systems of mixed nonlinear equalities, general inequalities and simple bounds are proposed. The first method is based on a Gauss–Newton model, the second one is based on a regularized Gauss–Newton model and results to be a Levenberg–Marquardt method. The globalization strategy uses affine scaling matrices arising in bound-constrained optimization. Global convergence results are established and quadratic rate is achieved under an error bound assumption. The numerical efficiency of the new methods is experimentally studied.

Based on Chebyshev-Gauss-Lobatto points, the piecewise linear finite element preconditioner is analyzed in terms of condition numbers for the high-order element discretizations applied to a model elliptic operator. The optimality of such a preconditioner is proved for one-dimensional case and the scalability is shown for two-dimensional case. Further, we provide O(N^1^/^3) growth of piecewise linear finite element preconditioner numerically.

A local reconstruction method is discussed for functions belonging to a shift invariant space arising out of a function which has polynomial decay in time domain and moderate decay in frequency domain such that its Fourier transform is non-vanishing on a unit interval. This method is useful in solving the scaling identity (associated wavelet basis) locally. � 2008 IMACS.

For biharmonic equations, the Hermite finite element methods (FEM) are chosen, to seek their approximate solutions. The linear algebraic equations Ax=b are obtained from the Hermite FEM, where the matrix A is symmetric and positive definite, and x and b are the unknown and known vectors, respectively. It is well known that Cond=@l"m"a"x@l"m"i"n, and @l"m"a"x and @l"m"i"n are the maximal and minimal eigenvalues of the stiffness matrix A, respectively. The bounds of Cond are derived to be O(h^-^4). Note that when h is small, the values of Cond (=O(h^-^4)) are huge, to indicate a severe instability, compared with Cond =O(h^-^2) for Poisson's equation by the FEM. In fact, for specific application problems, the instability is not so severe, a new effective condition number is defined by Cond_eff =@?b@?@?x@?@l"m"i"n in [Z.C. Li, C.S. Chien, H.T. Huang, Effective condition number for finite difference method, Comput. Appl. Math. 198 (2007) 208-235], to provide a better upper bound of perturbation errors. It is proven that Cond_eff =O(h^-^3^.^5) for general cases, which is smaller than the traditional Cond. However, for special cases, the Cond_eff could be much smaller. For instant, for the homogeneous boundary conditions of biharmonic equations, Cond_eff =O(1), can be reached as h diminishes. This is astonishing, against our intuition from the knowledge of the Cond. From the analysis in this paper, the traditional Cond may mislead the stability analysis for practical computation of engineering problems.

It is well known that for the discretization of the biharmonic operator with spectral methods (Galerkin, tau, or collocation) we have a condition number of O(N^8), where N is the number of retained modes of approximations. This paper presents some efficient spectral algorithms, for reducing this condition number to O(N^4), based on the Jacobi-Galerkin methods for fourth-order equations in one variable. The key to the efficiency of these algorithms is to construct appropriate base functions, which lead to systems with specially structured matrices that can be efficiently inverted. Jacobi-Galerkin methods for fourth-order equations in two dimension are considered. Numerical results indicate that the direct solvers presented in this paper are significantly more accurate at large N values than that based on the Chebyshev- and Legendre-Galerkin methods.

In this paper, error estimates for the finite point method are presented in Sobolev spaces in multiple dimensions when nodes and shape functions satisfy certain conditions. From the error analysis of the finite point method, the error bound of the numerical solution is directly related to the radii of the weight functions and the condition number of the coefficient matrix.

We address the solution of multiregion elliptic and parabolic problems with strongly discontinuous coefficients across interfaces. The underlying idea is, roughly, to perturb around the infinitely discontinuous coefficient solution, that is, to perturb the solution where one region is a perfect conductor. The result is partial decoupling of the interface conditions. The algorithm requires a small number of well-conditioned solves in the individual regions (in many cases only a single solve over each region is necessary) that are then assembled into an accurate global solution. The error from the assembly step is asymptotically small in the ratio of the discontinuous coefficients. Further, the framework can be extended to problems with moderately discontinuous coefficients using a series expansion in the discontinuity ratio in a manner similar to a Schwarz alternating method.

In this paper, we report some new discoveries of Adini's elements for Poisson's equation in error estimates, stability analysis and global superconvergence. It is well known that the optimal convergence rate ||u - uh||I = O(h3|u|4) can be obtained, where uh and u are the Adini's solution and the true solution, respectively. In this paper, for all kinds of boundary conditions of Poisson's equations, the supercloseness ||uIA - uh||I = O(h3.5||u||5) can be obtained for uniform rectangles □ij, where uIA is the Adini's interpolation of the true solution u. Moreover, for the Neumann problems of Poisson's equation, new treatments adding the explicit natural constraints (un)ij = gij on the boundary are proposed to yield the Adini's solution uh* having supercloseness ||uIA - uh*||I = O(h4||u||5). Hence, the global superconvergence ||u-Π5 uh*||I = O(h4||u||5) can be achieved, where Π5uh* is an a posteriori interpolant of polynomials with order five based on the obtained solution uh*. New basic estimates of errors are derived for Adini's elements. Numerical experiments in this paper are also provided to verify the supercloseness and superconvergences, O(h3.5) and O(h4), and the standard condition number O(h-2). It is worthy pointing out that for the Neumann problems on rectangular domains, the traditional finite element method is not as good as the newly proposed method interpolating the Neumann condition in this paper. Not only is the new method more accurate, but also economical in computation, as the discrete system has less unknowns.

The aim of this paper is to obtain error estimates for a modified local Shepard's approximation. This interpolation operator uses approximated Taylor polynomials at the data points glued together by a local Shepard's partition of unity. We introduce a condition number which is a geometric measure of the quality of the approximate derivatives obtained by least square fits of polynomials to function values at nearby nodes. The condition number is practically computable and it is closely related to the approximating power of the method. The error estimates obtained are important in the analysis of Galerkin approximations based on these Shepard's interpolation operators.

We consider the solution of the linear system (ATA + σI)Xσ = ATb, for various real values of σ. This family of shifted systems arises, for example, in Tikhonov regularization and computations in lattice quantum chromodynamics. For each single shift σ this system can be solved using the conjugate gradient method for least squares problems (CGLS). In literature various implementations of the, so-called, multishift CGLS methods have been proposed. These methods are mathematically equivalent to applying the CGLS method to each shifted system separately but they solve all systems simultaneously and require only two matrix-vector products (one by A and one by AT) and two inner products per iteration step. Unfortunately, numerical experiments show that, due to roundoff errors, in some cases these implementations of the multishift CGLS method can only attain an accuracy that depends on the square of condition number of the matrix A. In this paper we will argue that, in the multishift CGLS method, the impact on the attainable accuracy of rounding errors in the Lanczos part of the method is independent of the effect of roundoff errors made in the construction of the iterates. By making suitable design choices for both parts, we derive a new (and efficient) implementation that tries to remove the limitation of previous proposals. A partial roundoff error analysis and various numerical experiments show promising results.

The goal of this paper is to study the relation of the condition number of the star of nodes in normal equations for error estimates of Moving Least Square approximations in Sobolev spaces. The condition numbers are closely related to the good quality of the set of nodes and the approximating power of the method.

First, the basic theory of matrix polynomials and the construction of solvents are reviewed in terms of the concept of eigenpair. Then a study of the number of solvents is done. Conditions for the number of solvents to be infinite are stated and for a finite (positive) number the minimum and the maximum are estimated.

For three space dimensions, from now on, we show that the condition number of the incremental unknowns matrix associated to the Laplace operator is O(1/H2)O((1/h)|log h|), where H is the mesh size of the coarsest grid and where h is the mesh size of the finest grid; furthermore, if block diagonal scaling is used, the condition number of the preconditioned incremental unknowns matrix associated to the Laplace operator turns out to be O(1/h), these conditioning results proved by using a generic algebraic conditioning analysis-based upon graph techniques--and by setting up a discrete inequality. In contrast, the condition number of the nodal unknowns matrix associated to the Laplace operator is O (1/h2). Therefore, the incremental unknowns preconditioner is an efficient preconditioner in three space dimensions.

We introduce a new algorithm for the evaluation, at a general point x, of the pth derivative of a polynomial expressed as a finite series of Jacobi polynomials. The proposed algorithm permits the direct evaluation without obtaining the pth derivative of the polynomial itself, with the consequent memory and time savings. The stability of the algorithm is studied and it is compared with classical methods for evaluating derivatives in pseudospectral methods. Another algorithm, based on the previous one, is also proposed to reduce the rounding errors near the endpoints of the interval of evaluation.

The Conjugate Gradient Method (CG) has an intrinsic regularization property when applied to systems of linear equations with ill-conditioned matrices. This regularization property is specially useful when either the right-hand side or the coefficient matrix, or both are given with errors. The regularization parameter is the iteration number, and in order to find this parameter, the L-curve is used. Here we present a novel method to find the corner of the L-curve, that determines the regularizing iteration number. Numerical results on the collection of test problems [SIAM J. Sci. Comput. 16 (1995) 506-512] are given to illustrate the potentiality of the method.

In this article, we define the notion of block incremental unknowns for anisotropic elliptic equations. Written in a block structure, they are nothing more than the classical second order incremental unknowns in one space dimension. In particular, we obtain a priori estimates and we observe a significant gain in the condition number for stiff problems when compared with the classical two-dimensional second order incremental unknowns.