Search

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.

Circulant and skew-circulant splitting iteration method is employed for solving linear systems from finite difference discretisation of tempered fractional diffusion equations. The method is shown to be convergent unconditionally and the convergence rate is fast in numerical tests. In each iteration, a circulant system and a skew-circulant system are required to be solved which cost only $$O(N\log N)$$ operations by fast Fourier transform, where N is the number of interior mesh points in space. Moreover, the induced preconditioner possesses circulant-times-skew-circulant structure so that it can be inverted in $$O(N\log N)$$ operation. In all of our numerical experiments, the preconditioner performs very well with a very simple choice of the method parameter.

High-dimensional two-sided space fractional diffusion equations with variable diffusion coefficients are discussed. The problems can be solved by an implicit finite difference scheme that is proven to be uniquely solvable, unconditionally stable and first-order convergent in the infinity norm. A nonsingular multilevel circulant pre-conditoner is proposed to accelerate the convergence rate of the Krylov subspace linear system solver efficiently. The preconditoned matrix for fast convergence is a sum of the identity matrix, a matrix with small norm, and a matrix with low rank under certain conditions. Moreover, the preconditioner is practical, with an O(NlogN) operation cost and O(N) memory requirement. Illustrative numerical examples are also presented.

The unconditional stability of a second order finite difference scheme for space fractional diffusion equations is proved theoretically for a class of variable diffusion coefficients. In particular, the scheme is unconditionally stable for all one-sided problems and problems with Riesz fractional derivative. For problems with general smooth diffusion coefficients, numerical experiments show that the scheme is still stable if the space step is small enough.

We consider a discrete-time orthogonal spline collocation scheme for solving Schrodinger equation with wave operator. The scheme is proposed recently by Wang et al. (J Comput Appl Math 235 (2011), 1993–2005) and is showed to have high-order convergence rate when a parameter θ in the scheme is not less than . In this article, we show that the result can be extended to include under an assumption. Numerical example is given to justify the theoretical result. © 2012 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2013

Based on our continuum hydrodynamic model for immiscible two-phase flows at solid surfaces, the stick-slip motion has been predicted for moving contact line at chemically patterned surfaces [Wang et al., J. Fluid Mech., 605 (2008), pp. 59-78]. In this paper we show that the continuum predictions can be quantitatively verified by molecular dynamics (MD) simulations. Our MD simulations are carried out for two immiscible Lennard-Jones fluids confined by two planar solid walls in Poiseuille flow geometry. In particular, one solid surface is chemically patterned with alternating stripes. For comparison, the continuum model is numerically solved using material parameters directly measured in MD simulations. From oscillatory fluid-fluid interface to intermittent stick-slip motion of moving contact line, we have quantitative agreement between the continuum and MD results. This agreement is attributed to the accurate description down to molecular scale by the generalized Navier boundary condition in our continuum model. Numerical results are also presented for the relaxational dynamics of fluid-fluid interface, in agreement with a theoretical analysis based on the Onsager principle of minimum energy dissipation. PACS: 68.08.-p, 83.50.Rp, 83.10.Mj, 83.10.Ff

We consider the solution of differential equations with multidelays by using boundary value methods (BVMs). These methods require the solution of some nonsymmetric, large and sparse linear systems. The GMRES method with the Strang-type block-circulant preconditioner is proposed to solve these linear systems. If an A k 1 , k 2 -stable BVM is used, we show that our preconditioner is invertible and the spectrum of the preconditioned matrix is clustered. It follows that when the GMRES method is applied to solving the preconditioned systems, the method would converge fast. Numerical results are given to show the effectiveness of our methods.

In this paper, we study nonsymmetric and highly nondiagonally dominant linear systems that arise from discretizations of constant-coefficient first-order partial differential equations (PDEs). We apply the generalized minimal residual method [Y. Saad, Iterative Methods for Sparse Linear Systems, PWS Publishing Company, Boston] for solving the system with a preconditioner based on the fast sine transform. An analytic formula for the eigenvalues of the preconditioned matrix is derived and it is shown that the eigenvalues are clustered around 1 except some outliers. The outlier eigenvalues are bounded and well separated from the origin when the size of system increases. In numerical experiments, we compare our preconditioner with the semi-Toeplitz preconditioner proposed in [SIAM J. Sci. Comput. 17 (1996) 47]. We refer to [J. Numer. Linear Algebra Appl. 1 (1992) 77, Numer. Math. J. Chinese Univ. 2 (1993) 116, BIT 32 (1992) 650, Linear Algebra Appl. 293 (1999) 85] for the early works on preconditioning techniques for PDEs.

We consider the solution of delay differential equations (DDEs) by using boundary value methods (BVMs). These methods require the solution of one or more nonsymmetric, large and sparse linear systems. The GMRES method with the Strang-type block-circulant preconditioner is proposed for solving these linear systems. We show that if a P k 1,k 2-stable BVM is used for solving an m-by-m system of DDEs, then our preconditioner is invertible and all the eigenvalues of the preconditioned system are clustered around 1. It follows that when the GMRES method is applied to solving the preconditioned systems, the method may converge fast. Numerical results are given to illustrate the effectiveness of our methods.