Algorithm for determining pure pointedness of self-affine tilings

Overlap coincidence in a self-affine tiling in Rd is equivalent to pure point dynamical spectrum of the tiling dynamical system. We interpret the overlap coincidence in the setting of substitution Delone set in Rd and find an efficient algorithm to check the pure point dynamical spectrum. This algorithm is easy to implement into a computer program. We give the program and apply it to several examples. In the course of the proof of the algorithm, we show a variant of the conjecture of Urbański (Solomyak (2006) [40]) on the Hausdorff dimension of the boundaries of fractal tiles.     

Fast amortized multi-point evaluation

The efficient evaluation of multivariate polynomials at many points is an important operation for polynomial system solving. Kedlaya and Umans have recently devised a theoretically efficient algorithm for this task when the coefficients are integers or when they lie in a finite field. In this paper, we assume that the set of points where we need to evaluate is fixed and “sufficiently generic”. Under these restrictions, we present a quasi-optimal algorithm for multi-point evaluation over general fields. We also present a quasi-optimal algorithm for the opposite interpolation task.     

Computing integral solutions of complementarity problems

In this paper an algorithm is proposed to find an integral solution of (nonlinear) complementarity problems. The algorithm starts with a nonnegative integral point and generates a unique sequence of adjacent integral simplices of varying dimension. Conditions are stated under which the algorithm terminates with a simplex, one of whose vertices is an integral solution of the complementarity problem under consideration.     

模糊推理的变权综合算法及其构造的模糊系统响应能力分析

将变权综合原理应用于模糊推理,提出一种新的模糊推理算法-变权综合推理算法,并给出利用模糊蕴涵算子确定规则变权的方法。证明了由一些正常蕴涵算子如Lukasiewicz蕴涵、Goguen蕴涵、Godel蕴涵、Dubois-Prade蕴涵等确定的变权综合算法是相容的。进一步分析了该变权综合算法构造的模糊系统的响应能力,结果表明:基于这些正常蕴涵算子的变权综合算法构造的模糊系统具有泛逼近性。     

Locally connected spanning trees in strongly chordal graphs and proper circular-arc graphs

A locally connected spanning tree of a graph G is a spanning tree T of G such that the set of all neighbors of v in T induces a connected subgraph of G for every v∈V(G). The purpose of this paper is to give linear-time algorithms for finding locally connected spanning trees on strongly chordal graphs and proper circular-arc graphs, respectively.     

遥感傅里叶变换红外光谱层析技术中的重构算法

在遥感傅里叶变换红外光谱层析技术中，对于是否能够快速、经济地得出气体空间浓度分布图及预测浓度峰位置，重构算法的选择是至重要的。理想的重构算法即使在仪器噪声较大、存在测量误差、光线数量少以及待测气体在空间的分布不稳定情况下，也能够通过有限的测量数据和非对称的光线构型，得出理想的重构图。本文对遥感傅里叶变换红外光谱层析技术中采用的几种重构算法，如ART法、MART法、SIRT法和SBFM法等，作了扼要描述。与传统的ART法相比，MART法在迭代速度和迭代精度上有较大的优越性，SIRT法克服了采用代数重构技术所带来的模糊性，SBFM法使重构结果噪声明显减小。     

一种非线性RED算法的研究

定量分析了平均队列长度与网络性能的关系，在介绍了尾丢弃和RED算法之后，提出了一种非线性RED算法，并将非线性RED算法与RED算法进行了定量的比较，指出采用非线性RED算法，路由器可以避免在平均队列长度到达最大阈值前过多地丢弃分组，而且可以提高路由器的缓冲区利用率。     

多目标优化问题的模糊交叉算法与收敛性

本文研究了目标权重未事先确知的多目标优化问题，建立可以同时确定目标权重与方案相对优属度的模糊交叉迭代算法，严格证明了该算法的局部收敛性．     

Recognizing Balanceable Matrices

A 0/±1 matrix is balanced if it does not contain a square submatrix with exactly two nonzero entries per row and per column in which the sum of all entries is 2 modulo 4. A 0/1 matrix is balanceable if its nonzero entries can be signed ±1 so that the resulting matrix is balanced. A signing algorithm due to Camion shows that the problems of recognizing balanced 0/±1 matrices and balanceable 0/1 matrices are equivalent. Conforti, Cornuéjols, Kapoor and Vušković gave an algorithm to test if a 0/±1 matrix is balanced. Truemper has characterized balanceable 0/1 matrices in terms of forbidden submatrices. In this paper we give an algorithm that explicitly finds one of these forbidden submatrices or shows that none exists. Received: October 2004     

一类半线性双曲系统的状态观测问题

本文考虑一类半线性双曲系统的状态观测问题,给出了一个(求解)算法并证明了其在某种相当强的意义上的有效性.