正交匹配追踪算法的迭代残差重建方法

正交匹配追踪(Orthogonal Matching Pursuit, OMP)算法是一种重要的压缩感知重构算法. OMP算法在每次迭代中选择与当前残差最相关的原子. 针对每次迭代需要重新计算残差的问题, 本文考虑偶数次迭代下残差未知的情况. 首先, 研究了奇数次迭代的残差与下一次迭代的残差之间的关系, 得到了一种偶数次迭代时选择原子的标准. 然后, 引入一种回溯机制来处理前面所得的迭代结果, 这种机制通过剔除其中多余的原子来实现精确重建. 据此, 提出了可减少计算残差的改进型正交匹配追踪算法.     

基于Kronecker型替换的黑盒多项式稀疏插值

本文基于新的Kronecker型替换,给出两个由黑盒表示的稀疏多项式的新确定性插值算法.令f∈R[x1,……,xn]是一个稀疏黑盒多项式,其次数上界为D.当R是C或者是有限域时,相对于已有算法,新算法具有更好的计算复杂度或者关于D的复杂度更低.特别地,对于一般黑盒模型,D是复杂度中的主要因素,而在所有的确定性算法中,本文的第二个算法的复杂度关于D是最低的.     

Spectral estimates for saddle point matrices arising in weak constraint four‐dimensional variational data assimilation

We consider the large sparse symmetric linear systems of equations that arise in the solution of weak constraint four‐dimensional variational data assimilation, a method of high interest for numerical weather prediction. These systems can be written as saddle point systems with a 3 × 3 block structure but block eliminations can be performed to reduce them to saddle point systems with a 2 × 2 block structure, or further to symmetric positive definite systems. In this article, we analyse how sensitive the spectra of these matrices are to the number of observations of the underlying dynamical system. We also obtain bounds on the eigenvalues of the matrices. Numerical experiments are used to confirm the theoretical analysis and bounds.     

第二类端点奇异Fredholm积分方程的分数阶退化核方法

本文针对第二类端点奇异Fredholm积分方程构造基于分数阶Taylor展开的退化核方法，设计了两种计算格式，一是在全区间上使用分数阶Taylor展开式近似核函数，二是在包含奇点的小区间上采用分数阶插值，在剩余区间上采用分段二次多项式插值逼近核函数.讨论了两种退化核方法收敛的条件，并给出了混合插值法的收敛阶估计.数值算例表明对于非光滑核函数分数阶退化核方法有着良好的计算效果，且混合二次插值法比全区间上的分数阶退化核方法有着更广泛的适用范围.     

Numerical solution of a singular integral equation arising in a cruciform crack problem

A singular integral equation arising in a cruciform crack problem is investigated in the present paper. Based on the convex technique, the piecewise Taylor-series expansion method is extended by introducing a weight parameter. An approximate solution of the singular integral equation is constructed and its convergence and error estimate are made. The variations of the approximate solutions associating with stress intensity factors are analyzed by considering internal pressures of power and sine functions, respectively. By comparing with the known methods, the observations reveal that a good approximation can be achieved using less derivative times, less discretization points, and a suitable weight parameter. The obtained results show that the crack growth is dependent on applied mechanical loadings.     

广义Khasminskii条件下自变量分段连续型带Poisson随机测度随机微分方程Euler方法的依概率收敛性

针对满足广义Khasminskii条件的由维纳过程和泊松随机测度驱动的自变量分段连续型随机微分方程(EPCASDEs),给出了Euler方法,广义Khasminskii条件比经典条件包容了更多的EPC.ASDEs.现有文献对该类方程的研究成果较少.针对EPCASDEs在广义Khasminskii条件下证明了全局解的存在唯一性,并研究了Euler方法的依概率收敛性.给出了数值算例支持主要结论.     

基于Delaunay三角剖分的地表平均温度模拟

利用Delaunay三角网对目标区域进行剖分,在对地表温度进行高度插值后,运用二重积分的思想建立了基于Delaunayr三角剖分的地表平均温度测量模型.同时以南极地表平均温度的测量为例,将67个自动气象地表台站、46个气象地表台站以及56个高空气象观测站的加权平均温度与地表平均温度的数据进行分析,得到南极2015全年地表平均温度均在-8℃以下,最低温约为-20℃,符合南极大陆地表温度的实际情况.     

Constructing near spanning trees with few local inspections

Constructing a spanning tree of a graph is one of the most basic tasks in graph theory. Motivated by several recent studies of local graph algorithms, we consider the following variant of this problem. Let G be a connected bounded‐degree graph. Given an edge e in G we would like to decide whether e belongs to a connected subgraph consisting of edges (for a prespecified constant ), where the decision for different edges should be consistent with the same subgraph . Can this task be performed by inspecting only a constant number of edges in G ? Our main results are:

• We show that if every t‐vertex subgraph of G has expansion then one can (deterministically) construct a sparse spanning subgraph of G using few inspections. To this end we analyze a “local” version of a famous minimum‐weight spanning tree algorithm.
• We show that the above expansion requirement is sharp even when allowing randomization. To this end we construct a family of 3‐regular graphs of high girth, in which every t‐vertex subgraph has expansion . We prove that for this family of graphs, any local algorithm for the sparse spanning graph problem requires inspecting a number of edges which is proportional to the girth.

© 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 183–200, 2017     

Convergent sequences of sparse graphs: A large deviations approach

Models based on sparse graphs are of interest to many communities: they appear as basic models in combinatorics, probability theory, optimization, statistical physics, information theory, and more applied fields of social sciences and economics. Different notions of similarity (and hence convergence) of sparse graphs are of interest in different communities. In probability theory and combinatorics, the notion of Benjamini‐Schramm convergence, also known as left‐convergence, is used quite frequently. Statistical physicists are interested in the the existence of the thermodynamic limit of free energies, which leads naturally to the notion of right‐convergence. Combinatorial optimization problems naturally lead to so‐called partition convergence, which relates to the convergence of optimal values of a variety of constraint satisfaction problems. The relationship between these different notions of similarity and convergence is, however, poorly understood. In this paper we introduce a new notion of convergence of sparse graphs, which we call Large Deviations or LD‐convergence, and which is based on the theory of large deviations. The notion is introduced by “decorating” the nodes of the graph with random uniform i.i.d. weights and constructing corresponding random measures on and . A graph sequence is defined to be converging if the corresponding sequence of random measures satisfies the Large Deviations Principle with respect to the topology of weak convergence on bounded measures on . The corresponding large deviations rate function can be interpreted as the limit object of the sparse graph sequence. In particular, we can express the limiting free energies in terms of this limit object. We then establish that LD‐convergence implies the other three notions of convergence discussed above, and at the same time establish several previously unknown relationships between the other notions of convergence. In particular, we show that partition‐convergence does not imply left‐ or right‐convergence, and that right‐convergence does not imply partition‐convergence. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 51, 52–89, 2017     

HIGH PERFORMANCE SPARSE SOLVER FOR UNSYMMETRICAL LINEAR EQUATIONS WITH OUT-OF-CORE STRATEGIES AND ITS APPLICATION ON MESHLESS METHODS

A new direct method for solving unsymmetrical sparse linear systems(USLS) arising from meshless methods was introduced. Computation of certain meshless methods such as meshless local Petrov-Galerkin (MLPG) method need to solve large USLS. The proposed solution method for unsymmetrical case performs factorization processes symmetrically on the upper and lower triangular portion of matrix, which differs from previous work based on general unsymmetrical process, and attains higher performance. It is shown that the solution algorithm for USLS can be simply derived from the existing approaches for the symmetrical case. The new matrix factorization algorithm in our method can be implemented easily by modifying a standard JKI symmetrical matrix factorization code. Multi-blocked out-of-core strategies were also developed to expand the solution scale. The approach convincingly increases the speed of the solution process, which is demonstrated with the numerical tests.