Block preconditioners for linear systems arising from multiscale collocation with compactly supported RBFs

Symmetric collocation methods with RBFs allow approximation of the solution of a partial differential equation, even if the right‐hand side is only known at scattered data points, without needing to generate a grid. However, the benefit of a guaranteed symmetric positive definite block system comes at a high computational cost. This cost can be alleviated somewhat by considering compactly supported RBFs and a multiscale technique. But the condition number and sparsity will still deteriorate with the number of data points. Therefore, we study certain block diagonal and triangular preconditioners. We investigate ideal preconditioners and determine the spectra of the preconditioned matrices before proposing more practical preconditioners based on a restricted additive Schwarz method with coarse grid correction. Numerical results verify the effectiveness of the preconditioners. Copyright © 2015 John Wiley & Sons, Ltd.     

Improved seed methods for symmetric positive definite linear equations with multiple right‐hand sides

We consider symmetric positive definite systems of linear equations with multiple right‐hand sides. The seed conjugate gradient (CG) method solves one right‐hand side with the CG method and simultaneously projects over the Krylov subspace thus developed for the other right‐hand sides. Then the next system is solved and used to seed the remaining ones. Rounding error in the CG method limits how much the seeding can improve convergence. We propose three changes to the seed CG method: only the first right‐hand side is used for seeding, this system is solved past convergence, and the roundoff error is controlled with some reorthogonalization. We will show that results are actually better with only one seeding, even in the case of related right‐hand sides. Controlling rounding error gives the potential for rapid convergence for the second and subsequent right‐hand sides. Polynomial preconditioning can help reduce storage needed for reorthogonalization. The new seed methods are applied to examples including matrices from quantum chromodynamics. Copyright © 2013 John Wiley & Sons, Ltd.     

循环矩阵及其在结构计算中的应用

本文推广了循环矩阵的概念,讨论了它的一般性质,并提出了一种解系数矩阵为循环矩阵或准循环矩阵的线性代数方程组(这种方程组在一大类常见的结构物的计算中出现)的方法,这种解法比通常解法计算量小而且节省存储,同时还允许应用快速富氏变换以增怏其计算速度。     

Bernstein polynomial basis for numerical solution of boundary value problems

The purpose of this paper is to propose a computational method for the approximate solution of linear and nonlinear two-point boundary value problems. In order to approximate the solution, the expansions in terms of the Bernstein polynomial basis have been used. The properties of the Bernstein polynomial basis and the corresponding operational matrices of integration and product are utilized to reduce the given boundary value problem to a system of algebraic equations for the unknown expansion coefficients of the solution. On this approach, the problem can be solved as a system of algebraic equations. By considering a special case of the problem, an error analysis is given for the approximate solution obtained by the present method. At last, five examples are examined in order to illustrate the efficiency of the proposed method.     

ON THE ACCURACY OF THE LEAST SQUARES AND THE TOTAL LEAST SQUARES METHODS

Consider solving an overdetermined system of linear algebraic equations by both the least squares method (LS) and the total least squares method (TLS). Extensive published computational evidence shows that when the original system is consistent. one often obtains more accurate solutions by using the TLS method rather than the LS method. These numerical observations contrast with existing analytic perturbation theories for the LS and TLS methods which show that the upper bounds for the LS solution are always smaller than the corresponding upper bounds for the TLS solutions. In this paper we derive a new upper bound for the TLS solution and indicate when the TLS method can be more accurate than the LS method.Many applied problems in signal processing lead to overdetermined systems of linear equations where the matrix and right hand side are determined by the experimental observations (usually in the form of a lime series). It often happens that as the number of columns of the matrix becomes larger, the ra     

Semi-Conjugate Direction Methods for Real Positive Definite Systems

In this preliminary work, left and right conjugate direction vectors are defined for nonsymmetric, nonsingular matrices A and some properties of these vectors are studied. A left conjugate direction (LCD) method for solving nonsymmetric systems of linear equations is proposed. The method has no breakdown for real positive definite systems. The method reduces to the usual conjugate gradient method when A is symmetric positive definite. A finite termination property of the semi-conjugate direction method is shown, providing a new simple proof of the finite termination property of conjugate gradient methods. The new method is well defined for all nonsingular M-matrices. Some techniques for overcoming breakdown are suggested for general nonsymmetric A. The connection between the semi-conjugate direction method and LU decomposition is established. The semi-conjugate direction method is successfully applied to solve some sample linear systems arising from linear partial differential equations, with attractive convergence rates. Some numerical experiments show the benefits of this method in comparison to well-known methods. This revised version was published online in July 2006 with corrections to the Cover Date.     

A preconditioned low‐rank CG method for parameter‐dependent Lyapunov matrix equations

This paper is concerned with the numerical solution of symmetric large‐scale Lyapunov equations with low‐rank right‐hand sides and coefficient matrices depending on a parameter. Specifically, we consider the situation when the parameter dependence is sufficiently smooth, and the aim is to compute solutions for many different parameter samples. On the basis of existing results for Lyapunov equations and parameter‐dependent linear systems, we prove that the tensor containing all solution samples typically allows for an excellent low multilinear rank approximation. Stacking all sampled equations into one huge linear system, this fact can be exploited by combining the preconditioned CG method with low‐rank truncation. Our approach is flexible enough to allow for a variety of preconditioners based, for example, on the sign function iteration or the alternating direction implicit method. Copyright © 2013 John Wiley & Sons, Ltd.     

Solving boundary value problems,integral, and integro-differential equations using Gegenbauer integration matrices

We introduce a hybrid Gegenbauer (ultraspherical) integration method (HGIM) for solving boundary value problems (BVPs), integral and integro-differential equations. The proposed approach recasts the original problems into their integral formulations, which are then discretized into linear systems of algebraic equations using Gegenbauer integration matrices (GIMs). The resulting linear systems are well-conditioned and can be easily solved using standard linear system solvers. A study on the error bounds of the proposed method is presented, and the spectral convergence is proven for two-point BVPs (TPBVPs). Comparisons with other competitive methods in the recent literature are included. The proposed method results in an efficient algorithm, and spectral accuracy is verified using eight test examples addressing the aforementioned classes of problems. The proposed method can be applied on a broad range of mathematical problems while producing highly accurate results. The developed numerical scheme provides a viable alternative to other solution methods when high-order approximations are required using only a relatively small number of solution nodes.     

A new numerical method for delay and advanced integro-differential equations

A general formulation is constructed for Jacobi operational matrices of integration, product, and delay on an arbitrary interval. The main purpose of this study is to improve Jacobi operational matrices for solving delay or advanced integro–differential equations. Some theorems are established and utilized to reduce the computational costs. All algorithms can be used for both linear and nonlinear Fredholm and Volterra integro-differential equations with delay. An error estimator is introduced to approximate the absolute error when the exact solution of a given problem is not available. The error of the proposed method is less compared to other common methods such as the Taylor collocation, Chebyshev collocation, hybrid Euler–Taylor matrix, and Boubaker collocation methods. The reliability and efficiency of the proposed scheme are demonstrated by some numerical experiments.     

On the applicability of Genocchi wavelet method for different kinds of fractional‐order differential equations with delay

A novel collocation method based on Genocchi wavelet is presented for the numerical solution of fractional differential equations and time‐fractional partial differential equations with delay. In this work, to achieve the approximate solution with height accuracy, we employed the operational matrix of integer derivative and the pseudo‐operational matrix of fractional derivative in Caputo sense. Also, based on Genocchi function properties, we presented delay and pantograph operational matrices of Genocchi wavelet functions (GWFs). Due to operational and pseudo‐operational matrices, the equations under this study can be turned into nonlinear algebraic equations with the unknown GWF coefficients. For illustrating the upper bound of error for the proposed method, we estimate the error in the sense of Sobolev space. In addition, to demonstrate the efficacy of the pseudo‐operational matrix of fractional derivative, we investigate the upper bound of error for the mentioned matrix. Finally, the algorithm based on the proposed approach is implemented for some numerical experiments to confirm accuracy and applicability.     

On solution of large systems of linear equations with block-Toeplitz banded matrices

A novel numerical algorithm is proposed for solving systems of linear equations with block-Toeplitz narrow-banded matrices. Its arithmetical cost is about double of that of the block cyclic reduction. The backward roundoff error stability of the method guarantees its reliability for the matrices that are not symmetric positive definite or diagonally dominant.     

Substructured two-grid and multi-grid domain decomposition methods

Two-level Schwarz domain decomposition methods are very powerful techniques for the efficient numerical solution of partial differential equations (PDEs). A two-level domain decomposition method requires two main components: a one-level preconditioner (or its corresponding smoothing iterative method), which is based on domain decomposition techniques, and a coarse correction step, which relies on a coarse space. The coarse space must properly represent the error components that the chosen one-level method is not capable to deal with. In the literature, most of the works introduced efficient coarse spaces obtained as the span of functions defined on the entire space domain of the considered PDE. Therefore, the corresponding two-level preconditioners and iterative methods are defined in volume. In this paper, we use the excellent smoothing properties of Schwarz domain decomposition methods to define, for general elliptic problems, a new class of substructured two-level methods, for which both Schwarz smoothers and coarse correction steps are defined on the interfaces (except for the application of the smoother that requires volumetric subdomain solves). This approach has several advantages. On the one hand, the required computational effort is cheaper than the one required by classical volumetric two-level methods. On the other hand, our approach does not require, like classical multi-grid methods, the explicit construction of coarse spaces, and it permits a multilevel extension, which is desirable when the high dimension of the problem or the scarce quality of the coarse space prevents the efficient numerical solution. Numerical experiments demonstrate the effectiveness of the proposed new numerical framework.

     

TWO-VARIABLE JACOBI POLYNOMIALS FOR SOLVING SOME FRACTIONAL PARTIAL DIFFERENTIAL EQUATIONS

Two-variable Jacobi polynomials, as a two-dimensional basis, are applied to solve a class of temporal fractional partial differential equations. The fractional derivative operators are in the Caputo sense. The operational matrices of the integration of integer and fractional orders are presented. Using these matrices together with the Tau Jacobi method converts the main problem into the corresponding system of algebraic equations. An error bound is obtained in a two-dimensional Jacobi-weighted Sobolev space. Finally, the efficiency of the proposed method is demonstrated by implementing the algorithm to several illustrative examples. Results will be compared with those obtained from some existing methods.     

A uniformly optimal‐order estimate for finite volume method for advection‐diffusion equations

We prove an optimal‐order error estimate in a weighted energy norm for finite volume method for two‐dimensional time‐dependent advection–diffusion equations on a uniform space‐time partition of the domain. The generic constants in the estimates depend only on certain norms of the true solution but not on the scaling parameter. These estimates, combined with a priori stability estimates of the governing partial differential equations with full regularity, yield a uniform estimate of the finite volume method, in which the generic constants depend only on the Sobolev norms of the initial and right side data but not on the scaling parameter. We use the interpolation of spaces and stability estimates to derive a uniform estimate for problems with minimal or intermediate regularity, where the convergence rates are proportional to certain Besov norms of the initial and right‐hand side data. © 2013 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 30: 17‐43, 2014     

On fast direct methods for solving elliptic equations over nonrectangular regions

In this paper, two methods based on the symmetric marching technique (SMT) are presented for the solution of elliptic equations over nonrectangular regions. Method I illustrates the direct adaptation of the SMT to irregular geometries. In method II, an efficient implementation of the capacitance matrix method has been considered using SMT. The favorable characteristics of the SMT for solving the Poisson equation with several right hand side functions and different boundary conditions without extra computational effort have been exploited for the last generation of the capacitance matrix. The successful application of the SMT combined with quasilinearization to solve mildly nonlinear elliptic equations is also described. Several test examples have been solved to demonstrate the efficiency of the proposed methods.     

A new version of the Smith method for solving Sylvester equation and discrete-time Sylvester equation

Recently, Xue etc. \cite{28} discussed the Smith method for solving Sylvester equation $AX+XB=C$, where one of the matrices $A$ and $B$ is at least a nonsingular $M$-matrix and the other is an (singular or nonsingular) $M$-matrix. Furthermore, in order to find the minimal non-negative solution of a certain class of non-symmetric algebraic Riccati equations, Gao and Bai \cite{gao-2010} considered a doubling iteration scheme to inexactly solve the Sylvester equations. This paper discusses the iterative error of the standard Smith method used in \cite{gao-2010} and presents the prior estimations of the accurate solution $X$ for the Sylvester equation. Furthermore, we give a new version of the Smith method for solving discrete-time Sylvester equation or Stein equation $AXB+X=C$, while the new version of the Smith method can also be used to solve Sylvester equation $AX+XB=C$, where both $A$ and $B$ are positive definite. % matrices. We also study the convergence rate of the new Smith method. At last, numerical examples are given to illustrate the effectiveness of our methods     

Bi-criteria evolution strategy in estimating weights from the AHP ratio-scale matrices

The problem of deriving weights from ratio-scale matrices in an analytic hierarchy process (AHP) is addressed by researchers worldwide. There are various ways to solve the problem that are generally grouped into simple matrix and optimization methods. All methods have received criticism regarding the accuracy of derived weights, and different criteria are in use to compare the weights obtained from different methods. Because the set of Pareto non-dominated solutions (weights) is unknown and for inconsistent matrices is indefinite, a bi-criterion optimization approach is proposed for manipulating such matrices. The problem-specific evolution strategy algorithm (ESA) is implemented for a robust stochastic search over a feasible indefinite solution space. The fitness function is defined as a scalar vector function composed of the common error measure, i.e. the Euclidean distance and a minimum violation error that accounts for no violation of the rank ordering. The encoding scheme and other components of the search engine are adjusted to preserve the imposed constraints related to the required normalized values of the weights. The solutions generated by the proposed approach are compared with solutions obtained by five well-known prioritization techniques for three judgment matrices taken from the literature. In these and other test applications, the prioritization method that uses the entitled weights estimation by evolution strategy algorithm (WEESA) appears to be superior to other methods if only two, the most commonly used methods, are applied: the Euclidean distance and minimum violation exclusion criteria.     

Operational matrices of Chebyshev cardinal functions and their application for solving delay differential equations arising in electrodynamics with error estimation

In this paper, a new and effective direct method to determine the numerical solution of pantograph equation, pantograph equation with neutral term and Multiple-delay Volterra integral equation with large domain is proposed. The pantograph equation is a delay differential equation which arises in quite different fields of pure and applied mathematics, such as number theory, dynamical systems, probability, mechanics and electrodynamics. The method consists of expanding the required approximate solution as the elements of Chebyshev cardinal functions. The operational matrices for the integration, product and delay of the Chebyshev cardinal functions are presented. A general procedure for forming these matrices is given. These matrices play an important role in modelling of problems. By using these operational matrices together, a pantograph equation can be transformed to a system of algebraic equations. An efficient error estimation for the Chebyshev cardinal method is also introduced. Some examples are given to demonstrate the validity and applicability of the method and a comparison is made with existing results.     

Single projection Kaczmarz extended algorithms

In order to find the least squares solution of a very large and inconsistent system of equations, one can employ the extended Kaczmarz algorithm. This method simultaneously removes the error term, so that a consistent system is asymptotically obtained, and applies Kaczmarz iterations for the current approximation of this system. It has been shown that for random corrections of the right hand side and Kaczmarz updates selected at random, the algorithm converges to the least squares solution. In this work we consider deterministic strategies like the maximal-residual and the almost-cyclic control, and show convergence to a least squares solution.     

A preconditioned block Arnoldi method for large scale Lyapunov and algebraic Riccati equations

In the present paper, we propose a preconditioned Newton–Block Arnoldi method for solving large continuous time algebraic Riccati equations. Such equations appear in control theory, model reduction, circuit simulation amongst other problems. At each step of the Newton process, we solve a large Lyapunov matrix equation with a low rank right hand side. These equations are solved by using the block Arnoldi process associated with a preconditioner based on the alternating direction implicit iteration method. We give some theoretical results and report numerical tests to show the effectiveness of the proposed approach.