Solving sparse non-negative tensor equations: algorithms and applications

We study iterative methods for solving a set of sparse non-negative tensor equations (multivariate polynomial systems) arising from data mining applications such as information retrieval by query search and community discovery in multi-dimensional networks. By making use of sparse and non-negative tensor structure, we develop Jacobi and Gauss-Seidel methods for solving tensor equations. The multiplication of tensors with vectors are required at each iteration of these iterative methods, the cost per iteration depends on the number of non-zeros in the sparse tensors. We show linear convergence of the Jacobi and Gauss-Seidel methods under suitable conditions, and therefore, the set of sparse non-negative tensor equations can be solved very efficiently. Experimental results on information retrieval by query search and community discovery in multi-dimensional networks are presented to illustrate the application of tensor equations and the effectiveness of the proposed methods.     

Backward error and perturbation bounds for high order Sylvester tensor equation

In this article, we investigate the backward error and perturbation bounds for the high order Sylvester tensor equation (STE). The bounds of the backward error and three types of upper bounds for the perturbed STE with or without dropping the second order terms are presented. The classic perturbation results for the Sylvester equation are extended to the high order case.     

Splitting methods for tensor equations

The Jacobi, Gauss‐Seidel and successive over‐relaxation methods are well‐known basic iterative methods for solving system of linear equations. In this paper, we extend those basic methods to solve the tensor equation , where is an m th‐order n ?dimensional symmetric tensor and b is an n ‐dimensional vector. Under appropriate conditions, we show that the proposed methods are globally convergent and locally r‐linearly convergent. Taking into account the special structure of the Newton method for the problem, we propose a Newton‐Gauss‐Seidel method, which is expected to converge faster than the above methods. The proposed methods can be extended to solve a general symmetric tensor equations. Our preliminary numerical results show the effectiveness of the proposed methods.     

反应扩散方程的奇摄动

§ 1　 IntroductionThe nonlinearsingularly perturbed problem is a very attractive subjectof study in theinternational academic circles[1 ] .During the past decade many approximate methods havebeen developed and refined,including the method of average,boundary layer method,matched asymptotic expansions,and multiple scales.Recently,many scholars,for example,Bohé[2 ] ,Butuzov and Smurov[3] ,O Malley[4] ,Butuzov,Nefedov and Schneider[5] ,Kelley[6]and so on did a great deal of work.Mo consider…     

Iterative algorithms for solving some tensor equations

We propose a class of iterative algorithms to solve some tensor equations via Einstein product. These algorithms use tensor computations with no matricizations involved. For any (special) initial tensor, a solution (the minimal Frobenius norm solution) of related problems can be obtained within finite iteration steps in the absence of roundoff errors. Numerical examples are provided to confirm the theoretical results, which demonstrate that this kind of iterative methods are effective and feasible for solving some tensor equations.     

非Lipschitz系数随机波动方程适度解的存在唯一性

本文在系数为非Lipschitz条件下(Lipschitz和线性增长作为其特例),通过构造逐次逼近列的方法证明了随机波动方程适度解的存在唯一性.     

Derivatives for antisymmetric tensor powers and perturbation bounds

In an earlier paper (R. Bhatia, T. Jain, Higher order derivatives and perturbation bounds for determinants, Linear Algebra Appl. 431 (2009) 2102-2108) we gave formulas for derivatives of all orders for the map that takes a matrix to its determinant. In this paper we continue that work, and find expressions for the derivatives of all orders for the antisymmetric tensor powers and for the coefficients of the characteristic polynomial. We then evaluate norms of these derivatives, and use them to obtain perturbation bounds.     

Uniqueness and stability of solution for Cauchy problem of degenerate quasilinear parabolic equations

The uniqueness and existence of BV-solutions for Cauchy problem of the form are proved.     

Entrywise relative perturbation bounds for exponentials of essentially non-negative matrices

A real square matrix is said to be essentially non-negative if all of its off-diagonal entries are non-negative. We establish entrywise relative perturbation bounds for the exponential of an essentially non-negative matrix. Our bounds are sharp and contain a condition number that is intrinsic to the exponential function. As an application, we study sensitivity of continuous-time Markov chains. J. Xue was supported by the National Science Foundation of China under grant number 10571031, the Program for New Century Excellent Talents in Universities of China and Shanghai Pujiang Program. Q. Ye was supported in part by NSF under Grant DMS-0411502.     

Finite iterative algorithm for the complex generalized Sylvester tensor equations

A finite iterative algorithm is proposed to solve a class of complex generalized Sylvester tensor equations. The properties of this proposed algorithm are discussed based on a real inner product of two complex tensors and the finite convergence of this algorithm is obtained. Two numerical examples are offered to illustrate the effectiveness of the proposed algorithm.     

在Lipschitz条件下随机脉冲随机微分方程解的存在性和唯一性

随机脉冲随机微分方程有着广泛的应用, 本文主要研究在均方条件下, 此类方程解的存在性和唯一性. 在方程系数满足利普希兹条件以及脉冲时刻和脉冲函数满足一定条件下, 采用皮尔逊迭代, 柯系--施瓦兹不等式, 等矩公式以及随机分析中的技巧推导出结论.     

On the Krylov subspace methods based on tensor format for positive definite Sylvester tensor equations

This paper deals with studying some of well‐known iterative methods in their tensor forms to solve a Sylvester tensor equation. More precisely, the tensor form of the Arnoldi process and full orthogonalization method are derived by using a product between two tensors. Then tensor forms of the conjugate gradient and nested conjugate gradient algorithms are also presented. Rough estimation of the required number of operations for the tensor form of the Arnoldi process is obtained, which reveals the advantage of handling the algorithms based on tensor format over their classical forms in general. Some numerical experiments are examined, which confirm the feasibility and applicability of the proposed algorithms in practice. Copyright © 2016 John Wiley & Sons, Ltd.     

Preconditioned tensor format conjugate gradient squared and biconjugate gradient stabilized methods for solving stein tensor equations

This article is concerned with solving the high order Stein tensor equation arising in control theory. The conjugate gradient squared (CGS) method and the biconjugate gradient stabilized (BiCGSTAB) method are attractive methods for solving linear systems. Compared with the large-scale matrix equation, the equivalent tensor equation needs less storage space and computational costs. Therefore, we present the tensor formats of CGS and BiCGSTAB methods for solving high order Stein tensor equations. Moreover, a nearest Kronecker product preconditioner is given and the preconditioned tensor format methods are studied. Finally, the feasibility and effectiveness of the new methods are verified by some numerical examples.     

伴有边界摄动的Volterra型积分微分方程组的奇摄动

讨论了伴有边界摄动的二阶非线性Volterra型积分微分方程组的奇摄动.在适当的条件下,利用对角化技巧证明了解的存在性,构造出解的渐近展开式并给出余项的一致有效估计.     

On exact solutions to partial differential equations by the modified homotopy perturbation method

Based on the modified homotopy perturbation method (MHPM), exact solutions of certain partial differential equations are constructed by separation of variables and choosing the finite terms of a series in p as exact solutions. Under suitable initial conditions, the PDE is transformed into an ODE. Some illustrative examples reveal the effciency of the proposed method.     

Two perturbation bounds for singular values and eigenvalues

The relative error in as an approximation to α is measured by

矩阵广义逆新的扰动上界

利用矩阵的奇异值分解方法,研究了矩阵广义逆的扰动上界,得到了在F-范数下矩阵广义逆的扰动上界定理,所得定理推广并彻底改进了近期的相关结果.相应的数值算例验证了定理的有效性.     

A projection method and Kronecker product preconditioner for solving Sylvester tensor equations

The preconditioned iterative solvers for solving Sylvester tensor equations are considered in this paper.By fully exploiting the structure of the tensor equation,we propose a projection method based on the tensor format,which needs less flops and storage than the standard projection method.The structure of the coefficient matrices of the tensor equation is used to design the nearest Kronecker product(NKP) preconditioner,which is easy to construct and is able to accelerate the convergence of the iterative solver.Numerical experiments are presented to show good performance of the approaches.